Rechenhärte von Weisfeiler-Lehman-Etiketten

15

Der 1-dim Weisfeiler-Lehman-Algorithmus (WL) ist allgemein als kanonischer Markierungs- oder Farbverfeinerungsalgorithmus bekannt. Es funktioniert wie folgt:

  • Die anfängliche Färbung ist einheitlich, C 0 ( v ) = 1 für alle Eckpunkte v V ( G ) V ( H ) .C0C0(v)=1vV(G)V(H)
  • In der -ten Runde wird die Farbe C i + 1 ( v ) als ein Paar definiert, das aus der vorhergehenden Farbe C i - 1 ( v ) und dem Mehrfachsatz der Farben C i - 1 ( u ) für besteht alle u neben v . Zum Beispiel ist C 1 ( v ) = C 1 ( w ) iff v und w(ich+1)Cich+1(v)Cich-1(v)Cich-1(u)uvC1(v)=C1(w)vw haben den gleichen grad.
  • Um die Farbkodierung kurz zu halten, werden die Farben nach jeder Runde umbenannt.

Bei zwei ungerichteten Graphen und H meldet der Algorithmus, dass die Graphen nicht isomorph sind , wenn die Mehrfachmenge von Farben (auch als Beschriftungen bezeichnet) der Scheitelpunkte von G von der Mehrfachmenge von Farben der Scheitelpunkte von H verschieden ist. Andernfalls werden sie als isomorph deklariert.GHGH

Es ist bekannt, dass der 1-dim WL für alle Bäume korrekt funktioniert und nur Runden benötigt.Ö(Logn)

Meine Frage ist :

Wie hart ist es, 1-dim WL-Etiketten eines Baums zu berechnen? Ist eine Untergrenze besser als ein Logspace bekannt?

Shiva Kintali
quelle

Antworten:

11

Das Problem der Entscheidung, ob zwei Graphen äquivalente Beschriftungen aufweisen, und damit auch das Problem der Berechnung der kanonischen Beschriftung sind PTIME-vollständig. Sehen

M. Grohe, Die Äquivalenz in der endlichen Variablenlogik ist für die Polynomzeit vollständig. Combinatorica 19: 507-532, 1999. (Konferenzversion in FOCS'96.)

Man beachte, dass die Farbverfeinerungsäquivalenz der Äquivalenz in der Logik C ^ 2 entspricht.

-Martin

Martin Grohe
quelle
3
Hallo Martin. Willkommen bei cstheory.
Kaveh
@Martin Was ist die bekannteste Härte bei der Berechnung der WL-Bezeichnungen von Diagrammen ohne Nebeneffekte? Ist es noch P-vollständig? Ich versuche zu beweisen, dass der Graph-Isomorphismus von minderwertigen Graphen in AC1 vorliegt.
Shiva Kintali