Twardość NP problemu podziału grafu?

Jestem zainteresowany tym problemem: Biorąc pod uwagę undirected wykres , Czy istnieje podział na wykresach i takie, że i są izomorficzne? $G(E, V)$ $G$ $G_1(E_1, V_1)$ $G_2(E_2, V_2)$ $G_1$ $G_2$

Tutaj jest podzielony na dwa rozłączne zestawy i . Zestawy i niekoniecznie są rozłączne. i . $E$ $E_1$ $E_2$ $V_1$ $V_2$ $E1∪E2=E$ $V1∪V2=V$

Ten problem jest co najmniej tak trudny jak problem z izomorfizmem grafów. Wydaje mi się, że jest trudniejszy niż Graph Isomorphism, ale nie NP-trudny.

Czy ten problem z partycją twardy? $NP$

EDYCJA 3-3-2012: Wysłano na MathOverflow .

EDYCJA 3-5-2012: Okazuje się, że odniesienie w odpowiedzi Diego jest jednym z niepublikowanych wyników. Po kilku kopaniach znalazłem odniesienie do niego w kolumnie NP-Completeness Column: The On Guide autorstwa Davida JOHNSONA (strona 8). Znalazłem inne prace, które cytują wynik zupełności NP Grahama i Robinsona jako niepublikowane.

cc.complexity-theory graph-theory graph-isomorphism Mohammad Al-Turkistany
źródło

Myślę, że masz na myśli

, w przeciwnym razie jest to po prostu możliwe do rozwiązania w

i wspomniałem o tym, ponieważ jeśli

są rozłączne, unia nie może być prawdziwa ( dla krawędzi).

E_{1} \cup E_{2} = E

$E_1\cup E_2 = E$

V_{1} \cup V_{2} = V

$V_1\cup V_2 = V$

P

$P$

V_{1}

$V_1$

V_{2}

$V_2$

Saeed

@ Saeed, GI, o którym nie wiadomo, że jest w P, można zredukować do tego problemu.

Mohammad Al-Turkistany

Wydaje się, że jest to związane z grą zachowującą łamanie symetrii (patrz artykuły Harary'ego: „Strategia symetryczna w grach unikania wykresów”, „O długościach łamania i zabezpieczania symetrii na wykresach”) ... oba „za daleko” od mojego poziomu wiedza specjalistyczna :-(

Marzio De Biasi

Myślę, że można założyć,

V_{1} = V_{2} = V

$V_1=V_2=V$

Diego de Estrada

Jeśli

, istnieje

. Możesz dodać

i zmapować je w izomorfizmie, ponieważ są one izolowane w podgrafach.

v \in V_{1} - V_{2}

$v\in V_1-V_2$

w \in V_{2} - V_{1}

$w\in V_2-V_1$

| V_{1} | = | V_{2} |

$|V_1|=|V_2|$

v

$v$

V_{2}

$V_2$

w

$w$

V_{1}

$V_1$

Diego de Estrada

Twardość NP problemu podziału grafu?

Odpowiedzi: