Сокращение от Vertex Cover, чтобы доказать NP-завершенность

Question

Мы определяем ROMAN-SUBSET как следующую проблему:

ВХОД: Направленный граф G = (V, E) и положительное целое число k

ВЫХОД: Если существует подмножество R в V такое, что | R | <= k, и так, что каждая направленная схема в G включает в себя хотя бы одну вершину из R, то результат должен быть «ИСТИНА», в противном случае он должен быть "FALSE". </p>

Предполагая, что проблема Vertex Cover (VC) является NP-полной, я должен доказать, что ROMAN-SUBSET также NP-полная. Из того, что я понимаю, это означает, что нужно взять вход VC, изменить его, а затем показать, что подключение его к алгоритму ROMAN-SUBSET даст результат проблемы VC.

Мне очень тяжело придумывать трансформацию. Я знаю, что вход VC - это граф G и целое число k, и проблема в том, существует ли подмножество R в V, которое покрывает каждое ребро в G, такое, что | R | <= к. Ясно, что R и k похожи от ROM к VC, но моя трудность заключается в определении того, как преобразовать граф так, чтобы 1 вершина в каждом направленном цикле (для ROM) соответствовала каждому ребру (для VC). Как я могу изменить график, чтобы доказать, что VC может быть уменьшен до ROM? </p>

Спасибо!

Answer 1

Вот конструкция.

Возьмите неориентированный график G = (V, E), как в VC. Теперь определите ориентированный граф G1 = (V, E1), где для каждого ребра (u,v) в E есть два ребра (u,v) и (v,u) в E1.

Другими словами, новый граф такой же, как старый, но каждое ненаправленное ребро заменяется двумя направленными ребрами, которые образуют 2-цикл.

Утверждение состоит в том, что из ПЗУ на G1 следует VC на G.

Действительно, предположим, что ответ для ПЗУ на G1 - ЛОЖЬ. Тогда для каждого выбора множества, меньшего чем k вершин, существует цикл, не входящий в это множество. Таким образом, существует ребро, конечные точки которого не входят в набор. Но это означает, что для того же выбора набора из менее чем k вершин в G существует ребро, конечные точки которого не входят в набор, поэтому ответ VC - FALSE.

И наоборот, предположим, что ответ для ПЗУ на G1 - ИСТИНА. Тогда существует подмножество V, содержащее менее k вершин, так что для любого цикла в цикле существует хотя бы одна вершина, которая находится в наборе. Но это означает, что для любого ребра в E одна из его конечных точек в наборе, потому что ребро в E соответствует 2-циклу в E1. Таким образом, ответ для ВК - ИСТИНА.