Udowodnienie, że diagnoza ukierunkowanego wykresu jest trudna do przeprowadzenia

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 \overset{.}{\cup} O \overset{.}{\cup} B$$E$$k$$I$$O$$B$$D=O\times I$

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

$\qquad \displaystyle \exists\,S\subseteq D, |S|\leq k.\ \forall\, v\in V.\ \exists\,(v_1,v_2) \in S.\ v_1 \to^* v \to^* v_2$

gdzie oznacza, że ​​istnieje ukierunkowana ścieżka od a do b .$a\to^* b$$a$$b$

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 ′$1$$2$$3$$(1,2)$$(1,3)$$k = 1$$1$$(1 \to 2 \to 1')$$(1 \to 3 \to 1')$; 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 ?$k$$k$$k$

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:$S_1,\dots,S_m \subseteq\{1,\dots,n\}$$k\in\mathbb{N}$$(V,E,k')$

• $V= \{s_1,\dots,s_m,o_1,\dots,o_m,e_1,\dots,e_n,o\}$
• $E= \{(s_i,o_i) \mid i = 1,\dots,n \} \cup \{(s_i,e_j)\mid j \in S_i\} \cup\{(e_j,o)\mid j=1,\dots,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$$(s_i,o_i)$$o_i$$k$$m$$(s_i,o)$$e_j$

Ponieważ konstrukcja jest możliwa w czasie wielomianowym, dowodzi to USTAWIENIA POKRYWY DGD.$\leq_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\}\}$

^{[ źródło ]}