Udowodnienie, że diagnoza ukierunkowanego wykresu jest trudna do przeprowadzenia

11

Mam zadanie domowe, od którego walę głową od jakiegoś czasu i byłbym wdzięczny za wszelkie wskazówki. Chodzi o wybranie znanego problemu, którego kompletność NP jest udowodniona, i skonstruowanie redukcji z tego problemu do następującego problemu, który nazywam DGD (diagnostyka grafu ukierunkowanego).

Problem

Instancja projekcie wytycznych składa się z wierzchołkami V = I . O . B , skierowane krawędzie E i dodatnia liczba całkowita k . Istnieją trzy rodzaje wierzchołków: wierzchołki z krawędziami przychodzących tylko ja , tylko z wierzchołków krawędzi wychodzącej O i wierzchołków z zarówno przychodzących i wychodzących krawędzi B . Niech ponadto D = O x ja .(V,E,k)V=I.O.BEkIOBD=O×I

Problem polega na tym, czy możemy pokryć wszystkie węzły co najwyżej elementami D , tjkD

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

gdzie oznacza, że ​​istnieje ukierunkowana ścieżka od a do b .abab


Myślę, że problem Dominującego zestawu jest tym, z którego powinienem się zmniejszyć, ponieważ dotyczy to również pokrycia podzbioru węzłami innym podzbiorem. Próbowałem utworzyć instancję DGD, najpierw tworząc dwa węzły dla każdego elementu dominującego zestawu, kopiując wszystkie krawędzie, a następnie ustawiając wartość instancji DGD równą instancji DS.k

Załóżmy, że jest to prosta instancja DS z węzłami , 2 i 3 oraz krawędziami ( 1 , 2 ) i ( 1 , 3 ) . To jest instancja typu tak dla k = 1 ; dominujący zestaw w tym przypadku składa się tylko z węzła 1 . Zmniejszenie za pomocą właśnie opisanej metody prowadziłoby do wystąpienia instancji DGD z dwiema ścieżkami ( 1 2 1 ) i ( 1 3 1 )123(1,2)(1,3)k=11(121)(131); do pokrycia wszystkich węzłów wystarczyłaby tylko jedna para . Działałoby to idealnie, gdyby nie fakt, że dominujący zestaw instancji DS nie może być oczywiście określony w czasie wielomianowym, co jest tutaj wymagane.(1,1)

I odkryli, że istnieje wiele dobrych wyglądających sposoby przekształcenia krawędzie i wierzchołki przy redukcji, ale mój problem jest w jakiś sposób wyrażania DGD za pod względem DS za k . Dominujący zestaw wydawał się odpowiednim problemem do zredukowania, ale z tego powodu myślę, że może powinienem spróbować zmniejszyć problem, który nie ma takiego k ?kkk

użytkownik8879
źródło
Witamy! Próbowałem wyjaśnić problem; czy to tak miałeś na myśli? Przy okazji, możesz chcieć wybrać bardziej rozpoznawalną nazwę użytkownika niż „user8879”. :)
Raphael
Tak, dzięki, to jest rzeczywiście bardziej kompaktowa wersja.
user8879

Odpowiedzi:

9

Zamiast tego zmniejsz z NP-complete SET-COVER .

Niech z k N wystąpieniem zestawu osłon. Zdefiniuj instancję ( V , E , k ) DGD w następujący sposób: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

Łatwo zauważyć, że skonstruowana instancja DGD ma pozytywną odpowiedź wtedy i tylko wtedy, gdy dana instancja zestawu pokryw ma pozytywną odpowiedź. W szczególności wszystkie par ( y I , O i ) muszą być wybrane niezależnie, aby pokryć cały O I ; Następnie k o m par ( y i , o ) muszą obejmować wszystkie e j , a pierwsze elementy te wybrane są roztworu SET przykład pokrywy. Jeśli taki wybór nie jest możliwy, instancja SET-COVER również nie ma rozwiązania.m(si,oi)oikm(si,o)ej

Ponieważ konstrukcja jest możliwa w czasie wielomianowym, dowodzi to USTAWIENIA POKRYWY DGD.p


Jako przykład rozważmy przykładowy przykład okładki zestawu podany na Wikipedii , a mianowicie i zestawy S = { { 1 , 2 , 3 } , { 2 , 4 } , { 3 , 4 } , { 4 , 5 } } . To przekłada się na następujący wykres:{1,2,3,4,5}S={{1,2,3},{2,4},{3,4},{4,5}}

przykład
[ źródło ]

Raphael
źródło
1
Jest to prawie poprawne, ponieważ ja i B są rzeczywiście całkowicie objęte, ale O nie. Instancja set-cover jest instancją typu tak dla k = 2, ale w instancji DGD k = 2 pozostawia s2 i s3 odkryte. Myślę że można prawdopodobnie rozwiązać przez automatyczne dodawanie krawędzi z każdym węźle O z O .
user8879
(si,o)siS
Rozumiem teraz: utwórz dodatkowy węzeł w B dla każdego węzła w O , a następnie połącz go z odpowiadającym mu węzłem w O i o . W tym przykładzie otrzymujesz cztery dodatkowe ścieżki (s1 -> s1 '-> o itd.). Wreszcie po zwiększeniu k o cztery powinno być kompletne.
user8879
si