Breadth-First Search in Succinct Planar Graphs

Declaração do Problema

O artigo aborda o desafio de realizar algoritmos de travessia de grafos eficientes em termos de espaço, especificamente a Busca em Largura (BFS - Breadth-First Search), em grafos planares, mantendo a árvore de BFS resultante como uma estrutura de dados acessível. Algoritmos de BFS padrão no modelo word-RAM requerem $\Theta(n \log n)$ bits para armazenar o status de visitação e uma fila, o que é proibitivo para ambientes com restrição de espaço. Trabalhos anteriores conseguiram realizar BFS e Busca em Profundidade (DFS - Depth-First Search) eficientes em espaço usando $O(n)$ bits, mas tipicamente fornecem os vértices na ordem de visitação sem reter a árvore de travessia para consultas subsequentes (ex: consultas de pai/filho, consultas de camada ou o Menor Ancestral Comum - LCA). Essa falta de acesso estrutural limita a utilidade dessas travessias como sub-rotinas em algoritmos mais complexos. O objetivo específico é construir uma codificação sucinta de grafos planares que suporte a execução direta de BFS usando $o(n)$ bits adicionais, mantendo a árvore de BFS computada disponível para operações de árvore padrão em tempo constante por consulta.

Metodologia

A solução proposta baseia-se no framework de divisão aninhada sucinta introduzido por Blelloch e Farzan e estendido por Elberfeld et al. para DFS. A metodologia envolve vários componentes principais:

1. Divisão Aninhada Sucinta: O grafo planar de entrada é decomposto em uma hierarquia de "pequenas partes" (mini pieces) e "micro partes" (micro pieces) usando uma estratégia de $r$-divisão.

   • Pequenas partes (mini pieces) são de tamanho $r_0 = \text{poly}(\log n)$ e contêm $O(r_0^{1/2+\epsilon})$ vértices de fronteira.
   • Micro partes (micro pieces) são menores, de tamanho $r_1 = \text{poly}(\log \log n)$, e são pequenas o suficiente para serem representadas por índices em uma tabela de consulta pré-computada.
   • A codificação armazena a conectividade entre as partes e utiliza dicionários indexáveis comprimidos para mapear rótulos globais de vértices para rótulos locais dentro das partes.

2. Triangulação: Para facilitar a BFS, o artigo apresenta primeiro um procedimento para triangular grafos planos biconexos dentro da codificação sucinta. Isso envolve a adição de arestas auxiliares entre vértices de fronteira para garantir que as faces estejam inteiramente dentro de uma micro parte ou consistam unicamente de vértices de fronteira. Esta etapa é realizada em tempo esperado de $O(n)$ para a variante sucinta e tempo determinístico de $O(n)$ para uma variante compacta.

3. Execução de BFS via Troca de Tabela (Table-Swap): O algoritmo central executa a BFS diretamente na codificação sem armazenar explicitamente a fila completa ou o array de visitação.

   • Representação de Estado: O estado da BFS é mantido rastreando as "partes ativas" (active mini and micro pieces). Para as micro partes, o estado é codificado como um "estado de BFS parcial", consistindo em um perfil de fronteira (cores indicando o status de visitado/não visitado e o processamento da camada atual) e um contador de avanço local.
   • Operações de Troca de Tabela (Table-Swap Operations): A tabela de consulta para micro partes suporta uma operação de "troca de tabela". Dado o perfil de fronteira atual e o avanço local, a tabela retorna o próximo estado, os novos vértices de fronteira alcançados e se a parte permanece ativa. Isso permite que a BFS progrida através das micro partes em $O(1)$ de tempo por operação.
   • Sincronização: Quando um vértice de fronteira é alcançado, sua camada e informação de pai são propagadas para todas as outras partes que contêm esse vértice (sincronização de fronteira). Isso é tratado explicitamente para casos excepcionais e via operações de tabela para casos padrão.

4. Manutenção da Árvore: A árvore de BFS resultante é armazenada implicitamente dentro da codificação. Os ponteiros de pai e a informação de camada para os vértices de fronteira são armazenados explicitamente, enquanto os vértices internos são tratados via o estado da tabela de consulta.

Principais Contribuições e Resultados

O artigo apresenta os seguintes resultados principais:

• Codificação de BFS Sucinta: Uma codificação sucinta para grafos planares conexos que permite computar uma árvore de BFS enraizada em qualquer vértice $s$ em $O(n)$ de tempo usando $o(n)$ bits adicionais.
• Suporte a Consultas: Uma vez computada, a árvore de BFS suporta consultas de tempo constante para:
  • Travessia (pré-ordem, pós-ordem, ordem de BFS).
  • Consultas de camada ($\ell(u)$).
  • Iteração de pai e filho.
  • Teste de aresta de árvore versus aresta não-árvore.
  • Consultas de Menor Ancestral Comum (LCA).
• Complexidade de Construção:
  • Variante Sucinta: Construída em tempo esperado de $O(n)$ usando $O(n)$ bits durante a construção.
  • Variante Compacta: Construída em tempo determinístico de $O(n)$ usando $O(n)$ bits.
• Aplicações:
  • Teorema do Separador Planar: A codificação permite a computação de um separador balanceado de tamanho $O(\sqrt{n})$ para grafos planos biconexos em $O(n)$ de tempo usando $o(n)$ bits adicionais. Isso é alcançado encontrando um separador de ciclo de caminho curto balanceado usando a árvore interdigitada (a árvore geradora dual das arestas não-árvore).
  • Teste de Bipartição: Um teste de bipartição de espaço sublinear é fornecido, executando em $o(n)$ de tempo ao verificar a paridade das camadas de BFS para arestas não-árvore.
  • Decomposição de Árvore: Uma decomposição de árvore implícita de largura $O(d)$ (onde $d$ é o diâmetro do grafo) é derivada da árvore de BFS e da árvore interdigitada, com sacos (bags) navegáveis em tempo linear.
  • Generalização: Os resultados relativos à computação de BFS se generalizam para qualquer classe de grafos separáveis, desde que uma divisão aninhada sucinta esteja disponível, embora o tempo de construção específico e as garantias de espaço para grafos planares possam não se aplicar a todas as classes separáveis.

Significância

O artigo afirma preencher uma lacuna crítica em algoritmos de grafos eficientes em espaço. Embora o trabalho anterior (Elberfeld et al.) tenha adaptado com sucesso codificações sucintas para DFS, os autores observam que a BFS apresenta desafios únicos porque não é tão "local" quanto a DFS; uma árvore de BFS deve preservar as distâncias de caminho curto, o que significa que uma busca não pode simplesmente esgotar um subgrafo localmente sem considerar potenciais caminhos mais curtos entrando através de outros vértices de fronteira.

A significância deste trabalho reside em demonstrar que, apesar desses desafios, uma árvore de BFS pode ser computada e mantida dentro da codificação sucinta usando apenas $o(n)$ bits adicionais. Essa capacidade permite a implementação de algoritmos de grafos complexos, como o teorema do separador planar, em espaço sublinear enquanto retém o acesso estrutural à árvore de travessia que é frequentemente necessário para correção e eficiência. A capacidade de realizar essas operações em grafos não rotulados (preservando o isomorfismo) torna a codificação adequada para problemas de decisão e rastreamento de soluções específicas, mesmo que rótulos de vértices arbitrários não sejam preservados. O trabalho estende a aplicabilidade de estruturas de dados sucintas de saídas de travessia simples para representações estruturais completas de árvores de travessia.