Dureza da computação de etiquetas Weisfeiler-Lehman

15

O algoritmo Weisfeiler-Lehman (WL) 1-dim é comumente conhecido como rotulagem canônica ou algoritmo de refinamento de cores. Funciona da seguinte maneira:

  • A coloração inicial é uniforme, C 0 ( v ) = 1 para todos os vértices v V ( G ) V ( H ) .C0C0(v)=1vV(G)V(H)
  • Na rodada , a cor C i + 1 ( v ) é definida como um par que consiste na cor anterior C i - 1 ( v ) e no conjunto múltiplo de cores para todos os(i+1)Ci+1(v)Ci1(v)Ci1(u)u adjacentes a . Por exemplo, sse v e w têm o mesmo grau.vC1(v)=C1(w)vw
  • Para manter a codificação de cores curta, após cada rodada, as cores são renomeadas.

Dado dois gráficos não direcionados e H , se o multiset de cores (também conhecido como rótulos) dos vértices de G for distinto do multiset de cores dos vértices de H , o algoritmo relata que os gráficos não são isomórficos; caso contrário, declara-os isomórficos.GHGH

É sabido que o WL 1-dim funciona corretamente para todas as árvores e requer apenas rodadas .O(registron)

Minha pergunta é :

Qual é a dureza de calcular etiquetas WL 1-dim de uma árvore? Um limite inferior é melhor que o espaço de registro conhecido?

Shiva Kintali
fonte

Respostas:

11

O problema de decidir se dois gráficos têm rótulos equivalentes e, portanto, também o problema de calcular o rótulo canônico são PTIME completos. Vejo

M. Grohe, A equivalência na lógica de variáveis ​​finitas é completa por tempo polinomial. Combinatorica 19: 507-532, 1999. (Versão da conferência em FOCS'96.)

Observe que a equivalência de refinamento de cor corresponde à equivalência na lógica C ^ 2.

-Martin

Martin Grohe
fonte
3
Olá Martin. Bem-vindo à história.
Kaveh
@ Martin Qual é a dureza mais conhecida da computação dos rótulos WL de gráficos menores livres? Ainda está P-completo? Estou tentando provar que o isomorfismo de grafos de grafos menores-livres está em AC1.
21412 Shiva Kintali