🔢 mathematics

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

This paper characterizes the expressive power of the $k$ -variable, quantifier-rank- $q$ fragment of counting logic via homomorphism indistinguishability over graphs with $k$ -pebble forest covers of depth $q$ , proving that this class is distinct from the intersection of bounded treewidth and bounded treedepth graphs and confirming Roberson's conjecture that these classes are homomorphism distinguishing closed through a novel monotone Cops-and-Robber game analysis.

Original authors: Isolde Adler, Eva Fluck, Tim Seppelt, Gian Luca Spitzer

Published 2026-04-02

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Isolde Adler, Eva Fluck, Tim Seppelt, Gian Luca Spitzer

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to describe two complex cities to a friend who has never seen them. You want to know: Are these cities fundamentally the same, or are they secretly different?

In the world of computer science and mathematics, "cities" are graphs (networks of points and lines), and the "description" is a logic language. This paper is about a specific, powerful language called Counting Logic. It's like a language where you don't just say "There is a park," you can say, "There are at least five parks connected to the main square."

The authors of this paper are trying to figure out exactly how much detail this language can see. They discovered that the language has a specific "resolution limit." If two cities look the same through this lens, they are indistinguishable. But what kind of cities can this language distinguish?

Here is the breakdown of their discovery using simple analogies.

1. The Two Ways to Measure a City

To understand the limits of the language, the authors looked at two different ways to measure the complexity of a city:

Treewidth (The "Width" of the City): Imagine trying to flatten a city onto a map without tearing it apart. If the city is a simple grid or a tree, it's easy. If it's a tangled mess of highways, it's hard. "Treewidth" measures how "tree-like" a city is. A low treewidth means the city is simple and organized.
Treedepth (The "Height" of the City): Imagine a hierarchy. In a city with low depth, everyone is close to the mayor (the root). In a city with high depth, you have to go through many layers of managers to get to the top. "Treedepth" measures how deep the hierarchy goes.

The Old Belief:
For a long time, mathematicians thought that if you combined these two rules—saying a city must be both "narrow" (low width) AND "shallow" (low depth)—you would get the perfect description of what the Counting Logic can see. They thought:

If a city is narrow enough AND shallow enough, the logic can see everything about it.

2. The Big Surprise: The "Hidden" Complexity

The authors proved that this old belief is wrong.

They found a special class of cities (let's call them "T-k-q Cities") that are actually simpler than the combination of "narrow and shallow."

The Analogy of the "Peek-a-Boo" Game:
Imagine a game of Cops and Robbers played on a city map.

The Cops are trying to catch the Robber.
The Robber is trying to hide.
The Counting Logic is like a referee watching the game.

The authors showed that the "T-k-q Cities" are the specific types of cities where a team of k cops can catch the robber in q rounds.

Here is the twist: They found cities where the cops can win in $q$ rounds using $k$ cops, but these cities are not simply "narrow and shallow" in the traditional sense.

Think of it like a maze. You might be able to solve a maze quickly (low depth) with a few people (low width), but the structure of the maze allows for a specific type of "shortcut" that the old rules didn't account for.
The authors proved that the set of cities the logic can distinguish is a strict subset of the "narrow and shallow" cities. There are "narrow and shallow" cities that the logic cannot distinguish from each other, even though they are technically different.

3. The "Cleaning" Procedure (The Secret Sauce)

How did they prove this? They invented a new way to look at the game.

Imagine the Cops have a winning strategy, but it's messy. They might move a cop back and forth, or move a cop into a dead end and then pull them out. This is a "non-monotone" strategy (it goes back and forth).

The authors developed a "Cleaning Up" procedure.

Imagine you have a messy room (the game strategy).
You want to organize it so that once you put a box in a corner, you never have to move it again.
They showed that even if the Cops' original strategy was messy, you can rearrange it into a "clean" strategy where the Cops never have to backtrack.
This "clean" strategy corresponds to a specific mathematical structure (a Pre-Tree-Decomposition) that perfectly matches the logic's limits.

This was a huge deal because, in many similar games, you can't always clean up the strategy without losing the win. But for this specific type of graph, they proved you always can.

4. The "Homomorphism" Test (The Magic Mirror)

Finally, they connected this game to a concept called Homomorphism Indistinguishability.

Think of this as a Magic Mirror.

You take a small shape (a "pattern" or a "query") and try to fit it into City A and City B.
If the number of ways you can fit the shape into City A is exactly the same as into City B, the mirror says, "They are the same."
The authors proved that the "T-k-q Cities" are the only shapes you need to use as your "test patterns" to see if two cities are indistinguishable by the Counting Logic.

Summary: Why Does This Matter?

It Refines Our Tools: We now know exactly how powerful the "Counting Logic" is. It's not just about width and depth; it's about a specific, more subtle combination of the two.
It Solves a Puzzle: It proves that two different mathematical definitions (one based on width/depth, one based on the Cop game) are actually different. One is strictly "smaller" than the other.
It Helps AI and Databases: This logic is used in Graph Neural Networks (the AI that powers things like recommendation engines) and database queries. Knowing the exact limits of what these systems can "see" helps engineers build better, more efficient algorithms.

In a nutshell: The authors found a hidden layer of complexity in how we measure networks. They showed that a specific game (Cops and Robbers) reveals a "sweet spot" of complexity that is smaller and more precise than anyone thought possible, and they proved it by inventing a clever way to "clean up" the game strategies.

1. Problem Statement

The paper investigates the expressive power of the $k$ -variable, quantifier-rank- $q$ fragment of counting first-order logic, denoted as $\mathcal{C}^k_q$ . This logic extends standard first-order logic with counting quantifiers ( $\exists^{\ge t} x$ ) and restricts the number of variables to $k$ and the nesting depth of quantifiers to $q$ .

The central problem is to characterize the equivalence relation induced by $\mathcal{C}^k_q$ (i.e., when two graphs satisfy the same sentences in this fragment) using homomorphism indistinguishability.

Homomorphism Indistinguishability: Two graphs $G$ and $H$ are indistinguishable over a class of graphs $\mathcal{F}$ (denoted $G \equiv_{\mathcal{F}} H$ ) if for every $F \in \mathcal{F}$ , the number of homomorphisms from $F$ to $G$ equals the number from $F$ to $H$ .
Context: Previous work established that:
- $\mathcal{C}^k$ -equivalence corresponds to indistinguishability over graphs of treewidth $\le k-1$ ( $\mathcal{TW}_{k-1}$ ).
- $\mathcal{C}^q$ -equivalence corresponds to indistinguishability over graphs of treedepth $\le q$ ( $\mathcal{TD}_q$ ).
The Gap: It was an open question whether $\mathcal{C}^k_q$ -equivalence corresponds to indistinguishability over the intersection $\mathcal{TW}_{k-1} \cap \mathcal{TD}_q$ . The authors define a specific class $\mathcal{T}^k_q$ (graphs admitting a $k$ -pebble forest cover of depth $q$ ) and prove that $\mathcal{T}^k_q \subsetneq \mathcal{TW}_{k-1} \cap \mathcal{TD}_q$ when $q$ is sufficiently larger than $k$ . The core challenge is to prove that this syntactic separation of graph classes translates to a semantic separation of their homomorphism indistinguishability relations.

2. Methodology

The authors employ a multi-faceted approach combining structural graph theory, game theory, and logic:

A. Graph Decompositions

They introduce and analyze three equivalent characterizations of the class $\mathcal{T}^k_q$ :

$k$ -Pebble Forest Covers: A rooted forest cover where edges respect the ancestor-descendant relation, and pebbles (labels $1 \dots k$ ) are assigned such that no two vertices on a path between an edge's endpoints share a pebble.
Rooted Tree-Decompositions: A tree-decomposition with width $\le k-1$ and a specific depth measure (max size of the union of bags along any root-to-leaf path).
$k$ -Construction Trees: A tree of $k$ -labelled graphs built via product nodes (combining graphs) and elimination nodes (removing a label). The "elimination depth" is bounded by $q$ .

B. Cops-and-Robber Games

To characterize $\mathcal{T}^k_q$ , the authors define a $k$ -Cops, $q$ -Round Cops-and-Robber game.

Key Technical Innovation: They prove that for this specific game, monotonicity is not a restriction; if Cop has a winning strategy, they have a monotone winning strategy (where cleared areas are never re-entered).
Proof Technique: They introduce the concept of a pre-tree-decomposition (inspired by matroid decompositions) derived from a non-monotone winning strategy. They then apply a breadth-first "cleaning up" procedure to transform this pre-tree-decomposition into an exact one (and subsequently a standard tree-decomposition) while preserving width and depth bounds. This involves a vertex exchange argument to control the number of rounds across all branches.

C. Homomorphism Distinguishing Closure

To separate the logical equivalences, they rely on Roberson's Conjecture, which posits that any graph class closed under minors and disjoint unions is homomorphism distinguishing closed (i.e., if $G \equiv_{\mathcal{F}} H$ , then $hom(F, G) = hom(F, H)$ for all $F \in \mathcal{F}$ implies $F \in \mathcal{F}$ ).

They prove that $\mathcal{TD}_q$ and $\mathcal{T}^k_q$ are homomorphism distinguishing closed.
They utilize CFI-like graphs (Cai-Fürer-Immerman constructions) to construct pairs of graphs that are indistinguishable over $\mathcal{T}^k_q$ but distinguishable over $\mathcal{TW}_{k-1} \cap \mathcal{TD}_q$ .

3. Key Contributions and Results

Theorem 1: Characterization of $\mathcal{C}^k_q$

Two graphs are $\mathcal{C}^k_q$ -equivalent if and only if they are homomorphism indistinguishable over the class $\mathcal{T}^k_q$ .

Method: They provide an elementary proof translating $\mathcal{C}^k_q$ sentences into construction trees and vice versa, generalizing results by Dvořák and Grohe.
Extension: They also characterize Guarded Counting Logic ( $\mathcal{GC}^k_q$ ) using a restricted class of construction trees ( $\mathcal{GT}^k_q$ ).

Theorem 2: Strict Separation of Classes

For $q$ sufficiently larger than $k$ , the class $\mathcal{T}^k_q$ is a proper subclass of $\mathcal{TW}_{k-1} \cap \mathcal{TD}_q$ .

Proof: They construct grid graphs $G_{h \times \ell}$ where the treewidth is small ( $h$ ) and treedepth is bounded ( $q$ ), but the specific structural constraints of $\mathcal{T}^k_q$ (simultaneous width and depth control) are violated. This is demonstrated by showing Robber wins the $k$ -Cops, $q$ -Round game on these grids, implying they are not in $\mathcal{T}^k_q$ .

Theorem 3: Homomorphism Distinguishing Closure

The classes $\mathcal{TD}_q$ and $\mathcal{T}^k_q$ are homomorphism distinguishing closed.

Significance: This confirms Roberson's conjecture for these specific classes. It ensures that the syntactic difference between $\mathcal{T}^k_q$ and $\mathcal{TW}_{k-1} \cap \mathcal{TD}_q$ is not "hidden" by homomorphism counts.

Corollary: Semantic Separation

For $q$ sufficiently larger than $k$ , the homomorphism indistinguishability relation $\equiv_{\mathcal{T}^k_q}$ is strictly coarser than $\equiv_{\mathcal{TW}_{k-1} \cap \mathcal{TD}_q}$ .

This implies that $\mathcal{C}^k_q$ -equivalence is strictly weaker than the conjunction of $\mathcal{C}^k$ and $\mathcal{C}^q$ equivalences. There exist graphs that satisfy the same $\mathcal{C}^k$ and $\mathcal{C}^q$ sentences but differ in $\mathcal{C}^k_q$ .

4. Significance and Impact

Refining Logical Expressivity: The paper resolves a subtle but important question in finite model theory: the intersection of logical fragments does not simply correspond to the intersection of their structural characterizations. The "going deep and going wide" title reflects the necessity of a specific decomposition (pebble forest cover) that captures the interplay between variable count and quantifier depth, which is distinct from simply having both low width and low depth.
New Proof Techniques: The introduction of pre-tree-decompositions and the cleaning-up procedure provides a novel method for proving monotonicity in graph searching games. This technique avoids the need for dual objects (like brambles) and may be applicable to other graph parameters where monotonicity is non-trivial.
Advancing Roberson's Conjecture: By confirming the homomorphism distinguishing closure for $\mathcal{T}^k_q$ and $\mathcal{TD}_q$ , the paper adds significant evidence to Roberson's conjecture, which is a major open problem in the field of homomorphism indistinguishability.
Connections to GNNs and Algorithms: Since counting logic fragments are closely related to the expressive power of Graph Neural Networks (GNNs) (specifically the Weisfeiler-Leman algorithm), these results offer deeper theoretical bounds on what GNNs can distinguish when constrained by both depth and width parameters.

In summary, the paper establishes that the expressive power of counting logic with bounded variables and depth is captured by a specific, strictly smaller class of graphs than the naive intersection of bounded treewidth and treedepth, and rigorously proves that this structural difference is detectable via homomorphism counts.