Эффективный изоморфизм графов для аналогичных графовых запросов

Учитывая граф G1, G2 и G3, мы хотим выполнить тест F изоморфизма между G1 и G2, а также G1 и G3. Если G2 и G3 очень похожи, так что G3 формируется путем удаления одного узла и вставки одного узла из G2, и у нас есть результат F (G1, G2), можем ли мы вычислить F (G1, G3), не вычисляя его с нуля расширяя какие-либо существующие современные методы?

Например, если G2 образован узлами 2,3,4,5, а G3 образован узлами 3,4,5,6, можем ли мы использовать результат F (G1, G2) для вычисления F (G1, G3) более эффективно?

graph-theory graph-algorithms graph-isomorphism Эрик Хуан
источник

У меня нет аргументов в данный момент. Но мне кажется, что ваша проблема морально связана с гипотезой реконструкции ( en.wikipedia.org/wiki/Reconstruction_conjecture ).

Исинь Цао

Это простое полиномиальное сокращение времени, показывающее, что проблема является GI-полной : даже если вы знаете, что изоморфны, проверка того, является ли , созданный из и добавляющим узел, изоморфной , так же трудно, как изоморфизм графов сам (в худшем случае). $G_1, G_2$ $G_3$ $G_2$ $G_1$

Даны два графика построения $G = (V, E), G'= (V', E')$

$G_1 = ( V \cup V' \cup \{u\},\; E \cup E' \cup \{ (v_i,u) \mid v_i \in V \})$

т.е. объединение двух графов плюс дополнительный узел связанный со всеми вершинами $u$ $V$

выберите ; и ясно, что они изоморфны. $G_2 = G_1$

Теперь создайте удалив и добавив связанный со всеми вершинами : $G_3$ $u$ $u'$ $V'$

$G_3 = ( V \cup V' \cup \{u'\},\; E \cup E' \cup \{ (v_i',u') \mid v_i' \in V'\} )$

$G_1, G_3$ изоморфны тогда и только тогда когда изоморфны. $G, G'$

Марцио де Биаси
источник

Это хорошее сокращение! Тем не менее, я бы добавил, что одна только GI-полнота не обязательно означает, что нет никакого преимущества, только то, что в худшем случае их сложности связаны с полиномиальной зависимостью. В качестве другого примера, обратите внимание, что GI вершинного цвета также является GI-полным, но большинство известных мне алгоритмов все еще могут использовать цвета вершин полезным способом.

Джошуа

@ JoshuaGrochow: спасибо, я прояснил этот момент.

Марцио Де

@MarzioDeBiasi: спасибо за объяснения. Исходя из моего понимания ваших объяснений, мы не можем воспользоваться какими-либо преимуществами для вычисления F (G1, G3), зная F (G1, G2), если вершины, связанные с u и u ', различны (необязательно связаны со всеми вершинами V или V '), даже если мы знаем, что G и G' изоморфны. Это верно? В этом случае эта проблема так же сложна, как и сам изоморфизм графов?

Эрик Хуан

G_{1}, G_{2}

$G_1, G_2$

G_{3}

$G_3$

G_{2}

$G_2$

G_{1}, G_{3}

$G_1, G_3$

G_{3}

$G_3$

G_{1}, G_{3}

$G_1,G_3$

Марцио Де

Вы можете попробовать метод Weisfeiler-Lehman или его вариации, особенно если ваши исходные графы имеют такие структуры, как планарный, древовидный, интервальный граф или ограниченный график длины дерева, их размерность Weisfeiler-Lehman является небольшой константой, на этапе уточнения, я думаю, вы можете Воспользуйтесь преимуществами отношений между двумя графиками.

Рупей Сюй

Эффективный изоморфизм графов для аналогичных графовых запросов

Ответы: