Dureza de la computación de las etiquetas Weisfeiler-Lehman

El algoritmo Weisfeiler-Lehman 1-dim (WL) se conoce comúnmente como etiquetado canónico o algoritmo de refinamiento de color. Funciona de la siguiente manera:

• La coloración inicial es uniforme, C 0 ( v ) = 1 para todos los vértices v ∈ V ( G ) ∪ V ( H ) .$C_0$$C_0(v) = 1$$v \in V (G) \cup V (H)$
• En la ronda st, el color C i + 1 ( v ) se define como un par que consiste en el color anterior C i - 1 ( v ) y el conjunto múltiple de colores C i - 1 ( u ) para todos u adyacentes a v . Por ejemplo, C 1 ( v ) = C 1 ( w ) si v y $(i + 1)$$C_{i+1}(v)$$C_{i−1}(v)$$C_{i−1}(u)$$u$$v$$C_1(v) = C_1(w)$$v$$w$ tener el mismo grado
• Para mantener corta la codificación de color, después de cada ronda se renombran los colores.

Dados dos gráficos no dirigidos y H , si el conjunto múltiple de colores (también conocido como etiquetas) de los vértices de G es distinto del conjunto múltiple de colores de los vértices de H , el algoritmo informa que los gráficos no son isomórficos; de lo contrario, los declara isomórficos.$G$$H$$G$$H$

Es bien sabido que el WL de 1 dim funciona correctamente para todos los árboles y solo requiere rondas .$O({\log}n)$

Mi pregunta es :

¿Cuál es la dureza de calcular etiquetas WL de 1 dim de un árbol? ¿Es mejor un límite inferior que el espacio de registro conocido?

El problema de decidir si dos gráficos tienen etiquetados equivalentes y, por lo tanto, también el problema de calcular el etiquetado canónico es PTIME completo. Ver

M. Grohe, Equivalencia en lógicas de variables finitas está completa para el tiempo polinomial. Combinatorica 19: 507-532, 1999. (Versión de conferencia en FOCS'96.)

Tenga en cuenta que la equivalencia de refinamiento de color corresponde a la equivalencia en la lógica C ^ 2.

-Martín