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

Probleemstelling

Het artikel onderzoekt de expressiviteit van het fragment $C^k_q$ van de tellende eerste-orde logica (first-order logic with counting quantifiers). Dit fragment bestaat uit formules met maximaal $k$ variabelen en een kwantifiekerrang (quantifier rank) van $q$.

Een centrale vraag in de eindige modeltheorie is hoe logische equivalentie tussen grafen kan worden gekarakteriseerd via homomorfisme-ononderscheidbaarheid (homomorphism indistinguishability). Twee grafen $G$ en $H$ zijn ononderscheidbaar over een graafklasse $\mathcal{F}$ (genoteerd als $G \equiv_{\mathcal{F}} H$) als het aantal homomorfismen van elke graaf $F \in \mathcal{F}$ naar $G$ gelijk is aan het aantal naar $H$.

Eerdere resultaten (Dvořák, Grohe) toonden aan dat:

• $C^k$-equivalentie correspondeert met ononderscheidbaarheid over grafen met treewidth $\le k-1$ ($\mathcal{TW}_{k-1}$).
• $C^q$-equivalentie correspondeert met ononderscheidbaarheid over grafen met treedepth $\le q$ ($\mathcal{TD}_q$).

Dawar, Jakl en Reggio (2021) bewezen recent dat $C^k_q$-equivalentie correspondeert met ononderscheidbaarheid over een specifieke klasse $\mathcal{T}^k_q$, die bestaat uit grafen die een $k$-pebble forest cover van diepte $q$ toelaten. Een natuurlijke hypothese zou zijn dat $\mathcal{T}^k_q$ simpelweg de doorsnede is van $\mathcal{TW}_{k-1}$ en $\mathcal{TD}_q$. Dit artikel weerlegt deze intuïtie en toont aan dat deze klassen strikt verschillend zijn, zelfs op semantisch niveau.

Methodologie

De auteurs hanteren een combinatie van grafentheoretische decomposities, speltheorie (Cops-and-Robber games) en homomorfisme-telling.

1. Elementaire Bewijstechnieken:
   In plaats van te vertrouwen op de complexe categorische framework van "game comonads" (zoals in eerdere werken), geven de auteurs een elementair en uniform bewijs dat $C^k_q$-equivalentie correspondeert met homomorfisme-ononderscheidbaarheid over $\mathcal{T}^k_q$. Ze gebruiken constructie-bomen (construction trees) om de relatie tussen logica en grafen inductief op te bouwen.

2. Grafische Decomposities:
   Ze introduceren drie equivalente definities voor de klasse $\mathcal{T}^k_q$:

   • Grafen met een $k$-pebble forest cover van diepte $q$.
   • Grafen met een georiënteerde boom-decompositie (rooted tree-decomposition) met breedte $\le k-1$ en diepte $\le q$.
   • Grafen die $(k, q)$-constructibel zijn via een specifieke boomstructuur.

3. Cops-and-Robber Spellen:
   Een kernbijdrage is het karakteriseren van $\mathcal{T}^k_q$ via een variant van het Cops-and-Robber spel. Ze definiëren een spel met $k$ agenten (Cops) en $q$ rondes. Het cruciale technische resultaat is het bewijzen dat dit spel monotoon is: als de Cops een winnende strategie hebben, hebben ze ook een winnende strategie waarbij ze nooit een eerder opgehelderd gebied hoeven te verlaten (geen "terugtrekken").

   • Om dit te bewijzen, introduceren ze het concept van een pre-tree-decomposition, geïnspireerd door matroid-decomposities.
   • Ze ontwikkelen een breadth-first 'cleaning up' procedure die een niet-monotone strategie transformeert in een exacte pre-tree-decompositie, en uiteindelijk in een boom-decompositie, zonder de breedte of diepte te vergroten.

4. Homomorfisme-onderscheidings-sluiting (Homomorphism Distinguishing Closure):
   Om de semantische scheiding te bewijzen, gebruiken ze de theorie van Roberson (2022). Een graafklasse $\mathcal{F}$ is "homomorphism distinguishing closed" als voor elke graaf $F \notin \mathcal{F}$ er twee grafen bestaan die ononderscheidbaar zijn over $\mathcal{F}$, maar een verschillend aantal homomorfismen hebben van $F$. De auteurs bewijzen dat $\mathcal{TD}_q$ en $\mathcal{T}^k_q$ deze eigenschap bezitten.

Belangrijkste Resultaten

1. Scheiding van Grafklassen (Syntactisch):
   Voor $q$ voldoende groter dan $k$, is de klasse $\mathcal{T}^k_q$ een strikt echte deelklasse van de doorsnede $\mathcal{TW}_{k-1} \cap \mathcal{TD}_q$.

   • Bewijs: Ze construeren roosters (grids) $G_{h \times \ell}$ waarvoor een boom-decompositie met kleine breedte en een bos-cover met kleine diepte bestaan, maar waarvoor geen enkele decompositie tegelijkertijd kleine breedte en kleine diepte heeft. Dit wordt aangetoond door te laten zien dat de Robber een winnende strategie heeft in het Cops-and-Robber spel op deze roosters, ondanks dat de grafen in de doorsnede zitten.

2. Scheiding van Logische Equivalentie (Semantisch):
   Omdat $\mathcal{T}^k_q$ en $\mathcal{TD}_q$ (en dus ook hun doorsnede) homomorphism distinguishing closed zijn, impliceert de syntactische scheiding direct een semantische scheiding.

   • Er bestaan grafen $G$ en $H$ die $C^k_q$-equivalent zijn (ononderscheidbaar over $\mathcal{T}^k_q$), maar die niet ononderscheidbaar zijn over $\mathcal{TW}_{k-1} \cap \mathcal{TD}_q$.
   • Dit betekent dat de expressiviteit van $C^k_q$ strikt lager is dan wat men zou verwachten van de combinatie van beperkte breedte en beperkte diepte.

3. Guarded Counting Logic:
   De auteurs passen hun methode toe op Guarded Counting Logic ($GC^k_q$). Ze introduceren een subklasse $GT^k_q$ van grafen en bewijzen dat $GC^k_q$-equivalentie precies correspondeert met homomorfisme-ononderscheidbaarheid over deze klasse.

4. Monotonie van Cops-and-Robber:
   Ze leveren een nieuw, constructief bewijs voor de monotonie van het Cops-and-Robber spel voor treewidth en de nieuwe parameter voor $\mathcal{T}^k_q$, zonder gebruik te maken van duale objecten zoals brambles.

Significantie

• Fundamentele Inzicht: Het artikel weerlegt de intuïtie dat logische fragmenten die beperkingen op zowel variabelen als diepte combineren, simpelweg corresponderen met de doorsnede van de respectievelijke grafklassen. De interactie tussen "breedte" (treewidth) en "diepte" (treedepth) is subtieler dan gedacht.
• Technische Innovatie: De introductie van pre-tree-decomposities en de cleaning-up procedure biedt een krachtig nieuw instrument om de relatie tussen spelstrategieën en graf-decomposities te analyseren. Dit is relevant voor het bestuderen van andere grafparameters en spelvarianten.
• Roberson's Vermoeden: Het artikel draagt bij aan het open probleem van Roberson door te bewijzen dat de klassen $\mathcal{TD}_q$ en $\mathcal{T}^k_q$ homomorphism distinguishing closed zijn. Dit bevestigt het vermoeden voor deze specifieke, belangrijke klassen.
• Toepassingen: De resultaten hebben implicaties voor het Weisfeiler-Leman algoritme en Graph Neural Networks (GNNs), aangezien de expressiviteit van deze modellen vaak wordt gekarakteriseerd door logische fragmenten en homomorfisme-tellingen. Het inzicht in de scheiding tussen klassen helpt bij het begrijpen van de beperkingen van deze modellen bij het tellen van subgrafieken.

Kortom, dit werk verduidelijkt de hiërarchie van expressiviteit in tellende logica door een nauwkeurige analyse van de structuur van grafen met beperkte breedte en diepte, ondersteund door innovatieve speltheoretische methoden.