Diagrammklassen, bei denen Probleme mit dem Hamilton-Zyklus und dem Hamilton-Pfad unterschiedlich komplex sind

Beim Durchsuchen des Informationssystems zu Graphenklassen und ihren Einschlüssen fand ich mehrere Graphenklassen, für die das Hamilton-Zyklus-Problem NP-vollständig ist, während die Komplexität von Hamilton-Pfad-Problemen NICHT bekannt ist. Einige dieser Klassen sind zweigeteilte Diagramme mit maximalem Grad 3, Diagramme mit maximalem Grad 3 und Diagramme mit zwei zusammenhängenden kubischen Ebenen. Auch dieses Phänomen gilt für Kreisgraphen und Dreiecksgittergraphen.

Gibt es eine Aktualisierung der Komplexität des Hamiltonschen Pfadproblems für diese Klassen? Gibt es eine Erklärung für dieses Phänomen?

BEARBEITEN : Ich fand in der Datenbank der Graphenklassen einen seltsamen Fall von soliden Gittergraphen, bei denen das Hamiltonsche Zyklusproblem in während das Hamiltonsche Pfadproblem von unbekannter Komplexität ist. $P$

cc.complexity-theory graph-theory Mohammad Al-Turkistany
quelle

Ich frage mich, ob es eine interessante Graphklasse gibt, für die HP in

, HC jedoch

-vollständig ist.

P

$P$

N P

$NP$

Mohammad Al-Turkistany

Gibt es im Allgemeinen eine Graphklasse, für die eines der Probleme (HC und HP)

-vollständig und das andere in

oder in

? Ich suche nach veröffentlichten Ergebnissen für HC- und HP-Probleme.

N P

$NP$

P

$P$

N P I

$NPI$

Mohammad Al-Turkistany

Für das, was es wert ist (nicht viel), haben der Hamilton-Pfad und der Hamilton-Zyklus unterschiedliche Komplexität bei Bäumen: Der Zyklus ist trivial, aber der Pfad erfordert einen linearen Scan, um festzustellen, ob es einen Scheitelpunkt gibt, dessen Grad mehr als zwei beträgt.

David Richerby

Es ist unwahrscheinlich, dass HP in

und HC

-komplett für jede Graphklasse ist, da es eine Cook-Reduktion von HC auf HP gibt, die höchstens

Aufrufe an HPs Orakel macht. Die eigentliche Frage ist, ob eine Karp-Reduktion vorliegt (

P

$P$

N P

$NP$

O (| E |)

$O(|E|)$

H C <_{P}^{m} H P

$HC<_P^m HP$

Mohammad Al-Turkistany

Antworten:

Das Hamiltonsche Pfadproblem auf Gittergraphen mit maximalem Grad 3 ist NP-vollständig. Der Beweis ist in CH Papadimitriou und UV Vazirani, Über zwei geometrische Probleme im Zusammenhang mit dem Problem des Handelsreisenden, Journal of Algorithms, Band 5, Ausgabe 2, Juni 1984, Seiten 231–246 (Satz 2).

Marzio De Biasi
quelle

Vielen Dank, Marzio. Verwenden sie die gleiche Definition, die in der Datenbank für Rasterdiagramme verwendet wird? (da es sich in der Literatur um unterschiedliche Definitionen handelt)

Mohammad Al-Turkistany

Ein Gittergraph ist ein endlicher, knoteninduzierter Teilgraph von

, dem unendlichen Graphen, dessen Scheitelpunktmenge aus allen Punkten der Ebene mit ganzzahligen Koordinaten besteht und in dem zwei Scheitelpunkte genau dann verbunden sind, wenn der euklidische Abstand zwischen ihnen 1 beträgt; so kann ein Gittergraph "Löcher" haben und der Satz ist für (auf) Gittergraphen bewiesen, in denen Eckpunkte den Maximalgrad 3 haben.

G^{\infty}

$G^\infty$

Marzio De Biasi

Danke Marzio, also für diese Klasse haben HC und HP die gleiche Komplexität.

Mohammad Al-Turkistany

@ MohammadAl-Turkistany: Ein weiterer Hinweis: Gittergraphen (und Gittergraphen mit maximalem Grad 3) sind ebenfalls zweigeteilt, sodass HP auch für zweigeteilte Graphen mit maximalem Grad 3 NP-vollständig sein sollte.

Marzio De Biasi

Das Informationssystem über Diagrammklassen und ihre Einschlüsse wurde aktualisiert. Nun wird angegeben, dass das Hamiltonsche Zyklusproblem und das Hamiltonsche Pfadproblem auf 2-zusammenhängenden kubischen planaren Graphen NP-vollständig sind.

Die Rechenkomplexität von HC- und HP-Problemen ist jedoch für ein Problem unbekannt und für das andere NP-vollständig in Kreisdiagrammen , Dreiecksgitterdiagrammen und Vollgitterdiagrammen aufgeführt .

Mohammad Al-Turkistany
quelle

Sie sagen "... die Komplexität von HC- und HP-Problemen ist immer noch unterschiedlich ..."; vielleicht ist es besser zu sagen, dass "für diese Klassen von Graphen HC NPC ist, aber HP hat noch unbekannte Komplexität"

Marzio De Biasi

@ MarzioDeBiasi Vielen Dank für Ihren wertvollen Kommentar. Ich habe Ihren Vorschlag bearbeitet.

Mohammad Al-Turkistany

Vermisse ich etwas HC ist in festen Gittergraphen polynomiell zeitlösbar. ieeexplore.ieee.org/document/646138

Saeed