The 3-Decomposition Conjecture: A SAT-Based Approach with Specialized Propagators

Tianwei Zhang, Stefan SzeiderCP 2025 · DOI

TL;DR

This paper tackles the 3-Decomposition Conjecture, a long-standing problem in graph theory, by employing a sophisticated SAT-solving approach. They successfully verify the conjecture for all connected cubic graphs up to 28 vertices, a significant leap from previous bounds, and introduce novel techniques for pruning the search space using forbidden subgraphs.

What Problem Does This Paper Address?

The 3-Decomposition Conjecture posits that every connected cubic graph (a graph where every vertex has exactly three neighbors) can be decomposed into three specific types of edge-disjoint subgraphs: a spanning tree, a collection of cycles, and a matching. While this conjecture has been verified for certain classes of graphs (e.g., planar, Hamiltonian), it remains open for the vast majority of cubic graphs. Verifying such conjectures often involves an exhaustive search through an exponentially growing number of graphs, making brute-force approaches infeasible for larger graph sizes. This paper aims to overcome this computational barrier by developing an efficient, constraint-based method to verify the conjecture for a much larger range of graphs.

Methods

The core of the paper's methodology lies in leveraging a SAT (Satisfiability) solver, specifically within the Satisfiability Modulo Symmetries (SMS) framework. This framework is augmented with "specialized propagators" – custom modules that add constraints to the SAT solver.

Key techniques include:

  • SAT Modulo Symmetries (SMS): This framework combines a CDCL (Conflict-Driven Clause Learning) SAT solver with external propagators. It's designed for enumerating graphs with specific properties while efficiently handling graph symmetries.
  • Specialized Propagators:
    • Minimality Check: Filters out non-canonical graph representations early in the search.
  • Forbidden (Partial) Subgraphs Check: This is a crucial innovation. It uses the Glasgow Subgraph Solver (GSS) to dynamically identify and forbid specific graph structures (subgraphs or partially defined subgraphs) that cannot appear in a minimal counterexample to the conjecture. This significantly prunes the search space.
  • Spanning Tree Check & 3-Decomposability Check: These propagators are designed to filter out graphs that cannot have a 3-decomposition based on properties of potential spanning trees.
  • Reducible Extensions: The paper introduces and utilizes the concept of "reducible extensions" of templates. These are specific graph structures that, if found in a counterexample, guarantee the existence of a smaller counterexample. By identifying and forbidding these reducible extensions, the search for minimal counterexamples becomes more efficient.
  • Dynamic Constraint Generation: Instead of pre-defining all constraints, the approach dynamically discovers and applies forbidden subgraph constraints as the search progresses, making it more adaptive and powerful.

Datasets

The paper does not use traditional "datasets" in the machine learning sense. Instead, it generates and tests cubic graphs of increasing sizes (from n=4 up to n=28). The "benchmark" is the set of all connected cubic graphs up to a certain number of vertices. The paper also systematically computes lists of "reducible templates" and "forbidden (partial) subgraphs" which can be seen as derived datasets used to guide the search.

Key Insights and Ideas

  • The Power of Forbidden Subgraphs: The most significant insight is the effectiveness of dynamically identifying and forbidding specific graph structures (reducible extensions) to prune the search space for minimal counterexamples. This "learn-as-you-go" paradigm is highly effective.
  • Trade-off in Propagator Usage: The paper experimentally demonstrates a trade-off between the frequency of calling the forbidden subgraph propagators and the overall search time. Too frequent calls can slow down the search, while too infrequent calls reduce pruning effectiveness.
  • Partial Subgraphs vs. Subgraphs: Forbidding "subgraphs" (unlabeled) generally proved more efficient than forbidding "partial subgraphs" (labeled), despite partial subgraphs offering more concise pruning rules. This is attributed to the overhead of subgraph isomorphism testing for partial subgraphs.
  • Extending SMS: The work showcases how the SMS framework can be extended with custom propagators to tackle complex combinatorial problems beyond simple graph enumeration.

Key Results

  • Verification up to 28 Vertices: The 3-Decomposition Conjecture has been verified for all connected cubic graphs up to 28 vertices. This is a substantial increase from the previous bound of 20 vertices.
  • Identification of Reducible Templates: The paper systematically identifies reducible templates (patterns that cannot appear in minimal counterexamples) up to order 18 and index 6.
  • Performance Gains: The use of forbidden subgraph constraints significantly speeds up the search process. For instance, the time to verify graphs up to n=28 is drastically reduced compared to a naive generate-and-test approach. Table 1 shows the dramatic increase in time for larger n without these techniques.
  • Experimental Analysis: The paper provides detailed experimental data on the impact of different propagator configurations and the number of forbidden subgraphs on solving efficiency.

Limitations and Future Work

  • Computational Cost: While significantly improved, verifying larger graphs still requires substantial computational resources, as indicated by the time taken for n=28 (approximately 4 years).
  • Automated Proof Verification: The authors suggest future work on implementing a systematic and automated way to verify the proofs and certificates generated by the SMS framework and its propagators. This would involve integrating tools like DRAT for proof checking and developing verifiers for each propagator's output.
  • Generalizing the Approach: The authors believe their dynamic forbidden subgraph approach can be extended to other graph conjecture verification tasks and combinatorial problems in extremal graph theory and Ramsey theory.

Summary updated

BibTeX
@inproceedings{zhang2025decomposition,
  author = {Tianwei Zhang and Stefan Szeider},
  title = {{The 3-Decomposition Conjecture: A SAT-Based Approach with Specialized Propagators}},
  booktitle = {CP},
  year = {2025},
  doi = {10.4230/lipics.cp.2025.39},
}
Figure