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

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

• Начальная раскраска равномерна, C 0 ( v ) = 1 для всех вершин v ∈ V ( G ) ∪ V ( H ) .$C_0$$C_0(v) = 1$$v \in V (G) \cup V (H)$
• В первом раунде цвет C i + 1 ( v ) определяется как пара, состоящая из предыдущего цвета C i - 1 ( v ) и мультимножества цветов C i - 1 ( u ) для все ты рядом с v . Например, C 1 ( v ) = C 1 ( w ) тогда и только тогда, когда v и $(i + 1)$$C_{i+1}(v)$$C_{i−1}(v)$$C_{i−1}(u)$$u$$v$$C_1(v) = C_1(w)$$v$$w$ иметь такую ​​же степень.
• Чтобы сделать цветовую кодировку короткой, после каждого раунда цвета переименовываются.

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

Хорошо известно, что 1-dim WL корректно работает для всех деревьев и требует только раундов.$O({\log}n)$

Мой вопрос:

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

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

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

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

-Мартин