Твердость вычисления меток Вейсфайлера-Лемана

15

1-тусклый алгоритм Вейсфейлер-Леман (WL) широко известен как каноническая маркировка или алгоритм , цвета уточнения. Это работает следующим образом:

  • Начальная раскраска равномерна, C 0 ( v ) = 1 для всех вершин v V ( G ) V ( H ) .С0С0(v)знак равно1vВ(грамм)В(ЧАС)
  • В первом раунде цвет C i + 1 ( v ) определяется как пара, состоящая из предыдущего цвета C i - 1 ( v ) и мультимножества цветов C i - 1 ( u ) для все ты рядом с v . Например, C 1 ( v ) = C 1 ( w ) тогда и только тогда, когда v и w(я+1)Ся+1(v)Ся-1(v)Ся-1(U)UvС1(v)знак равноС1(вес)vвес иметь такую ​​же степень.
  • Чтобы сделать цветовую кодировку короткой, после каждого раунда цвета переименовываются.

Для двух неориентированных графов и H , если мультимножество цветов (или меток) вершин G отличается от мультимножества цветов вершин H , алгоритм сообщает, что графы не изоморфны; в противном случае он объявляет их изоморфными.граммЧАСграммЧАС

Хорошо известно, что 1-dim WL корректно работает для всех деревьев и требует только раундов.О(журналN)

Мой вопрос:

Какова сложность вычисления 1-мерных WL-меток дерева? Известна ли нижняя граница лучше, чем logspace?

Шива Кинтали
источник

Ответы:

11

Проблема определения того, имеют ли два графа эквивалентные метки, и, следовательно, также проблема вычисления канонической метки, являются PTIME-полными. Видеть

М. Грохе, Эквивалентность в логиках с конечными переменными полна за полиномиальное время. Combinatorica 19: 507-532, 1999. (Версия конференции в FOCS'96.)

Обратите внимание, что эквивалентность уточнения цвета соответствует эквивалентности в логике C ^ 2.

-Мартин

Мартин Гроэ
источник
3
Привет мартин Добро пожаловать в историю.
Каве
@Martin Какова самая известная сложность вычисления WL-меток неосновных графов? Это все еще P-полная? Я пытаюсь доказать, что граф Изоморфизм неосновных графов находится в AC1.
Шива Кинтали