Rechenhärte von Weisfeiler-Lehman-Etiketten

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 ) .$C_0$$C_0(v) = 1$$v \in V (G) \cup 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 $(i + 1)$$C_{i+1}(v)$$C_{i−1}(v)$$C_{i−1}(u)$$u$$v$$C_1(v) = C_1(w)$$v$$w$ 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.$G$$H$$G$$H$

Es ist bekannt, dass der 1-dim WL für alle Bäume korrekt funktioniert und nur Runden benötigt.$O({\log}n)$

Meine Frage ist :

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

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