Going deep and going wide: Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth

Resumo Técnico

Título: Going deep and going wide: Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth
Autores: Isolde Adler, Eva Fluck, Tim Seppelt, Gian Luca Spitzer
Data: 2 de abril de 2026 (versão arXiv)

1. Problema e Contexto

O artigo investiga o poder expressivo da Lógica de Contagem de Primeira Ordem (First-Order Logic with Counting Quantifiers), especificamente o fragmento $C^k_q$, que combina uma restrição de k variáveis e uma profundidade de quantificador q.

Historicamente, a equivalência lógica em fragmentos de contagem foi caracterizada por indistinguibilidade de homomorfismos sobre classes de grafos específicas:

• $C^k$ (k variáveis) corresponde à indistinguibilidade sobre grafos de largura de árvore (treewidth) $\le k-1$ ($TW_{k-1}$).
• $C_q$ (profundidade q) corresponde à indistinguibilidade sobre grafos de profundidade de árvore (treedepth) $\le q$ ($TD_q$).

A questão central deste trabalho é: a equivalência no fragmento interseção $C^k_q = C^k \cap C_q$ é caracterizada pela indistinguibilidade sobre a interseção das classes de grafos $TW_{k-1} \cap TD_q$? Ou seja, dois grafos satisfazem as mesmas sentenças em $C^k_q$ se e somente se eles são indistinguíveis por homomorfismos sobre grafos que possuem simultaneamente largura de árvore $\le k-1$ e profundidade de árvore $\le q$?

Intuitivamente, esperava-se que a resposta fosse afirmativa. O objetivo do artigo é provar que essa intuição está errada sob certas condições.

2. Metodologia

Os autores utilizam uma abordagem combinatória e estrutural baseada em três pilares principais:

1. Reprovação Elementar: Eles reprovam um resultado recente de Dawar, Jakl e Reggio (2021) que caracteriza $C^k_q$ através de uma nova classe de grafos, $T^k_q$ (grafos que admitem uma "cobertura de floresta com k pedras" de profundidade q), utilizando técnicas elementares inspiradas em Dvořák, em vez de comonads categóricos.
2. Análise de Classes de Grafos ($T^k_q$ vs. $TW_{k-1} \cap TD_q$):
   • Introduzem três definições equivalentes para a classe $T^k_q$: coberturas de floresta com pedras, decomposições de árvore com restrições de largura e profundidade, e árvores de construção (construction trees).
   • Demonstram que, quando $q$ é suficientemente maior que $k$, a classe $T^k_q$ é um subconjunto próprio de $TW_{k-1} \cap TD_q$. Ou seja, existem grafos que têm largura de árvore pequena e profundidade de árvore pequena, mas não possuem uma decomposição que satisfaça ambas as restrições simultaneamente de forma "acoplada".
3. Jogos de Busca (Cops-and-Robber):
   • Caracterizam $T^k_q$ através de um jogo de "Polícia e Ladrão" (Cops-and-Robber) com $k$ policiais e $q$ rodadas.
   • Contribuição Técnica Crucial: Provar que o jogo pode ser restrito à versão monótona (onde a área limpa nunca precisa ser rebuscada) sem perda de poder de captura. Para isso, introduzem o conceito de pré-decomposição de árvore (pre-tree-decomposition), inspirado em decomposições de matroides. Eles desenvolvem um procedimento de "limpeza" (cleaning up) em largura (BFS) que transforma uma estratégia vencedora não-monótona em uma pré-decomposição exata, e subsequentemente em uma decomposição de árvore válida, controlando a largura e a profundidade.
4. Fechamento de Indistinguibilidade (Homomorphism Distinguishing Closed):
   • Para separar semanticamente as relações de equivalência, eles provam que as classes $T^k_q$ e $TD_q$ são fechadas sob distinção de homomorfismos. Isso significa que se dois grafos são indistinguíveis sobre uma classe $F$, e $F$ é fechada, então eles são indistinguíveis sobre qualquer grafo em $F$.
   • Eles confirmam uma conjectura de Roberson (2022) para estas classes específicas, mostrando que classes fechadas sob menores e uniões disjuntas (como $T^k_q$) possuem essa propriedade de maximalidade.

3. Principais Contribuições e Resultados

• Teorema 1.1 (Guarded Counting Logic): Estabelecem uma caracterização para a lógica de contagem guardada ($GC^k_q$) usando uma nova classe de grafos $GT^k_q$, relacionada a $T^k_q$.
• Teorema 1.2 (Separação Sintática): Provam que, para $q$ suficientemente maior que $k$, a classe $T^k_q$ é estritamente contida em $TW_{k-1} \cap TD_q$ ($T^k_q \subsetneq TW_{k-1} \cap TD_q$). Isso demonstra que a existência de uma decomposição de largura pequena e a existência de uma cobertura de profundidade pequena não garantem a existência de uma estrutura que satisfaça ambas simultaneamente.
• Teorema 1.3 e 1.4 (Fechamento Semântico):
  • Provam que a classe $TD_q$ é fechada sob distinção de homomorfismos.
  • Provam que a classe $T^k_q$ é fechada sob distinção de homomorfismos.
  • Isso permite "elevar" a separação sintática para uma separação semântica.
• Corolário 1.5 (Separação Semântica): Concluem que, para $q$ suficientemente maior que $k$, a relação de indistinguibilidade de homomorfismos sobre $T^k_q$ é estritamente mais grosseira (mais fraca) do que a relação sobre $TW_{k-1} \cap TD_q$.
  • Implicação: Existem grafos $G$ e $H$ que satisfazem as mesmas sentenças em $C^k_q$ (são indistinguíveis sobre $T^k_q$), mas que podem ser distinguidos por homomorfismos sobre grafos em $TW_{k-1} \cap TD_q$. Portanto, a equivalência lógica $C^k_q$ não é caracterizada pela interseção das classes de largura e profundidade.

4. Significado e Impacto

1. Refinamento da Teoria da Lógica em Grafos: O trabalho corrige uma suposição intuitiva sobre como as restrições de variáveis e profundidade interagem na lógica de contagem. Mostra que a interação entre largura de árvore e profundidade de árvore é mais complexa do que a simples interseção de classes.
2. Novas Ferramentas Estruturais: A introdução de pré-decomposições de árvore e o procedimento de limpeza para provar a monotonicidade do jogo Cops-and-Robber para largura de árvore limitada oferecem novas ferramentas para a teoria de decomposição de grafos, potencialmente aplicáveis a outros parâmetros.
3. Conexão com Redes Neurais e Algoritmos: Como a lógica de contagem e a indistinguibilidade de homomorfismos estão intimamente ligadas ao poder expressivo de Redes Neurais em Grafos (GNNs) e ao algoritmo Weisfeiler-Leman, estes resultados fornecem limites teóricos mais precisos sobre o que esses modelos podem ou não distinguir em termos de contagem de subgrafos e estrutura.
4. Progresso na Conjectura de Roberson: Ao confirmar a conjectura de Roberson para a classe $T^k_q$, o artigo avança na compreensão de quais classes de grafos são "maximais" em termos de indistinguibilidade, um problema aberto na teoria de grafos moderna.

Em resumo, o artigo demonstra que "ir fundo" (profundidade de árvore) e "ir largo" (largura de árvore) não são propriedades independentes que se somam simplesmente na lógica de contagem; a estrutura combinatória necessária para capturar a lógica $C^k_q$ é estritamente mais restritiva do que a mera interseção das classes de largura e profundidade.