Breadth-First Search in Succinct Planar Graphs

Definizione del Problema

Il documento affronta la sfida di eseguire algoritmi di attraversamento di grafi spazialmente efficienti, nello specifico la ricerca in ampiezza (Breadth-First Search, BFS), su grafi planari mantenendo l'albero BFS risultante come una struttura dati accessibile. Gli algoritmi BFS standard nel modello word-RAM richiedono $\Theta(n \log n)$ bit per memorizzare lo stato di visita e una coda, il che è proibitivo per ambienti con vincoli di spazio. Lavori precedenti hanno ottenuto BFS e DFS (Depth-First Search) spazialmente efficienti utilizzando $O(n)$ bit, ma tipicamente restituiscono i vertici nell'ordine di visita senza conservare l'albero di attraversamento per query successive (ad esempio, query su genitore/figlio, query sui livelli o il Minimo Comune Ancestro). Questa mancanza di accesso strutturale limita l'utilità di tali attraversamenti come subroutine in algoritmi più complessi. L'obiettivo specifico è costruire una codifica succinta di grafi planari che consenta l'esecuzione diretta della BFS utilizzando $o(n)$ bit aggiuntivi, mantenendo l'albero BFS calcolato disponibile per le operazioni standard sugli alberi in tempo costante per query.

Metodologia

La soluzione proposta si basa sul framework di divisione nidificata succinta introdotto da Blelloch e Farzan e esteso da Elberfeld et al. per la DFS. La metodologia comprende diverse componenti chiave:

1. Divisione Nidificata Succinta: Il grafo planare in input viene decomposto in una gerarchia di "mini pezzi" (mini pieces) e "micro pezzi" (micro pieces) utilizzando una strategia di $r$-divisione.

   • Mini pezzi sono di dimensione $r_0 = \text{poly}(\log n)$ e contengono $O(r_0^{1/2+\epsilon})$ vertici di confine.
   • Micro pezzi sono più piccoli, di dimensione $r_1 = \text{poly}(\log \log n)$, e sono sufficientemente piccoli da essere rappresentati da indici in una tabella di lookup precomputata.
   • La codifica memorizza la connettività tra i pezzi e utilizza dizionari indicizzabili compressi per mappare le etichette globali dei vertici in etichette locali all'interno dei pezzi.

2. Triangolazione: Per facilitare la BFS, il documento presenta innanzitutto una procedura per triangolare grafi piani biconnessi all'interno della codifica succinta. Ciò comporta l'aggiunta di archi ausiliari tra i vertici di confine per garantire che le facce siano interamente all'interno di un micro pezzo o consistano esclusivamente di vertici di confine. Questo passaggio viene eseguito in tempo atteso $O(n)$ per la variante succinta e in tempo deterministico $O(n)$ per una variante compatta.

3. Esecuzione della BFS tramite Table-Swap: Il core dell'algoritmo esegue la BFS direttamente sulla codifica senza memorizzare esplicitamente la coda completa o l'array di visita.

   • Rappresentazione dello Stato: Lo stato della BFS è mantenuto monitorando i mini e i micro pezzi "attivi". Per i micro pezzi, lo stato è codificato come uno "stato parziale di BFS" che consiste in un profilo di confine (colori che indicano lo stato visitato/non visitato e l'elaborazione del livello corrente) e un contatore di avanzamento locale.
   • Operazioni di Table-Swap: La tabella di lookup per i micro pezzi supporta un'operazione di "table-swap". Dato il profilo di confine corrente e l'avanzamento locale, la tabella restituisce il successivo stato, i nuovi vertici di confine raggiunti e se il pezzo rimane attivo. Ciò consente alla BFS di progredire attraverso i micro pezzi in $O(1)$ tempo per operazione.
   • Sincronizzazione: Quando un vertice di confine viene raggiunto, le sue informazioni di livello e di genitore vengono propagate a tutti gli altri pezzi che contengono tale vertice (sincronizzazione del confine). Questo è gestito esplicitamente per i casi eccezionali e tramite operazioni di tabella per i casi standard.

4. Manutenzione dell'Albero: L'albero BFS risultante è memorizzato implicitamente all'interno della codifica. I puntatori ai genitori e le informazioni sui livelli per i vertici di confine sono memorizzati esplicitamente, mentre i vertici interni sono gestiti tramite gli stati della tabella di lookup.

Contributi Chiave e Risultati

Il documento presenta i seguenti risultati principali:

• Codifica BFS Succinta: Una codifica succinta per grafi planari connessi che permette di calcolare un albero BFS con radice in un qualsiasi vertice $s$ in $O(n)$ tempo utilizzando $o(n)$ bit aggiuntivi.
• Supporto alle Query: Una volta calcolato, l'albero BFS supporta query in tempo costante per:
  • Attraversamento (preorder, postorder, ordine BFS).
  • Query sui livelli ($\ell(u)$).
  • Iterazione su genitore e figlio.
  • Test tra arco dell'albero e non-arco dell'albero.
  • Query del Minimo Comune Ancestro (LCA).
• Complessità di Costruzione:
  • Variante Succinta: Costruita in tempo atteso $O(n)$ utilizzando $O(n)$ bit durante la costruzione.
  • Variante Compatta: Costruita in tempo deterministico $O(n)$ utilizzando $O(n)$ bit.
• Applicazioni:
  • Teorema del Separatore Planare: La codifica consente il calcolo di un separatore bilanciato di dimensione $O(\sqrt{n})$ per grafi piani biconnessi in $O(n)$ tempo utilizzando $o(n)$ bit aggiuntivi. Ciò è ottenuto trovando un separatore di ciclo a cammino minimo bilanciato usando l'albero interdigitato (l'albero spanning duale degli archi non appartenenti all'albero).
  • Test di Bipartitismo: Viene fornito un test di bipartitismo a spazio sublineare, che opera in $o(n)$ tempo controllando la parità dei livelli BFS per gli archi non appartenenti all'albero.
  • Decomposizione in Alberi: Una decomposizione in alberi implicita di larghezza $O(d)$ (dove $d$ è il diametro del grafo) è derivata dall'albero BFS e dall'albero interdigitato, con bag (sacche) attraversabili in tempo lineare.
  • Generalizzazione: I risultati riguardanti il calcolo della BFS e le query sull'albero si generalizzano a qualsiasi classe di grafi separabili, a patto che sia disponibile una divisione nidificata succinta, sebbene i tempi di costruzione specifici e le garanzie di spazio per i grafi planari possano non valere per tutte le classi separabili.

Significato

Il documento sostiene di colmare una lacuna critica negli algoritmi di grafi spazialmente efficienti. Mentre il lavoro precedente (Elberfeld et al.) ha adattato con successo le codifiche succinte per la DFS, gli autori osservano che la BFS presenta sfide uniche perché non è così "locale" come la DFS; un albero BFS deve preservare le distanze di cammino minimo, il che significa che una ricerca non può semplicemente esaurire un sottografo localmente senza considerare potenziali cammini più brevi che entrano attraverso altri vertici di confine.

Il significato di questo lavoro risiede nel dimostrare che, nonostante queste sfide, un albero BFS può essere calcolato e mantenuto all'interno della codifica succinta utilizzando solo $o(n)$ bit aggiuntivi. Questa capacità consente l'implementazione di algoritmi di grafi complessi, come il teorema del separatore planare, in spazio sublineare mantenendo l'accesso strutturale all'albero di attraversamento, che è spesso richiesto per correttezza ed efficienza. La capacità di eseguire queste operazioni su grafi non etichettati (preservando l'isomorfismo) rende la codifica adatta a problemi decisionali e al tracciamento di specifiche soluzioni, anche se le etichette arbitrarie dei vertici non vengono preservate. Il lavoro estende l'applicabilità delle strutture dati succinte da semplici output di attraversamento a rappresentazioni strutturali complete degli alberi di attraversamento.