NP-Härte eines Graphpartitionsproblems?

16

Dieses Problem interessiert mich: Gibt es bei einem ungerichteten Graphen eine Aufteilung von G in Graphen G 1 ( E 1 , V 1 ) und G 2 ( E 2 , V 2 ), so dass G 1 und G 2 sind isomorph?G(E,V)GG1(E1,V1)G2(E2,V2)G1G2

Hier ist in zwei disjunkte Mengen E 1 und E 2 unterteilt . Die Mengen V 1 und V 2 sind nicht notwendigerweise disjunkt. E 1 E 2 = E und V 1 V 2 = V .EE1E2V1V2E1E2=EV1V2=V

Dieses Problem ist mindestens so schwer wie das Graph Isomorphism Problem. Ich denke, es ist schwieriger als der Graph-Isomorphismus, aber nicht NP-hart.

Ist dieses Partitionsproblem -hart?NP

EDIT 3-3-2012: Veröffentlicht am MathOverflow .

EDIT 3-5-2012: Es stellt sich heraus, dass der Verweis in Diego's Antwort eines der unveröffentlichten Ergebnisse ist. Nach einigem Graben fand ich einen Verweis darauf in der NP-Vollständigkeitssäule: Ein fortlaufender Leitfaden von David JOHNSON (Seite 8). Ich fand andere Artikel, in denen das Ergebnis der NP-Vollständigkeit von Graham und Robinson als unveröffentlicht zitiert wurde.

Mohammad Al-Turkistany
quelle
1
Ich denke du meinst und V 1V 2 = V , sonst ist es einfach lösbar in P und ich erwähnte dies, weil, wenn V 1 und V 2 disjunkt sind, Vereinigung im Allgemeinen nicht wahr sein kann ( für Kanten). E1E2=EV1V2=VPV1V2
Saeed
@ Saeed, GI, von dem nicht bekannt ist, dass es sich um P handelt, lässt sich auf dieses Problem reduzieren.
Mohammad Al-Turkistany
1
Scheint im Zusammenhang mit dem symmetriebrechenden Erhaltungsspiel zu stehen (siehe Hararys Artikel: "Eine symmetrische Strategie in Graphenvermeidungsspielen", "Auf den Längen von symmetriebrechenden Erhaltungsspielen in Graphen") ... beide "zu weit" von meinem Level von Expertise :-(
Marzio De Biasi
1
Ich denke, Sie können annehmen . V1=V2=V
Diego de Estrada
1
Wenn , existiert ein w V 2 - V 1 seit | V 1 | = | V 2 | . Sie können v zu V 2 und w zu V 1 hinzufügen und sie im Isomorphismus abbilden, da sie in den Untergraphen isoliert sind. vV1-V2wV2-V1|V1|=|V2|vV2wV1
Diego de Estrada

Antworten:

7

Ich habe festgestellt, dass dieses Problem NP-schwer ist, sogar auf Bäume beschränkt. Die Referenz ist Graham und Robinson, "Isomorphe Faktorisierungen IX: sogar Bäume", aber ich konnte es nicht bekommen.

Diego de Estrada
quelle