Dieses Problem ergab sich aus meinem letzten Blogeintrag . Angenommen, Sie erhalten eine TSP-Tour. Ist es co-NP-vollständig, um festzustellen, ob es sich um ein Minimum handelt?
Genauer ist das folgende Problem NP-vollständig:
Instanz: Gegeben ist ein vollständiger Graph G mit Kanten, die mit positiven ganzen Zahlen gewichtet sind, und ein einfacher Zyklus C, der alle Knoten von G aufruft.
Frage: Gibt es einen einfachen Zyklus D, der alle Knoten von G so aufruft, dass das Gesamtgewicht aller Kanten von D in G genau kleiner ist als das Gesamtgewicht aller Kanten von C in G?
Eine Skizze einer möglichen Reduktion zum Nachweis der NP-Vollständigkeit.
Informell geht es von einer modifizierten 3SAT-Formel aus, die zeigt, dass 3SAT ASP-vollständig ist (ein weiteres Lösungsproblem), und "folgt" der Standard-Reduktionskette 3SAT => DIRECTED HAMCYCLE => UNDIRECTED HAMCYCLE => TSP
Beginnt mit einer 3SAT Formel mit n Variablen x 1 , . . . x n und m caluses C 1 , . . . , C m ;φnx1,...xnmC1,...,Cm
Verwandle es in eine neue Formel füge eine neue Variable t hinzuφ′t ... ;
... und jede Klausel auf ( x(xi1∨xi2∨xi3);(xi1∨xi2∨xi3∨t)
Von bauen , um die Diamant Struktur Graph G = { V , E } verwendet , um den DIRECTED Hamilton - Operator CYCLE ist NP-Complete zu beweisen; Angenommen, jede Klausel C j entspricht dem Knoten N j in G ;φ′G={V,E}CjNjG
Modifiziere in Graph G ' = { V ' , E ' } und ersetze jeden Knoten u durch drei verbundene Knoten uGG′={V′,E′}u und modifiziere die Kanten gemäß der Standardreduktion, die verwendet wird, um die NP-Vollständigkeit von UNDIRECTED HAMILTONIAN CYCLE zu beweisen aus DIRECTED HAMILTONIAN CYCLE dh u 1 ist der Knoten, der für eingehende Kanten verwendet wird, u 3 ist der Knoten, der für ausgehende Kanten verwendet wird;u1,u2,u3u1u3
Konvertiere die UNREGELTE HAMILTONISCHE ZYKLUS-Instanz auf in eine TSP-Instanz T, in der alle Kanten von G ' das Gewicht w = 1 haben , mit Ausnahme der (eindeutigen) Kante in der Raute, die zu der "positiven" Zuordnung von t mit dem Gewicht w = geht 2 (roter Rand in der Abbildung unten); Schließlich haben die Kanten, die hinzugefügt werden, um G 'zu vervollständigen, das Gewicht w = 3 .G′TG′w=1tw = 2G′w = 3
Eindeutig die TSP - Instanz hat einen einfachen Zyklus , dass Besuche alle Knoten den die erfüllende Belegung von φ ' , in der t = t r u e (und diese Tour kann leicht in Polynomzeit konstruiert werden), aber es hat Gesamtgewicht | V ' | + 1 (da es verwendet die Kante , die entsprechen die Belegung t = t r u e , dass das Gewicht 2 hat). T hat einen weiteren einfachen Zyklus, der alle Knoten mit einem niedrigeren Gesamtgewicht | besucht V ' |Tφ′t = t r u e| V′| +1t = t r u eT| V′|wenn und nur wenn die Kante des Gewichts Das entspricht die Zuordnung t = t r u e nicht verwendet wird ; oder äquivalent, wenn und nur wenn es eine andere befriedigende Zuordnung von φ 'gibt, in der
t = f a l s e ist ; Dies kann aber genau dann zutreffen, wenn die ursprüngliche Formel φ erfüllt ist.2t = t r u eφ′t = fa l s eφ
Ich werde mehr darüber nachdenken und einen formellen Beweis schreiben (wenn es sich nicht als falsch herausstellt :-). Lassen Sie mich wissen, wenn Sie weitere Details zu einer oder mehreren der oben genannten Passagen benötigen.
Wie durch domotorp bemerkt ist eine interessante Folge , dass das folgende Problem NP-vollständig ist: ein Graph Gegeben und ein Hamilton - Pfad in ihm, hat G hat einen Hamilton - Zyklus?GG
Sie zeigen also im Wesentlichen, dass es NPc ist, zu entscheiden, ob es einen H-Zyklus hat, wenn ein Graph und ein H-Pfad darin gegeben sind, oder?
Domotorp
Sieht großartig aus. Vielen Dank für die Mühe beim Schreiben. Ein paar Änderungen betreffen direkt meine Frage: Die Kanten des Graphen sollten mit 1 gewichtet werden, mit Ausnahme der speziellen Kante, die mit 2 gewichtet werden sollte, und der Nicht-Kanten sollten mit 3 gewichtet werden.
Papadimitriou & Steiglitz (1977) haben NP-Vollständigkeit dieses Problems gezeigt.
quelle