Presented at AAAI-23, this research bridges a significant gap between Parameterized Complexity (specifically model checking) and Automated Theorem Proving (ATP). The authors provide a formal framework to automatically verify whether long-standing graph theory conjectures hold true for all graphs within a certain "width" (such as treewidth or cliquewidth).
The Width-Based ATP Problem
In graph theory, many famous conjectures—like Tutte’s 5-flow conjecture or Hadwiger’s conjecture—remain unsolved in the general case. Mathematicians often seek insights by testing these conjectures on restricted classes of graphs, such as trees or planar graphs.
Computationally, this is the Width-Based ATP problem: Given a property $\mathbb{P}$ and an integer $k$, is it true that every graph with width at most $k$ satisfies property $\mathbb{P}$? While tools for Model Checking (verifying a property for a single graph) are well-developed, proving a statement for an entire class of graphs is significantly more difficult. Previous methods relied on Monadic Second-Order (MSO) logic, which results in "tower-of-exponentials" time complexities, making them practically unusable.
Methods: Treelike Dynamic Programming Cores
The authors introduce a modular framework that converts dynamic programming (DP) algorithms used for model checking into tools for automated theorem proving. The core of this approach is the Treelike Dynamic Programming Core (DP-core).
- Treelike Width Measures: Width measures like treewidth are represented as "tree languages," where graphs are built through a sequence of operations.
- DP-Cores: Instead of logic formulas, graph properties are described using DP. A DP-core defines how "local witnesses" (partial solutions) are updated as one traverses a tree decomposition.
- The Inclusion Test: By treating the DP-core as a tree automaton, the problem of universal verification becomes a subset-checking problem between tree languages.
Key Results and Complexity Shift
The most significant theoretical contribution is the reduction in complexity. By moving from MSO logic to DP-cores, the authors reduce the upper bound for verifying conjectures from a "tower of exponentials" to a double-exponential $2^{2^{O(k)}}$.
The framework is "plug-and-play": any graph property with a coherent DP algorithm can be dropped into the framework for theorem proving. The paper provides analytical upper bounds for several major properties and conjectures.
For example, the authors show that for a fixed number of colors $c$, Hadwiger’s Conjecture can be verified for graphs of treewidth $k$ in $2^{2^{O(k \log k + c^2)}}$ time. Similarly, Tutte’s Flow Conjectures (3-flow, 4-flow, and 5-flow) can all be tested on graphs of treewidth $k$ in double-exponential time.
Limitations and Future Outlook
While a double-exponential bound is a massive theoretical improvement, $2^{2^k}$ remains extremely large for practical computation beyond very small values of $k$. Currently, these results are most impactful for Proof Theory, providing bounds on the size of potential proofs.
Furthermore, the method is restricted to Bounded Width graphs. It cannot prove a conjecture for all graphs where $k$ is unbounded. However, since many difficult problems are tackled by incrementally increasing width, this remains a standard and highly valuable approach in discrete mathematics and computer science.
Summary updated