Klassen von Graphen mit einfachem Hamilton-Zyklus, aber NP-hartem TSP

13

Das Hamilton'sche Zyklusproblem (HC) besteht darin, einen Zyklus zu finden, der alle Eckpunkte in einem gegebenen ungerichteten Graphen durchläuft. Das Travelling Salesman Problem (TSP) besteht darin, einen Zyklus zu finden, der alle Eckpunkte in einem bestimmten kantengewichteten Diagramm durchläuft und die durch die Summe der Gewichte der Kanten im Zyklus gemessene Gesamtentfernung minimiert. HC ist ein Sonderfall von TSP, und beide sind bekanntermaßen NP-vollständig [Garey & Johnson]. (Weitere Details und Varianten dieser Probleme finden Sie unter den obigen Links.)

Gibt es untersuchte Klassen von Graphen, für die das Hamilton-Zyklus-Problem über einen nicht-trivialen Algorithmus in Polynomzeit lösbar ist, das Travelling Salesman-Problem jedoch NP-schwer ist?

Nicht trivial ist der Ausschluss von Klassen wie der Klasse vollständiger Graphen, bei denen das Vorhandensein eines Hamilton-Zyklus garantiert und leicht zu finden ist, oder allgemein von Klassen von Graphen, bei denen das Vorhandensein eines HC immer garantiert ist.

cc.complexity-theory np-hardness hamiltonian-paths tsp graph-classes Standa Zivny
quelle

Antworten:

20

Cographs sind nicht immer Hamiltonianer, haben polynomielle Zeittests für Hamiltonicity und sind NP-schwer zu lösen für das Problem des Handlungsreisenden.

Allgemeiner kann das Hamilton-Zyklus-Problem in Polynomzeit (aber nicht mit festen Parametern) auf Graphen mit begrenzter Cliquenbreite gelöst werden ; siehe z. B. Fomin et al., "Clique-width: on the price of generality", SODA'09. Da diese Diagrammfamilien jedoch auch die vollständigen Diagramme enthalten, ist der TSP mit diesen Diagrammen nicht zufrieden.

David Eppstein
quelle
Ich bin neugierig auf deine letzte Aussage. Liegt das daran, dass die TSP-Tour die Cliquen effektiv identifiziert, indem alle Cliquenscheitelpunkte in der Tour zusammenhängend sind?
Suresh Venkat
1
Nein, ich meine einfach, dass TSP selbst in einem vollständigen Diagramm hart ist, und vollständige Diagramme gehören zu den Diagrammen mit begrenzter Cliquenbreite. Komplette Graphen bieten selbst keine gute Antwort auf die Frage, da Hamiltonicity für sie trivial ist, aber Superklassen der Cliquen (wie die Cographs) können nichttriviale, sondern polynomiale Hamiltonicity-Tests haben.
David Eppstein
11

Wie wäre es mit vollständigen Grafiken ? Da TSP in vollständigen Diagrammen immer auf eine Instanz reduziert werden kann (durch Hinzufügen geeigneter Abstände zwischen Nichtkanten), ist es immer noch schwierig, TSP in vollständigen Diagrammen zu lösen. Alle vollständigen Graphen sind Hamilton-Graphen.

Hsien-Chih Chang 張顯 張顯
quelle
Ja, natürlich danke! Vergaß, vollständige Graphen auszuschließen, und im Übrigen alle Klassen von Graphen, in denen HC trivial lösbar ist.
Standa Zivny
3
@Standa Zivny: Ich bin nicht sicher, ob Sie die Frage bearbeiten werden oder nicht, aber wenn Sie "alle Klassen von Diagrammen ausschließen möchten, in denen HC trivial lösbar ist", sollten Sie die Frage bearbeiten. Ich bezweifle jedoch, dass es möglich ist, die Unterscheidung zwischen dem Fall, in dem HC "leicht" gelöst werden kann, und dem Fall, in dem HC "trivial" gelöst werden kann, zu formulieren.
Tsuyoshi Ito
@ Tsuyoshi Ito: Ein guter Punkt, ich habe die Frage bearbeitet.
Standa Zivny
@StandaZivny - Nicht alle Diagramme, die für HC trivial sind, sind für TSP schwierig, z. B. Pfaddiagramme.
RB
3

Es gibt viele unendliche Klassen von Graphen, von denen bekannt ist, dass sie Hamilton-Schaltkreise haben. Zwei besonders interessante Klassen sind die n-Würfel und die Halin-Graphen. Eine Möglichkeit, an die Halin-Graphen zu denken, besteht darin, einen Baum mit mindestens 3 Scheitelpunkten und ohne zwei Valenzscheitelpunkte in die Ebene einzubetten und dann einen einfachen Kreislauf durch die einwertigen Scheitelpunkte des Baums zu führen.

http://en.wikipedia.org/wiki/Halin_graph

Es ist bekannt, dass diese Graphen einen HC haben, und tatsächlich sind sie entweder panzyklisch (Schaltkreise aller Längen) oder es fehlt genau eine Schaltkreislänge, die eine gerade Länge haben muss.

Joseph Malkevitch
quelle