🧩 Constraint Solving POTD:Problem of the Day: Graph Isomorphism via SAT/SMT

[github-actions[bot]]

Problem Statement

Graph Isomorphism asks: given two graphs G and H, do they have identical structure? More formally, is there a bijection (one-to-one mapping) between their vertices such that two vertices are adjacent in G if and only if their images are adjacent in H?

Concrete instance:
Consider two 4-vertex graphs:

• G: edges {(0,1), (1,2), (2,3), (3,0), (0,2)}
• H: edges {(a,b), (b,c), (c,d), (d,a), (a,c)}

Is G ≅ H? (Can we find a permutation that makes their adjacency structures identical?)

Input & Output:

• Input: Two graphs (adjacency lists or matrices)
• Output: YES/NO or an explicit isomorphism (permutation π) if one exists

---

Why It Matters

Computational Complexity: Graph isomorphism occupies a unique complexity position—neither known to be in P nor NP-complete, despite decades of study. It has motivated new algorithmic paradigms.

Real-world Applications:

• Cheminformatics: Checking whether two molecular structures are identical (same connectivity, different 3D orientation)
• Pattern Recognition: Detecting duplicate patterns in networks (social graphs, citation networks, protein interaction networks)
• Database Query Optimization: Identifying isomorphic subgraph queries to reuse cached results
• Hardware Verification: Confirming that two circuit designs are functionally equivalent

---

Modeling Approaches

Approach 1: Constraint Programming (Permutation-Based)

Paradigm: Discrete constraint satisfaction with global constraints.

Decision variables:
Let π[i] denote the image of vertex i from G in H (a permutation). Each π[i] ∈ {0, 1, ..., n-1}, with all-different constraint.

Constraints:

π[i] ≠ π[j]  for all i ≠ j              # π is a permutation
(i, j) ∈ E_G  ⟺  (π[i], π[j]) ∈ E_H    # adjacency preserved

Trade-offs:

• ✓ Expressive: naturally captures the permutation semantics
• ✓ Strong propagation: all-different and transitivity via constraint checkers
• ✗ Search space huge: n! permutations to explore (requires good variable ordering)
• ✗ Limited by memory for n > 10,000

Key strength: Symmetry breaking is straightforward—fix π[0] = 0 and order-by-degree heuristics reduce search space dramatically.

Approach 2: SAT Encoding

Paradigm: Boolean satisfiability via CNF reduction.

Decision variables:
x[i,j] = true iff vertex i ∈ V_G maps to vertex j ∈ V_H.

Constraints (encoded as clauses):

(1) Each vertex maps exactly once:
    ∑_j x[i,j] = 1  for each i ∈ V_G
    
(2) Each target vertex receives at most one pre-image:
    ∑_i x[i,j] ≤ 1  for each j ∈ V_H
    
(3) Adjacency preservation:
    If (i1, i2) ∈ E_G and (i1 maps to j1, i2 maps to j2):
    (x[i1, j1] ∧ x[i2, j2]) ⟹ ((j1, j2) ∈ E_H)
    Negated: ¬x[i1, j1] ∨ ¬x[i2, j2] ∨ (j1, j2) ∈ E_H

Trade-offs:

• ✓ Leverages fast SAT solvers (CDCL, learned clauses)
• ✓ Scales reasonably for n ≤ 1,000 with good symmetry-breaking
• ✗ Clause explosion: quadratic in graph density
• ✗ Less intuitive variable semantics (harder to prune manually)

Key strength: CDCL conflict analysis learns global patterns, avoiding redundant search branches.

Approach 3: SMT (Satisfiability Modulo Theories)

Paradigm: SAT with integer linear arithmetic and uninterpreted functions.

Idea: Use SMT solver with bitvector or finite-domain theories to encode permutation constraints more naturally than raw CNF:

assert(forall i: π[i] ∈ [0, n-1])
assert(forall i j: i ≠ j ⟹ π[i] ≠ π[j])  # permutation via theory
assert(forall (i1, i2) ∈ E_G: (π[i1], π[i2]) ∈ E_H)

Trade-offs:

• ✓ Closer to the mathematical formulation
• ✓ Theory solvers handle permutation reasoning efficiently
• ✓ Easier to extend with additional constraints (e.g., degree preserving)
• ✗ Solver availability narrower than SAT (Z3, CVC5)
• ✗ Overhead for theory reasoning if graph is very dense

---

Modeling Approaches

Example Model (MiniZinc - Constraint Programming)

% Graph Isomorphism via MiniZinc
int: n;
array[1..n, 1..n] of int: adjG;  % adjacency matrix of G
array[1..n, 1..n] of int: adjH;  % adjacency matrix of H

array[1..n] of var 1..n: pi;     % permutation: pi[i] = image of vertex i

% All-different: π is a permutation
constraint alldifferent(pi);

% Adjacency constraint: edge (i,j) in G ⟹ edge (π[i], π[j]) in H
constraint forall(i, j in 1..n where i < j and adjG[i,j] = 1)(
  adjH[pi[i], pi[j]] = 1
);

% Non-adjacency constraint: non-edge (i,j) in G ⟹ non-edge in H
constraint forall(i, j in 1..n where i < j and adjG[i,j] = 0)(
  adjH[pi[i], pi[j]] = 0
);

% Symmetry breaking: fix first vertex
constraint pi[1] = 1;

solve satisfy;
output ["Isomorphism: ", show(pi)];

---

Key Techniques

1. Symmetry Breaking

Graph isomorphism exhibits heavy symmetry (multiple valid isomorphisms for symmetric graphs). Breaking symmetry early is critical:

• Degree-based ordering: Vertices with unique degrees must map to themselves
• Canonical labeling: Use graph invariants (e.g., iterative refinement by neighborhood) to impose a canonical form on both graphs before solving
• Lex-leader constraints: Force π to be lexicographically minimal

2. Constraint Propagation & Feasibility Pruning

• Arc consistency (AC-3/AC-4): For each pair (i, j), prune infeasible mappings by checking if neighbors of i can map to neighbors of π[i]
• Advanced propagation: Global all-different reachability, matching theory (Hall's theorem)
• Local consistency checks: If vertex i must map to j, propagate degree, neighborhood size, and spectral properties

3. Sophisticated Search Strategies

• Variable ordering heuristics: Order vertices by degree or other centrality measures; assign high-degree vertices first
• Value ordering: Given vertex i, try mapping to vertices j in H that maximize remaining feasible options (minimum-remaining-values heuristic)
• Restarts with clause learning (SAT): Periodically restart with accumulated learned clauses to escape plateaus
• Backjumping: Upon conflict, jump to the highest relevant decision level, not just the immediate parent

---

Challenge Corner

Questions for readers:

1. Symmetry Reduction: The graph isomorphism problem has automorphism groups that can be exponentially large. Can you design a refinement procedure that partitions vertices by their "role" in the graph structure and dramatically reduce the search space?

2. Spectral Insights: Isomorphic graphs have the same eigenvalues (spectrum) of their adjacency matrices. How could you use spectral information (e.g., eigenvalue multiplicity, eigenvector structure) to prune candidate mappings before solving?

3. Extension to Graph Monomorphism: How would you modify your model if the goal were not full isomorphism but a monomorphism (injective homomorphism)—finding if G "embeds" into H as a subgraph? What new constraints would help?

---

References

1. Babai, L. (2016). Graph Isomorphism in Quasipolynomial Time. In Proc. 48th STOC. A landmark result showing GI can be solved in quasipolynomial time.

2. Foggia, P., Sansone, C., & Vento, M. (2001). Graph Matching: A Fast Algorithm and Its Evaluation on 3D Face Databases. In IEEE Transactions on Pattern Analysis and Machine Intelligence. Practical algorithms for graph matching with industrial applications.

3. Rossi, F., van Beek, P., & Walsh, T. (Eds.) (2006). Handbook of Constraint Programming. Chapter 18 covers CSP approaches to combinatorial problems, including graph isomorphism encodings.

4. Järvisalo, M., & Heule, M. (2013). Inprocessing Techniques for SAT. A survey of SAT solver techniques applicable to highly symmetric problems like isomorphism.

---

Next time: Stay tuned for tomorrow's problem in the Packing & Cutting category!

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · ~10 AIC · ⌖ ~7 AIC · ⊞ 6.5K · ◷

• expires on Oct 31, 2026, 3:35 AM UTC-08:00

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #71869.