Twardość obliczeń etykiet Weisfeiler-Lehman

1-wym algorytm Weisfeiler-Lehman (WL) jest powszechnie znany jako kanonicznej oznakowania lub algorytmu kolor rafinacji. Działa w następujący sposób:

• Początkowe zabarwienie jest jednolite, C 0 ( v ) = 1 dla wszystkich wierzchołków v ∈ V ( G ) ∪ V ( H ) .$C_0$$C_0(v) = 1$$v \in V (G) \cup V (H)$
• W rundzie, kolor C i + 1 ( v ) jest zdefiniowany jako para składająca się z poprzedzającego koloru C i - 1 ( v ) i multisetutu kolorów C i - 1 ( u ) dla wszystko u sąsiaduje z v . Na przykład C 1 ( v ) = C 1 ( w ) iff v i $(i + 1)$$C_{i+1}(v)$$C_{i−1}(v)$$C_{i−1}(u)$$u$$v$$C_1(v) = C_1(w)$$v$$w$ mieć ten sam stopień.
• Aby kodowanie kolorów było krótkie, po każdej rundzie zmienia się nazwy kolorów.

Biorąc pod uwagę dwa nieukierowane wykresy i H , jeśli multisetta kolorów (inaczej etykiety) wierzchołków G różni się od multisetta kolorów wierzchołków H , algorytm zgłasza, że ​​wykresy nie są izomorficzne; w przeciwnym razie deklaruje je jako izomorficzne.$G$$H$$G$$H$

Powszechnie wiadomo, że 1-dim WL działa poprawnie dla wszystkich drzew i wymaga tylko rund .$O({\log}n)$

Moje pytanie brzmi :

Jaka jest twardość obliczania 1-dimowych etykiet WL drzewa? Czy dolna granica jest lepsza niż logspace?

Problem decydowania o tym, czy dwa wykresy mają równoważne oznaczenia, a zatem także problem obliczania oznakowania kanonicznego, jest zakończony PTIME. Widzieć

M. Grohe, Równoważność w logice zmiennych skończonych jest pełna dla czasu wielomianowego. Combinatorica 19: 507-532, 1999. (Wersja konferencyjna w FOCS'96.)

Zauważ, że równoważność udoskonalenia kolorów odpowiada równoważności w logice C ^ 2.

-Jaskółka oknówka