NP-сложность проблемы разбиения графа?

Меня интересует эта проблема: учитывая неориентированный граф , существует ли разбиение на графы и такие что а изоморфны? $G(E, V)$ $G$ $G_1(E_1, V_1)$ $G_2(E_2, V_2)$ $G_1$ $G_2$

Здесь разбивается на два непересекающихся множества и . Множества и не обязательно не пересекаются. и $E$ $E_1$ $E_2$ $V_1$ $V_2$ $E1∪E2=E$ . $V1∪V2=V$

Эта проблема, по крайней мере, так же сложна, как и проблема изоморфизма графов. Я предполагаю, что это сложнее, чем Изоморфизм графов, но не NP-сложно.

Это проблема раздела -hard? $NP$

РЕДАКТИРОВАТЬ 3-3-2012: Опубликовано на MathOverflow .

РЕДАКТИРОВАТЬ 3-5-2012: Оказывается, ссылка в ответе Диего является одним из неопубликованных результатов. После некоторых раскопок я нашел ссылку на это в столбце «NP-Полнота: постоянное руководство» Дэвида ДЖОНСОНА (стр. 8). Я нашел другие статьи, в которых цитируется результат полноты NP Грэма и Робинсона как неопубликованный.

cc.complexity-theory graph-theory graph-isomorphism Мухаммед Аль-Туркистани
источник

Я думаю, что вы имеете в виду

, иначе это просто разрешимо в

и я упомянул это потому, что если

не пересекаются, объединение не может быть истинным в общем случае ( для краев).

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, GI, который, как известно, не находится в P, сводится к этой проблеме.

Мухаммед Аль-Туркистани

Кажется, что это связано с игрой, сохраняющей нарушение симметрии (см. Статьи Харари: «Симметричная стратегия в играх с предотвращением графов», «О длинах игр, сохраняющих симметрию на графиках») ... оба «слишком далеко» от моего уровня экспертиза :-(

Марцио Де Биаси

Я думаю , что можно предположить ,

V_{1} = V_{2} = V

$V_1=V_2=V$

Диего де Эстрада

Если

, существует a

поскольку

, Вы можете добавить

и отобразить их в изоморфизме, так как они изолированы в подграфах.

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$

Диего де Эстрада

NP-сложность проблемы разбиения графа?

Ответы: