Доказать, что диагноз направленного графа является NP-трудным

11

У меня есть домашнее задание, от которого я некоторое время ломал голову, и я буду благодарен за любые подсказки. Речь идет о выборе известной проблемы, NP-полнота которой доказана, и построении перехода от этой проблемы к следующей проблеме, которую я назову DGD (диагностика направленного графа).

проблема

Экземпляр DGD состоит из вершин , направленных ребер и целого положительного числа . Есть три типа вершин: вершины, только входящих ребра , вершины только с уходящими краями и вершинами с входящим и исходящими ребрами . Пусть , кроме того .V = I . вывода . B E k I O B D = O × I(V,E,k)V=I.O.BEkIOBD=O×I

Теперь проблема в том, можем ли мы покрыть все узлы не более чем элементами , т.е.DkD

SD,|S|k. vV. (v1,v2)S. v1vv2

где означает, что существует направленный путь от до .a babab


Я думаю, что проблема Доминирующего множества - это та, от которой я должен уменьшить, потому что это также касается покрытия подмножества узлов другим подмножеством. Я попытался создать экземпляр DGD, сначала создав два узла для каждого элемента доминирующего набора, скопировав все ребра, а затем установив экземпляра DGD равным таковому экземпляра DS.k

Предположим, что простой экземпляр DS с узлами , и и ребрами и . Это экземпляр типа yes с ; доминирующий набор в этом случае состоит только из узла . Сокращение с только что описанным методом приведет к созданию экземпляра DGD с двумя путями и ; чтобы покрыть все узлы, достаточно одной пары . Это сработало бы отлично, если бы не тот факт, что доминирующий набор экземпляра DS, конечно, не может быть определен за полиномиальное время, что здесь является обязательным требованием.123(1,2)(1,3)k=11(121)(131)(1,1)

Я обнаружил, что существует много красивых способов преобразования ребер и вершин при сокращении, но моя проблема как-то выразить DGD's в терминах DS . Доминирующий Сет казался подходящей проблемой для уменьшения, но из-за этого я думаю, что, возможно, мне следует попытаться уменьшить проблему, у которой нет такого ?kkk

user8879
источник
Добро пожаловать! Я попытался уточнить постановку проблемы; это как ты это имел ввиду? Кстати, вы можете выбрать более узнаваемое имя пользователя, чем «user8879». :)
Рафаэль
Да, спасибо, это действительно более компактная версия.
user8879

Ответы:

9

Вместо этого уменьшите от NP-полной SET-COVER .

Пусть с экземпляром набора покрытий. Определите экземпляр DGD следующим образом:S1,,Sm{1,,n}kN(V,E,k)

  • V={s1,,sm,o1,,om,e1,,en,o}
  • E={(si,oi)i=1,,n}{(si,ej)jSi}{(ej,o)j=1,,n}
  • k=m+k

Легко видеть , что построенный экземпляр DGD имеет положительный ответ , если и только если данный экземпляр набора крышка имеет положительный ответ. В частности, все пар имеет не должно быть выбран независимо от того , что для того , чтобы охватить все ; то из пара должно охватывать все , и первые компонентами, выбираемые являются решением экземпляра SET-крышки. Если такой выбор невозможен, экземпляр SET-COVER также не имеет решения.m(si,oi)oikm(si,o)ej

Поскольку построение возможно за полиномиальное время, это доказывает SET-COVER .p


В качестве примера рассмотрим пример покрытия экземпляра набора, приведенный в Википедии , а именно и наборы . Это переводит на следующий график:{1,2,3,4,5}S={{1,2,3},{2,4},{3,4},{4,5}}

пример
[ источник ]

Рафаэль
источник
1
Это почти правильно, потому что я и В действительно покрыты полностью, а О нет. Экземпляр set-cover является экземпляром yes для k = 2, но в экземпляре DGD k = 2 оставляет s2 и s3 незамеченными. Я думаю, что это, вероятно, можно решить путем автоматического добавления ребра от каждого узла в O к o .
user8879
@ user8879: Черт, да. Образом ставится задача сейчас, ребра не исправить , потому что для того , чтобы крышка вам нужно , по крайней мере , одну пару , содержащую его в . s i S(si,o)siS
Рафаэль
Теперь понятно: создайте дополнительный узел в B для каждого узла в O , затем свяжите его с соответствующим узлом в O и o . В этом примере вы получите четыре дополнительных пути (s1 -> s1 '-> o и т. Д.). Наконец, после увеличения k с четырьмя оно должно быть завершено.
user8879
@ user8879: Исправлено. Нам нужны некоторые дополнительные узлы, которые означают, что все покрыты, но мы остаемся полиномиальными по размеру. (О, вы прокомментировали, пока я исправлял, молодец.)si
Рафаэль