Twardość obliczeń etykiet Weisfeiler-Lehman

15

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 ) .do0do0(v)=1vV.(sol)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 w(ja+1)doja+1(v)doja-1(v)doja-1(u)uvdo1(v)=do1(w)vw 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.solH.solH.

Powszechnie wiadomo, że 1-dim WL działa poprawnie dla wszystkich drzew i wymaga tylko rund .O(logn)

Moje pytanie brzmi :

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

Shiva Kintali
źródło

Odpowiedzi:

11

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

Martin Grohe
źródło
3
Cześć Martin. Witamy w cstheory.
Kaveh
@Martin Jaka jest najbardziej znana twardość obliczania etykiet WL dla niewielkich grafów? Czy to wciąż P-complete? Próbuję udowodnić, że izomorfizm grafów dla mniej wolnych grafów znajduje się w AC1.
Shiva Kintali,