Der Nachweis, dass die gerichtete Graphendiagnose NP-schwer ist

Ich habe eine Hausaufgabe, gegen die ich mich schon seit einiger Zeit mit dem Kopf geschlagen habe, und ich würde mich über Hinweise freuen. Es geht darum, ein bekanntes Problem auszuwählen, dessen NP-Vollständigkeit nachgewiesen ist, und eine Reduktion von diesem Problem auf das folgende Problem zu konstruieren, das ich DGD (Directed Graph Diagnostic) nennen werde.

Problem

Eine Instanz von DGD besteht aus Eckpunkten , gerichteten Kanten und einer positiven ganzen Zahl . Es gibt drei Arten von Eckpunkten: Ecken mit nur eingehenden Kanten , Ecken mit nur ausgehenden Kanten und Ecken mit beide ein- und ausgehenden Kanten . Lassen Sie außerdem .$(V,E,k)$$V = I \overset{.}{\cup} O \overset{.}{\cup} B$$E$$k$$I$$O$$B$$D=O\times I$

Das Problem ist nun, ob wir alle Knoten mit höchstens Elementen von abdecken können , d. H.$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$

wobei bedeutet, dass es einen gerichteten Weg von nach .$a\to^* b$$a$$b$

Ich denke, dass das Problem der dominierenden Menge das ist, von dem ich reduzieren sollte, da auch dies Bedenken hat, eine Teilmenge von Knoten mit einer anderen Teilmenge abzudecken. Ich habe versucht, eine DGD-Instanz zu erstellen, indem ich zuerst zwei Knoten für jedes Element der dominierenden Menge erstellt, alle Kanten kopiert und dann das der DGD-Instanz gleich dem der DS-Instanz gesetzt habe.$k$

Angenommen, eine einfache DS-Instanz mit den Knoten , 2 und 3 und den Kanten ( 1 , 2 ) und ( 1 , 3 ) . Dies ist eine Ja-Instanz mit k = 1 ; Die dominierende Menge besteht in diesem Fall nur aus Knoten 1 . Eine Reduzierung mit der gerade beschriebenen Methode würde zu einer DGD-Instanz mit zwei Pfaden ( 1 → 2 → 1 ′ ) und ( 1 → 3 → 1 ′$1$$2$$3$$(1,2)$$(1,3)$$k = 1$$1$$(1 \to 2 \to 1')$$(1 \to 3 \to 1')$;; Um alle Knoten abzudecken, würde nur ein Paar ausreichen. Dies hätte perfekt funktioniert, wenn nicht die dominierende Menge der DS-Instanz natürlich nicht in Polynomzeit bestimmt werden kann, was hier erforderlich ist.$(1, 1')$

Ich habe festgestellt, dass es viele gut aussehende Möglichkeiten gibt, die Kanten und Eckpunkte beim Reduzieren zu transformieren, aber mein Problem besteht darin, DGDs in Form von DSs k auszudrücken . Dominating Set schien ein passendes Problem zu sein, aber aus diesem Grund denke ich, dass ich vielleicht versuchen sollte, ein Problem zu reduzieren, das kein solches k hat ?$k$$k$$k$

Reduzieren Sie stattdessen von NP-komplett SET-COVER .

Sei mit k ∈ N eine Instanz der Mengenabdeckung. Definieren Sie eine Instanz ( V , E , k ′ ) von DGD wie folgt:$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$

Es ist leicht zu erkennen, dass die konstruierte DGD-Instanz genau dann eine positive Antwort hat, wenn die gegebene Set-Cover-Instanz eine positive Antwort hat. Insbesondere müssen alle Paare ( s i , o i ) ausgewählt werden, egal was passiert, um alle o i abzudecken ; dann müssen k der m Paare ( s i , o ) alle e j abdecken , und die ersten Komponenten der ausgewählten sind die Lösung der SET-COVER-Instanz. Wenn eine solche Auswahl nicht möglich ist, hat die SET-COVER-Instanz ebenfalls keine Lösung.$m$$(s_i,o_i)$$o_i$$k$$m$$(s_i,o)$$e_j$

Da die Konstruktion in Polynomzeit möglich ist, beweist dies SET-COVER DGD.$\leq_p$

Betrachten Sie als Beispiel die auf Wikipedia angegebene Beispielsatz-Deckungsinstanz , nämlich und setzen Sie S = { { 1 , 2 , 3 } , { 2 , 4 } , { 3 , 4 } , { 4 , 5 } } . Dies führt zu der folgenden Grafik:$\{1,2,3,4,5\}$$S=\{\{1,2,3\},\{2,4\},\{3,4\},\{4,5\}\}$

^{[ Quelle ]}