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

1. Il Problema

Il lavoro si concentra sulla potenza espressiva della logica del primo ordine con quantificatori di conteggio ($C$), in particolare sui suoi frammenti a $k$ variabili e profondità di quantificatore $q$, denotati come $C^k_q$.
Un problema centrale nella teoria dei modelli finiti è caratterizzare l'equivalenza logica tra grafi tramite relazioni di indistinguibilità per omomorfismi. Due grafi $G$ e $H$ sono indistinguibili su una classe di grafi $\mathcal{F}$ (scritto $G \equiv_{\mathcal{F}} H$) se il numero di omomorfismi da ogni grafo $F \in \mathcal{F}$ verso $G$ è uguale a quello verso $H$.

È noto che:

• L'equivalenza in $C^k$ corrisponde all'indistinguibilità sulla classe dei grafi con larghezza ad albero (treewidth) $\le k-1$ ($\mathcal{TW}_{k-1}$).
• L'equivalenza in $C^q$ corrisponde all'indistinguibilità sulla classe dei grafi con profondità ad albero (treedepth) $\le q$ ($\mathcal{TD}_q$).

La domanda aperta affrontata in questo lavoro è: l'equivalenza nel frammento intersecato $C^k_q = C^k \cap C^q$ è caratterizzata dall'indistinguibilità sulla classe intersecata $\mathcal{TW}_{k-1} \cap \mathcal{TD}_q$?
In altre parole, esiste una classe di grafi $\mathcal{T}^k_q$ che cattura esattamente $C^k_q$, e questa classe è strettamente contenuta in $\mathcal{TW}_{k-1} \cap \mathcal{TD}_q$ quando $q$ è sufficientemente grande rispetto a $k$?

2. Metodologia

Gli autori utilizzano un approccio combinato che integra teoria dei grafi, teoria dei giochi e logica matematica:

• Decomposizioni di Grafi: Introducono e analizzano tre definizioni equivalenti della classe $\mathcal{T}^k_q$:
  1. Copertura di foreste con $k$ sassolini (k-pebble forest cover) di profondità $q$.
  2. Decomposizione ad albero (tree-decomposition) con larghezza $\le k-1$ e una nuova nozione di "profondità" basata sulla dimensione delle borse (bags) lungo i percorsi.
  3. Alberi di costruzione ($k$-construction trees) con profondità di eliminazione limitata.
• Giochi di Ricerca (Cops-and-Robber): Caratterizzano $\mathcal{T}^k_q$ tramite un gioco varianto "Cops-and-Robber" con $k$ poliziotti e $q$ round. La sfida principale è dimostrare che la versione monotona del gioco (dove le aree già pulite non devono essere ri-pulite) è equivalente alla versione non monotona per questa specifica classe.
• Pre-alberi di decomposizione e Pulizia: Per dimostrare la monotonia, gli autori introducono il concetto di pre-tree-decomposition (ispirato alle decomposizioni di matroidi). Sviluppano una procedura di "pulizia" (cleaning-up) basata su una visita in ampiezza (BFS) che trasforma una strategia vincente non monotona in una decomposizione esatta, mantenendo il controllo su larghezza e profondità.
• Indistinguibilità per Omomorfismi: Utilizzano la tecnica delle "combinazioni lineari formali di grafi" (quantum graphs) e il teorema di Lovász generalizzato per collegare i conteggi degli omomorfismi alla logica. Dimostrano che certe classi di grafi sono "chiuse per distinzione per omomorfismi" (homomorphism distinguishing closed), un concetto congetturato da Roberson.

3. Contributi Chiave

A. Caratterizzazione di $\mathcal{T}^k_q$

Gli autori provano che le tre definizioni sopra menzionate sono equivalenti (Teorema 3.4 e 4.1). In particolare, dimostrano che un grafo appartiene a $\mathcal{T}^k_q$ se e solo se il poliziotto vince il gioco Cops-and-Robber con $k$ poliziotti in $q$ round, e che questa vittoria implica l'esistenza di una strategia monotona. Questo è un risultato non banale, poiché per altri parametri di larghezza (come la larghezza ad albero diretta) le versioni monotone e non monotone non sono equivalenti.

B. Separazione Sintattica e Semantica

• Separazione Sintattica: Dimostrano che per $q$ sufficientemente maggiore di $k$, la classe $\mathcal{T}^k_q$ è un sottoinsieme proprio di $\mathcal{TW}_{k-1} \cap \mathcal{TD}_q$ (Teorema 1.2). Costruiscono grafi (griglie $h \times \ell$) che hanno sia larghezza ad albero bassa che profondità ad albero bassa, ma che non ammettono una copertura di foreste con $k$ sassolini di profondità $q$.
• Separazione Semantica: La separazione sintattica non garantisce automaticamente che le relazioni di indistinguibilità siano diverse. Gli autori provano che le classi $\mathcal{TD}_q$ e $\mathcal{T}^k_q$ sono chiuse per distinzione per omomorfismi (Teoremi 1.3 e 1.4). Questo conferma la congettura di Roberson per queste classi. Di conseguenza, poiché le classi sono diverse e chiuse, le relazioni di indistinguibilità $\equiv_{\mathcal{T}^k_q}$ e $\equiv_{\mathcal{TW}_{k-1} \cap \mathcal{TD}_q}$ sono semanticamente distinte (Corollario 1.5).

C. Logica di Conteggio Protetta (Guarded Counting Logic)

Estendono i risultati alla logica di conteggio protetta ($GC^k_q$), introducendo una nuova classe di grafi $\mathcal{GT}^k_q$ basata su alberi di costruzione con vincoli di adiacenza per la rimozione dei label. Dimostrano che l'equivalenza in $GC^k_q$ corrisponde all'indistinguibilità su $\mathcal{GT}^k_q$ (Teorema 1.1).

4. Risultati Principali

1. Teorema 1.2: Per $q$ sufficientemente grande rispetto a $k$, $\mathcal{T}^k_q \subsetneq \mathcal{TW}_{k-1} \cap \mathcal{TD}_q$.
2. Teorema 1.3 e 1.4: Le classi $\mathcal{TD}_q$ e $\mathcal{T}^k_q$ sono chiuse per distinzione per omomorfismi.
3. Corollario 1.5: Per $q$ sufficientemente grande, la relazione di indistinguibilità su $\mathcal{T}^k_q$ è strettamente più grossolana (coarser) di quella su $\mathcal{TW}_{k-1} \cap \mathcal{TD}_q$. Questo significa che esistono grafi indistinguibili in $C^k_q$ ma distinguibili tramite omomorfismi da grafi nella classe intersecata.
4. Teorema 5.9: Due grafi sono equivalenti in $C^k_q$ se e solo se sono indistinguibili su $\mathcal{T}^k_q$.
5. Teorema 1.1: Due grafi sono equivalenti in $GC^k_q$ se e solo se sono indistinguibili su $\mathcal{GT}^k_q$.

5. Significato e Implicazioni

• Teoria dei Modelli: Il lavoro chiarisce la gerarchia espressiva della logica di conteggio, mostrando che l'intersezione di due frammenti logici ($C^k$ e $C^q$) non corrisponde semplicemente all'intersezione delle loro caratterizzazioni strutturali ($\mathcal{TW}$ e $\mathcal{TD}$). È necessaria una struttura più specifica ($\mathcal{T}^k_q$).
• Algoritmi e Reti Neurali: Poiché l'indistinguibilità per omomorfismi è legata alla potenza espressiva delle Reti Neurali su Grafi (GNN) e agli algoritmi di isomorfismo (come Weisfeiler-Leman), questi risultati forniscono limiti teorici precisi su cosa possono distinguere le GNN con un numero limitato di messaggi e profondità.
• Congettura di Roberson: Il lavoro fornisce una conferma significativa della congettura di Roberson sulla chiusura per distinzione per omomorfismi per una nuova classe di grafi strutturati, utilizzando tecniche di giochi di ricerca e decomposizioni di matroidi.
• Metodologia: La dimostrazione della monotonia del gioco Cops-and-Robber tramite la procedura di "pulizia" su pre-alberi di decomposizione rappresenta un contributo tecnico originale che potrebbe essere applicato ad altri parametri di larghezza.

In sintesi, il paper risolve una questione aperta sulla caratterizzazione logica dei grafi, dimostrando che la combinazione di vincoli di larghezza e profondità richiede una struttura di decomposizione specifica che non è semplicemente l'intersezione delle due strutture separate, e che questa differenza è rilevante anche a livello semantico (indistinguibilità).