Finden eines maximalen azyklischen Unterturniers bei zwei azyklischen Unterturnieren

Bei einem Turnier bei dem und zwei azyklische Unterturniere von .S 1 S 2$T$$S_1$$S_2$$T$

Ist das folgende Problem NP-Complete: Finden eines maximalen azyklischen Subturniers , das Teilmenge von ?S 1 ∪ S $S$$S_1 \cup S_2$

Kann das gegebene Problem in Polynomzeit gelöst werden? Wenn nicht, geben Sie bitte die NP-Vollständigkeit an.

Indem als solches und nur die Eckpunkte von , kann ein maximales azyklisches Turnier, das zu , in Polynomzeit erhalten werden. Die Lösung so erhalten wird, kann nicht die gleiche wie die maximale azyklische Unter Turnier .S 2 S ' S 1 ∪ S 2 S '$S_1$$S_2$$S'$$S_1 \cup S_2$$S'$$S$

Der Polynomzeitalgorithmus basiert auf dem Komprimierungsschritt im iterativen Komprimierungsalgorithmus für den im Turnier festgelegten Rückkopplungsscheitelpunkt aus dem Papier

Ergebnisse der Traktabilität mit festen Parametern für Feedback-Set-Probleme bei Turnieren , Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier, Anke Truss, Journal of Discrete Algorithms 8 (2010) 76–86.

Wenn das Finden eines maximalen azyklischen Subturniers NP-vollständig ist, habe ich keine andere Wahl, als zu finden , also möchte ich wissen, ob das Finden von NP-vollständig ist oder nicht.S '$S$$S'$$S$

Betrachten Sie die Reduzierung von der Scheitelpunktabdeckung auf das obige Problem.

$G(V,E)$

$x_{i},y_{i},z_{i}$

$x_{1},y_{1},z_{1},x_{2},y_{2},z_{2}...x_{n},y_{n},z_{n}$$z_{j},x_{i}$$x_{i},y_{i}$$T_{1}$$z_{i}$$T_{2}$$T_{1}$$T_{2}$

Beispiel für den Bau

Betrachten Sie den Graphen G (V, E) mit der Scheitelpunktmenge {1,2,3} und den Kanten als (1,2) (2,3) -Konstruktion wie folgt

$x_{1},y{1},z{1},x_{2},y_{2},z_{2},x_{3},y_{3},z_{3}$

$x_{1}$

$y_{1}$$x_{1}$

$z_{1}$$x_{1},y_{1}$

$x_{1}$$x_{1},y_{1},z_{1}$

und wiederholen Sie den Vorgang, bis alle Kanten für das Turnier erstellt sind

$(x_{1},y_{2})$$(y_{2},x_{1})$

Ein Fall ist klar: Wenn G eine Scheitelpunktabdeckung der Größe k hat, dann hat T sicherlich ein fvs der Größe k

$i<j$$x_{i},z_{j}$$y_{i},z_{i},x_{k},y_{k},z_{k},x_{j},y_{j}$$i<k<j$$x_{i},z_{j}$

Bitte sehen und überprüfen.