Beim Lesen der Frage Beispiele, bei denen die Eindeutigkeit der Lösung das Auffinden erleichtert, kam mir eine neue (einfachere?) Frage in den Sinn: Tatsächlich wissen wir nicht, ob das Graph Isomorphism ( ) -Problem in .
Aber was passiert, wenn wir annehmen, dass sowohl als auch asymmetrisch sind (dh beide haben nur den trivialen (Identitäts-) Automorphismus)? Wird das Problem leichter (Polynomialzeit)?
Hinweis: Das Problem kann nicht schwerer sein als Graph Automorphism ( ), da es sich um eine schnelle Reduktion handelt: Verwenden Sie für . Wenn die Antwort ja lautet, sind die beiden Graphen isomorph (siehe auch Johannes Köbler, Uwe Schöning, Jacobo Torán: Der Graph-Isomorphismus ist für PP (401-411) niedrig .G A G 1 ∪ G 2
reference-request
graph-isomorphism
Marzio De Biasi
quelle
quelle
Antworten:
Auf Anfrage von Marzio De Biasi wandle ich meinen Kommentar in eine Antwort um.
Ein Graph ist asymmetrisch (einige Autoren bezeichnen ihn als starr), wenn er einen eindeutigen Automorphismus aufweist, dh die Identität. Wie von Chad Brewbacker hervorgehoben, sind die meisten Diagramme asymmetrisch. Die folgenden zwei Fragen sind jedoch offen:
1) Isomorphie asymmetrischer Graphen in P?
2) Kann der Isomorphismus allgemeiner Graphen auf den Isomorphismus asymmetrischer Graphen reduziert werden?
quelle