💻 computer science

Breaking Symmetries from a Set-Covering Perspective

This paper formalizes symmetry breaking in graphs as a set-covering problem, enabling the derivation of optimal and improved partial symmetry breaks by leveraging decades of research on set-covering techniques to address the associated computational challenges.

Original authors: Michael Codish, Mikoláš Janota

Published 2026-03-31

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Michael Codish, Mikoláš Janota

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

The Big Picture: The "Symmetry" Problem

Imagine you are a detective trying to solve a mystery involving a set of unique, handcrafted jigsaw puzzles. However, there's a catch: you can rotate or flip any puzzle, and it still looks like the same puzzle.

If you try to list every possible version of every puzzle, you will end up with millions of duplicates. For example, a puzzle rotated 90 degrees is technically a different arrangement of pieces, but it's the same puzzle. This is called symmetry.

In computer science, when trying to solve complex problems (like finding the best network layout or designing a circuit), computers get stuck because they waste time checking these millions of "rotated" duplicates. They need a way to say: "Stop! We only need to check one version of this puzzle. Ignore all the others." This is called breaking symmetry.

The Old Way: The "Brute Force" Approach

Traditionally, to stop the computer from checking duplicates, programmers add a massive list of rules.

"Don't check this version."
"Don't check that version."
"Don't check the one where the red piece is on the left."

The problem is that for complex puzzles, this list of rules becomes astronomically huge. It's like trying to write a rule for every single person in the world to stop them from entering a room, instead of just putting up a "Closed" sign. The computer gets overwhelmed by the sheer size of the rulebook.

The New Idea: The "Set-Cover" Perspective

The authors of this paper, Michael Codish and Mikoláš Janota, decided to look at the problem differently. Instead of writing rules for every single puzzle, they asked: "What is the smallest team of 'Inspectors' we need to hire to catch every single duplicate?"

Here is how their analogy works:

The Universe of Graphs: Imagine a giant library containing every possible version of every puzzle (every graph).
The Inspectors (Permutations): An "Inspector" is a specific rule (a mathematical shuffle) that says, "If you see a puzzle that looks like this, it's a duplicate of that."
- If an Inspector finds a puzzle and says, "Hey, this is just a rotated version of a smaller, simpler one," we say the Inspector covers that puzzle.
The Goal (Set Cover): We want to find the smallest possible team of Inspectors such that every single duplicate puzzle in the library is caught by at least one of them.
- If we find a team of 3 Inspectors that catches all duplicates, we don't need the other 10,000 Inspectors. We can fire them!

The Secret Weapons: How They Tamed the Giant Problem

The challenge is that the library is huge (billions of puzzles) and there are millions of potential Inspectors. You can't just check them one by one. The authors used three clever tricks to shrink the problem down to a manageable size:

1. The "Lazy Inspector" Trick (Dominance)

Imagine you have two Inspectors:

Inspector A catches 100 specific duplicates.
Inspector B catches those same 100 duplicates plus 50 more.
The Trick: Why keep Inspector A? Inspector B does everything A does, and more. We can fire Inspector A immediately. This is called Permutation Dominance. It's like firing a junior employee because the senior employee already covers their entire job description.

2. The "Easy Target" Trick (Graph Dominance)

Imagine you have a very difficult puzzle (Graph X) that is hard to catch, and a very easy puzzle (Graph Y) that is easy to catch.

If the Inspectors who catch the hard puzzle (X) automatically catch the easy puzzle (Y) as well, then we don't need to worry about Y anymore. We only need to focus on the hard ones.
This is Graph Dominance. It lets the computer ignore the "easy" duplicates and focus its energy on the tricky ones.

3. The "One-of-a-Kind" Trick (Backbones)

Sometimes, there is a very weird, specific puzzle that only one single Inspector can catch. No one else can spot it.

That Inspector is a Backbone. They are essential. You must hire them, or that one weird puzzle will slip through the cracks.
Once you hire the Backbone, you can remove all the puzzles they catch from the list, because they are now taken care of. This often reveals new Backbones among the remaining Inspectors.

The Results: Solving the Unsolvables

Using these tricks, the authors were able to solve the "Set Cover" problem for graphs up to size 10 (which is huge in this field).

Before: They had to deal with a problem involving $10!$ (3.6 million) potential rules and billions of puzzles.
After: By using the "Backbone" and "Dominance" tricks, they reduced the problem to a tiny list of just 199 rules that perfectly cover all duplicates.

Why This Matters

This paper is like finding a master key. Instead of trying to lock every door in a castle individually (which takes forever), they found a way to identify the few specific keys that lock every door automatically.

For Computer Scientists: It provides a way to create the most efficient "rulebooks" for solving complex problems, saving massive amounts of computing time.
For the Rest of Us: It shows how looking at a messy problem from a different angle (viewing it as a "covering" problem rather than a "rule" problem) can turn an impossible task into a solvable one.

In a nutshell: They turned a chaotic mountain of duplicate puzzles into a neat, tiny list of essential inspectors, ensuring computers never waste time checking the same thing twice.

1. Problem Statement

Graph search problems (e.g., finding graphs with specific structural properties) suffer from an enormous search space due to graph isomorphism. Any permutation of the vertices of a solution yields an isomorphic (symmetric) solution, leading to redundant search effort.

Goal: To restrict the search to a single "canonical" graph per isomorphism class.
Standard Approach: Symmetry breaking constraints (e.g., LexLeader) are added to the problem formulation. A complete symmetry break ensures exactly one canonical graph per class is considered.
Challenge: The standard LexLeader constraint requires a super-exponential number of constraints (one for every permutation in $S_n$ ). While compact sets of constraints exist, finding the optimal (minimal size) set of constraints for complete symmetry breaking remains a difficult open problem, particularly for graphs of order $n > 6$ .

2. Methodology: The Set-Covering Perspective

The authors propose a novel formalization of symmetry breaking as a Set-Covering Problem.

Core Definitions

Covering: A permutation $\pi$ "covers" a graph $G$ if applying $\pi$ to $G$ results in a lexicographically smaller graph ( $\pi(G) < G$ ).
Canonizing Set: A set of permutations $\Pi$ is a complete symmetry break if and only if the union of graphs covered by $\Pi$ includes all non-canonical graphs.
Optimal Symmetry Break: The problem is redefined as finding the smallest subset of permutations $\Pi \subseteq S_n$ $Π \subseteq S_{n}$ that covers the universe of all non-canonical graphs. This is a classic Set-Cover problem where:
- Universe ( $U$ ): All non-canonical graphs of order $n$ (size $\approx 2^{n(n-1)/2}$ ).
- Subsets ( $S$ ): The set of graphs covered by each non-identity permutation (size $n!$ ).

Key Technical Innovations

To tackle the intractable size of the universe and the number of subsets, the authors introduce three main mechanisms:

A. Pattern Representation (Concise Encoding)
Instead of explicitly enumerating graphs, the authors use patterns to represent the set of graphs covered by a permutation.

A permutation $\pi$ makes a graph smaller at a specific index $i$ if the lexicographic comparison fails at that position.
This condition is encoded as a set of equality constraints on the adjacency matrix variables.
Using the Most General Unifier (MGU), these constraints are condensed into a "pattern" (a partial assignment of variables).
The set of graphs covered by $\pi$ is the disjoint union of graphs matching these patterns. This allows the authors to reason about exponential sets of graphs symbolically.

B. Symbolic Optimizations (Pre-Matrix Construction)
Before constructing the massive set-cover matrix, the authors apply three optimizations symbolically using SAT solvers:

Permutation Dominance: If the set of graphs covered by $\pi_1$ is a subset of those covered by $\pi_2$ , $\pi_1$ is redundant and discarded.
Graph Dominance: If a graph $G_1$ is covered by a subset of permutations that cover $G_2$ , then $G_2$ is redundant (if $G_1$ is covered, $G_2$ is likely covered by the same or fewer permutations).
Backbone Identification: A permutation is a backbone if it is the only permutation covering a specific graph. These must be included in any optimal solution.
- Algorithm: The authors iterate over graphs (or permutations) to identify backbones. They use "leap" heuristics to skip large ranges of graphs that are already covered by existing backbones or are canonical.

C. Matrix Construction and Solving
After symbolic pruning, the remaining problem is formulated as a matrix (rows = permutations, columns = graphs).

For $n \le 9$ , the optimizations reduce the problem to an empty matrix (all graphs covered by identified backbones).
For $n=10$ , the reduced matrix is small enough (199 rows $\times$ 197 columns) to be solved as an Optimization Pseudo-Boolean (OPB) problem using the solver RoundingSat.

3. Key Contributions

Formalization: Established symmetry breaking as a Set-Cover problem, bridging graph theory with combinatorial optimization.
Pattern-Based Symbolic Reasoning: Developed a method to represent exponential sets of graphs using concise patterns, enabling the handling of dominance and backbone checks without explicit enumeration.
Optimal Solutions: Computed optimal (minimal number of lex-constraints) complete symmetry breaks for graphs of order $n \le 10$ $n \leq 10$ .
- Previous work (e.g., Codish et al., 2016) found compact sets, but not necessarily minimal ones.
- The new approach proves that the 2016 sets were within 10% of optimal for $n \le 10$ .
Partial Symmetry Breaks: Demonstrated that the set of backbone permutations alone provides a highly effective partial symmetry break.
- For $n=10$ , using only 131 backbone permutations (vs. 45 transpositions in standard approaches) reduces the redundancy ratio significantly, offering a more precise partial break with fewer constraints.

4. Results

The authors successfully computed optimal symmetry breaks for graphs up to order 10.

Order ( $n$ )	Optimal Size (Lex-Constraints)	Previous Best (2016)	Time to Solve
4	3	3	4.6s
5	6	7	0.67s
6	13	13	103s
7	35	37	~2 min
8	121	135	~15 min
9	765	842	~4.8 hours
10	7,181	7,853	~613 hours (total)

Efficiency: For $n < 10$ , the problem was solved entirely via symbolic optimizations (no general set-cover solver needed). For $n=10$ , the problem was reduced from a theoretical size of $10! \times 2^{45}$ to a manageable $199 \times 197$ matrix.
Encoding Size: The resulting symmetry breaking constraints (encoded via negated patterns) are 3 orders of magnitude smaller than direct LexLeader encodings.
Verification: All solutions were verified using the model counter GANAK to ensure they cover exactly the number of non-isomorphic graphs (OEIS sequence A000088).

5. Significance

Theoretical Advancement: This work shifts the paradigm from heuristic construction of symmetry breaking constraints to a rigorous optimization framework. It proves that finding minimal complete symmetry breaks is feasible for small-to-medium graph orders.
Practical Impact: The derived constraints are significantly more compact than previous state-of-the-art methods, which can drastically improve the performance of SAT/SMT solvers and CP solvers on graph search problems.
New Opportunities: By framing the problem as set-covering, the authors open the door to applying decades of research on exact and approximate set-cover algorithms (e.g., greedy heuristics, LP relaxations) to symmetry breaking.
Partial Breaks: The discovery that "backbones" form a powerful partial symmetry break suggests a new strategy for large-scale problems where complete breaks are intractable: compute the backbone set to get a high-precision partial break with a minimal number of constraints.

In summary, the paper successfully tames the complexity of symmetry breaking by leveraging set-cover theory, pattern-based symbolic representation, and backbone identification, achieving optimal results for graphs up to order 10.