Hat jemand einen Polynomalgorithmus für den Isomorphismus des Hamilton-Zyklus gefunden?

Hat jemand, wie der Titel sagt, einen Polynomzeitalgorithmus gefunden, um zu überprüfen, ob zwei Graphen mit einem Hamilton-Zyklus isomorph sind? Ist dieses Problem NP-vollständig?

complexity-theory graph-theory time-complexity Leo Sanchez
quelle

Auf jeden Fall Nein, zumindest für gerichtete Diagramme. Weil der beste Algorithmus für Turnierisomorphismus . Und Turniere sind die Grafiken mit Hamilton-Pfaden. Siehe uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.190/Mitarbeiter/…

O (n^{\log n})

$O(n^{\log{n}})$

rizwanhudda

@ Rizwanhudda Vielen Dank. Darf ich Ihnen noch eine Frage stellen? Ist dieses Problem NP-vollständig?

Leo Sanchez

Und was ist mit Zyklen?

Leo Sanchez

Ich kenne keine Ergebnisse über den Hamilton-Zyklus. Dieses Problem kann jedoch nicht NP-vollständig sein, da es sich um einen Sonderfall des Graphisomorphismus handelt. Und es ist nicht bekannt, dass der Graphisomorphismus NP-vollständig ist.

Rizwanhudda

Wie Rizwanhudda sagte, ist dieses Problem ein Sonderfall des Graphisomorphismusproblems und daher ist nicht bekannt, dass es NP-vollständig ist. Wir können aus diesem Grund nicht sagen, dass dieses Problem nicht NP-vollständig sein kann, da das Graphisomorphismus-Problem möglicherweise NP-vollständig ist. Viele Komplexitätstheoretiker glauben jedoch, dass das Graph-Isomorphismus-Problem nicht NP-vollständig ist (und daher glauben sie, dass Ihr Problem auch nicht NP-vollständig ist), da die NP-Vollständigkeit des Graph-Isomorphismus-Problems der Vermutung widersprechen würde, die als „the Die Polynomhierarchie bricht nicht zusammen. “

Tsuyoshi Ito

Antworten:

Was folgt, stammt aus Tsuyoshi Itos Kommentar.

Wie Rizwanhudda sagte , ist dieses Problem ein Sonderfall des Graphisomorphismusproblems und daher ist nicht bekannt, dass es NP-vollständig ist. Wir können aus diesem Grund nicht sagen, dass dieses Problem nicht NP-vollständig sein kann, da das Graphisomorphismus-Problem möglicherweise NP-vollständig ist. Viele Komplexitätstheoretiker glauben jedoch, dass das Graph-Isomorphismus-Problem nicht NP-vollständig ist (und daher glauben sie, dass Ihr Problem auch nicht NP-vollständig ist), da die NP-Vollständigkeit des Graph-Isomorphismus-Problems der Vermutung widersprechen würde, die als „the Die Polynomhierarchie bricht nicht zusammen. “

Raphael
quelle

Bitte fühlen Sie sich nicht verpflichtet, eine Antwort als Community-Wiki zu markieren, nur weil es sich um eine Kopie meines Kommentars handelt, falls Sie oder jemand anderes dies wünscht.

Tsuyoshi Ito

Nun, ich denke, diese Antwort sollte jetzt aktualisiert werden, da GI als quasi-polynomisch bekannt ist.

Guillermo Angeris

Wie von Kaveh vorgeschlagen, ist dies möglicherweise eine Reduktion, die beweisen kann, dass die Klasse der Graphen mit einem Hamilton-Zyklus GI-vollständig ist.

Bei zwei Graphen und ist , erweitern Sie mit einem vollständigen Graphen , der seine Knoten paarweise kennzeichnet ; dann für jeden ScheitelpunktAddiere zwei Kanten und , die mit . Erweitern Sie auf die gleiche Weise. $G_1 = (V_1,E_1)$ $G_2 = (V_2,E_2)$ $|V_1| = |V_2|=n$ $G_1$ $K_{2n}$ $(a_i, b_i)$ $u_i \in |V_1|$ $(a_i,u_i)$ $(u_i,b_i)$ $G_1$ $K_{2n}$ $G_2$

Konstruktionsbedingt haben die beiden erweiterten Graphen und einen Hamilton-Zyklus und die ursprünglichen Graphen sind isomorph, wenn und isomorph sind. Informell: In und die hinzugefügten Knoten den ursprünglichen Isomorphismus nicht "stören", da ihr Grad größer als $G'_1$ $G'_2$ $(a_1 u_1 b_1 a_2 u_2 b_2 ... a_n u_n b_n a_1)$ $G'_1$ $G'_2$ $G'_1$ $G'_2$ $\max(\text{deg}(u_i))$

Vor
quelle