💻 computer science

State Canonization and Early Pruning in Width-Based Automated Theorem Proving

This paper advances width-based automated theorem proving by introducing state-canonization and early-pruning techniques to enhance practical efficiency, successfully validating Reed's conjecture for triangle-free graphs on bounded pathwidth and treewidth classes while automatically generating counterexamples to invalid strengthenings.

Original authors: Mateus de Oliveira Oliveira, Sam Urmian

Published 2026-05-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mateus de Oliveira Oliveira, Sam Urmian

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 a detective trying to solve a massive puzzle. The puzzle is a set of rules about how shapes (specifically, networks of dots and lines called "graphs") behave. Mathematicians have proposed many theories (conjectures) about these shapes, like "If a shape has no triangles, it can be colored with only X colors."

Sometimes, these theories are true. Sometimes, they are false, and if they are false, there is a specific shape that breaks the rule. This shape is called a counterexample.

For a long time, finding these counterexamples or proving the rules were true for complex shapes was like searching for a needle in a haystack the size of a galaxy. You had to check every single possible shape, one by one.

This paper introduces a new, super-smart detective tool called Width-Based Automated Theorem Proving. Here is how it works, using simple analogies:

1. The "Flat Map" Strategy (Width-Based Search)

Instead of trying to understand the whole messy galaxy of shapes at once, the researchers look at them through a specific lens called "width."

The Analogy: Imagine trying to organize a messy closet. If you just throw everything in, it's chaos. But if you organize it by "width"—say, how many hangers you can fit on a single rod at once—you can break the problem down into manageable chunks.
The Method: The tool breaks complex shapes into small, simple pieces (like a tree or a path) and checks the rules piece by piece. If a rule holds for all small pieces of a certain size, it likely holds for the whole shape. If it fails, the tool finds the specific small piece that causes the failure.

2. The Two Superpowers

The paper's main contribution is adding two "superpowers" to this detective tool to make it much faster and less wasteful.

Superpower A: State Canonization (The "Uniform" Trick)

When the detective builds a shape piece by piece, they often create the exact same shape but with the dots labeled differently (e.g., calling a dot "A" instead of "B").

The Problem: Without help, the tool would check the "A" version, then the "B" version, then the "C" version, wasting time on duplicates. It's like checking the same room in a house three times just because you walked in through different doors.
The Solution (Canonization): The tool now has a "Uniform" rule. Before checking a new shape, it instantly re-labels all the dots into a standard order (like sorting a hand of cards from Ace to King). If two shapes look the same after sorting, the tool knows they are the same and only checks one.
The Result: This cuts down the number of shapes to check by a huge amount, turning a search that might take years into one that takes hours.

Superpower B: Early Pruning (The "Dead End" Sign)

Sometimes, the tool is looking for a counterexample to a rule like: "If a shape has no triangles, it must be 3-colorable."

The Problem: The tool might start building a shape that already has a triangle. If the shape has a triangle, it no longer fits the "If no triangles" part of the rule. Checking how this shape gets colored is a waste of time because the rule doesn't even apply to it anymore.
The Solution (Early Pruning): The tool puts up a "Dead End" sign. As soon as it builds a piece that violates the "If" part (like adding a triangle), it immediately stops exploring that path. It cuts off the branch of the search tree before it grows too big.
The Result: It avoids building millions of useless shapes that don't fit the criteria, saving massive amounts of computer memory and time.

3. What They Actually Found

The researchers built a computer program called TreeWidzard to test these ideas. They didn't just talk about it; they ran it on real math problems.

Proving a Theory: They used the tool to prove Reed's Conjecture (a famous theory about coloring triangle-free shapes) for a specific group of shapes (those with "pathwidth" up to 5 and "treewidth" up to 3). The tool confirmed the theory holds true for these shapes.
Breaking a Theory: They also used the tool to find counterexamples to "strengthened" versions of the theory (claims that were too strict). The tool automatically built specific, complex shapes that proved these stricter claims were false.
The Impact: Before this, checking these theories for even small widths was often impossible due to the sheer number of possibilities. With their two superpowers (Canonization and Pruning), they reduced the search space from millions of states to just a few hundred in some cases.

Summary

Think of this paper as the invention of a smart, organized, and impatient detective.

Organized: It sorts everything so it doesn't check the same thing twice (Canonization).
Impatient: It stops investigating dead ends immediately (Early Pruning).
Effective: It successfully proved some math theories and broke others, showing that this new way of using computer algorithms to solve graph theory problems is a very promising path forward.

The authors emphasize that this is a practical step forward, showing that these complex mathematical theories can now be tested automatically on computers, something that was previously too difficult to do efficiently.

Title: State Canonization and Early Pruning in Width-Based Automated Theorem Proving

Problem Statement
Width-based automated theorem proving (ATP) is a framework designed to search for counterexamples to graph-theoretic conjectures by exploring graphs of bounded width (e.g., treewidth or pathwidth). While recent theoretical work [16] demonstrated that dynamic programming (DP) algorithms operating on tree decompositions could theoretically verify conjectures in double-exponential time relative to the width $k$ , the practical viability of this approach was unproven. The primary challenge lies in the combinatorial explosion of states during the search process. Standard DP-based searches often explore vast numbers of redundant states that are structurally identical but differ only in the labeling of interface vertices (symmetry), leading to intractable memory and time requirements even for small values of $k$ .

Methodology
The authors build upon the framework of instructive dynamic programming cores introduced in [16]. In this framework, graph properties are specified not by logical formulas (which suffer from tower-of-exponential time complexity) but by DP cores that operate on $k$ -instructive tree decompositions. These cores process decompositions from leaves to roots, maintaining sets of "local witnesses" that track the status of the property being verified.

To address the state explosion problem, the paper introduces two complementary optimization techniques:

State Canonization (Symmetry Breaking):
- Concept: The authors observe that many states in the search space are equivalent under relabeling of the active interface labels (the "bag").
- Mechanism: They define a witness action, a mathematical structure that allows local witnesses to be permuted consistently with interface relabelings. Using this, they define a canonical form for each state: the lexicographically smallest representative of its equivalence class under all possible injective relabelings.
- Implementation: The search algorithm (Algorithm 1) performs a breadth-first search where every generated successor state is immediately transformed into its canonical form before being stored or processed. This ensures that the algorithm explores the quotient space of states rather than the raw space, effectively identifying and discarding symmetric duplicates.
Early Pruning for Implications:
- Concept: Many conjectures take the form $P_1 \to P_2$ , where $P_1$ is a property closed under subgraphs (e.g., triangle-freeness, simplicity).
- Mechanism: The authors leverage the observation that if a partial graph constructed during the decomposition fails to satisfy $P_1$ (i.e., it contains a forbidden subgraph), no extension of this partial graph can satisfy $P_1$ . Consequently, no extension can serve as a counterexample to the implication (since a counterexample must satisfy $P_1$ but fail $P_2$ ).
- Implementation: The search algorithm (Algorithm 2) maintains a triple of states $(b, S_1, S_2)$ representing the interface, the witness set for $P_1$ , and the witness set for $P_2$ . If the state $S_1$ becomes inconsistent (i.e., the partial graph violates $P_1$ ), the search branch is pruned immediately, as it cannot yield a valid counterexample.

Key Contributions

Theoretical Advancement: The paper formalizes the integration of symmetry breaking and early pruning into the width-based ATP framework. It proves that these optimizations preserve the soundness and completeness of the search: a canonized, pruned refutation exists if and only if a counterexample exists within the bounded width class.
Algorithmic Implementation: The authors implemented these techniques in a tool called TreeWidzard. The tool supports the definition of DP cores for various graph properties (e.g., chromatic number, maximum degree, clique number) and executes the optimized search.
Complexity Analysis: The paper establishes that for specific conjectures like Reed's conjecture, the combined approach allows verification in time double-exponential in $O(k^2)$ , a significant practical improvement over the raw state space size.

Experimental Results
The authors evaluated their framework on Reed's Conjecture for triangle-free graphs, which posits that $\chi(G) \le \lceil (\Delta(G) + 3)/2 \rceil$ .

Counterexample Construction: The tool successfully constructed counterexamples to false strengthenings of the conjecture. For instance, it found a triangle-free graph with pathwidth 4 and chromatic number 4, disproving the claim that such graphs are 3-colorable.
Validation of Conjectures: The framework automatically validated Reed's conjecture for graphs of pathwidth at most 5 and treewidth at most 3.
Performance Metrics:
- State Reduction: The combination of canonization and early pruning yielded dramatic reductions in the search space. For pathwidth 3 and maximum degree 2, the baseline BFS explored ~24.5 million states, whereas the combined approach explored only 141 states.
- Resource Efficiency: The optimizations turned runs that previously exceeded memory limits (512 GB) or time limits (24 hours) into runs completing in seconds or minutes with memory usage under 1 GB.
- Scalability: The techniques enabled the verification of the conjecture on graphs of pathwidth 5 (a case previously intractable without these optimizations) in approximately 41.4 hours using 52 CPUs.

Significance and Claims
The paper claims to provide the first evidence that width-based automated theorem proving is a promising avenue for studying graph-theoretic conjectures. The authors emphasize that their work bridges the gap between theoretical parameterized complexity and practical automated reasoning.

Modularity: The framework allows graph theorists to utilize complex DP algorithms implemented as "plugins" without needing to understand the underlying search mechanics.
Practical Viability: The results demonstrate that the double-exponential time complexity inherent to the framework is manageable for small-to-moderate width parameters when combined with symmetry breaking and subgraph-closed pruning.
Community Impact: The authors suggest their approach facilitates a productive exchange between researchers in parameterized complexity and automated theorem proving, potentially leveraging decades of knowledge in width-based model checking for the automated verification of mathematical conjectures.

The paper remains modest in its scope, noting that these are "first steps" and that the current results are specific to the class of graphs with small treewidth/pathwidth, rather than a general solution for all graph-theoretic problems.