🧩 Constraint Solving POTD:Problem of the Day: Maximum Clique Problem

[github-actions[bot]]

Problem Statement

The Maximum Clique Problem asks: given an undirected graph G = (V, E), find the largest subset of vertices C ⊆ V such that every pair of vertices in C is connected by an edge. We say C is a clique—a complete subgraph where everyone knows everyone.

Concrete Example:
Consider a social network with 6 people and these friendships:

• Alice ↔ Bob, Charlie, Diana
• Bob ↔ Alice, Charlie, Eve
• Charlie ↔ Alice, Bob, Diana, Eve
• Diana ↔ Alice, Charlie, Frank
• Eve ↔ Bob, Charlie, Frank
• Frank ↔ Diana, Eve

Can you find the largest group where all members are mutual friends? {Alice, Bob, Charlie} is a clique of size 3. Can you do better?

Input/Output Specification:

• Input: Graph G = (V, E) with n = |V| vertices and m = |E| edges
• Output: A set C ⊆ V maximizing |C| such that ∀ u, v ∈ C: (u, v) ∈ E

---

Why It Matters

Social network analysis: Identifying tight-knit communities where everyone interacts with everyone else helps platforms detect user clusters for recommendation and content moderation.

Bioinformatics: Finding cliques in protein interaction networks reveals functionally related protein complexes that work together in cellular processes.

Conflict analysis: In scheduling, a clique in a conflict graph represents a set of tasks that all mutually conflict—critical for feasibility analysis.

SAT solver optimization: Maximum clique is equivalent to maximum independent set and relates to satisfiability; solving it efficiently informs the design of SAT and SMT solvers.

---

Modeling Approaches

Approach 1: Integer Linear Programming (ILP)

Decision variables: x_v ∈ {0, 1} for each vertex v (1 if v is in the clique).

Objective: Maximize Σ x_v.

Constraints:

• Clique constraint: For each non-edge (u, v) ∉ E, we have x_u + x_v ≤ 1 (at most one of them is in the clique).
• Implications: These are often lifted to stronger cuts like x_u + x_v + x_w ≤ 2 for triangles missing from the graph.

Trade-offs: ILP is exact and benefits from decades of solver engineering. However, the linear relaxation can be weak, requiring many branch-and-bound nodes. Scalability is limited to ~1000 vertices for hardest instances.

Approach 2: Constraint Programming with Arc Consistency

Decision variables: clique[i] ∈ {0..n} for each vertex i and size ∈ {0..n} representing clique membership.

Constraints:

• Neighborhood constraint: If i and j are both in the clique, then they must be adjacent: (clique[i] = 1 ∧ clique[j] = 1) → (i, j) ∈ E.
• Cardinality: size = Σ clique[i] (total clique size).
• Ordering/symmetry breaking: Order vertices arbitrarily; use the clique as an ordered list to prune symmetric solutions.

Propagation: Domain filtering exploits neighborhood structure—if vertex i is in the clique, remove any vertex not adjacent to i from the remaining domain.

Trade-offs: CP naturally encodes reachability and global constraints. The neighborhood propagation is efficient. Local search and branch-and-bound can find good solutions quickly, though proving optimality requires exhaustive search.

Approach 3: Reduction to Maximum Independent Set

The complement graph Ḡ has an edge between u and v iff (u, v) ∉ E in G. A clique in G is an independent set in Ḡ. Solving maximum independent set on Ḡ yields the maximum clique in G. This reduction clarifies the computational complexity and enables reuse of independent-set algorithms.

Example Model (Pseudo-code)

// MiniZinc-style pseudo-code for maximum clique

int: n;                           // number of vertices
set of int: VERTICES = 1..n;
array[VERTICES, VERTICES] of bool: adj;  // adjacency matrix

array[VERTICES] of var 0..1: in_clique;  // decision variables
var 0..n: clique_size = sum(in_clique);

% Clique constraint: if both in_clique, must be adjacent
forall(i, j in VERTICES where i < j)(
  in_clique[i] + in_clique[j] <= 1 + adj[i, j] * 2
);

% Maximize clique size
maximize clique_size;

This model enforces that any pair in the clique must be adjacent. The solver searches over 2^n subsets, pruned by domain consistency.

---

Key Techniques

1. Clique Graph Representation & Neighborhood Propagation

Maintain adjacency lists for each vertex. When a vertex v enters the clique, immediately restrict remaining candidate vertices to N(v) (neighbors of v). This reduces the search space exponentially and is the backbone of practical clique-finding algorithms.

2. Branch-and-Bound with Upper Bounds

Use a greedy coloring of the remaining graph to estimate an upper bound on the maximum clique size reachable from the current partial solution. If current_size + upper_bound ≤ incumbent, prune. Also, compute lower bounds via greedy clique construction to focus the search.

3. Symmetry Breaking & Canonical Forms

Since the vertex ordering is arbitrary, many search branches explore isomorphic subproblems. Use canonical labeling (e.g., lexicographically smallest clique representation) or impose strict ordering: require vertex indices in the clique to be strictly increasing, v_1 < v_2 < ... < v_k.

---

Challenge Corner

1. Can you model this as a SAT formula? Given a target clique size k, encode "find a clique of size ≥ k" as a Boolean formula and feed it to a SAT solver. How many clauses do you need?

2. Symmetry & Certificates: A clique is its own certificate—easy to verify. But the maximum clique problem is NP-hard. Can you design a symmetry-breaking rule that doesn't discard the optimal clique?

3. Greedy vs. Optimal: A greedy algorithm picks vertices greedily if they're adjacent to all current clique members. Does this always find a maximal clique? Why or why not? Can you improve it?

4. Parameterized Complexity: For graphs with bounded degeneracy d, can you solve maximum clique faster than 2^n? What about planar graphs?

---

References

1. Rossi, F., van Beek, P., & Walsh, T. (2006). Handbook of Constraint Programming. Chapter on hard combinatorial problems. Elsevier. — Covers cliques, independent sets, and graph problems in CP.

2. Bomze, I. M., Budinich, M., Pardalos, P. M., & Pelillo, M. (1999). "The Maximum Clique Problem." In Handbook of Combinatorial Optimization. — Comprehensive survey of algorithms, complexity, and applications.

3. Konc, J., & Janežič, D. (2007). "An improved branch and bound algorithm for the maximum clique problem." MATCH Communications in Mathematical and in Computer Chemistry. — Modern practical algorithms leveraging neighborhood reduction.

4. Östergård, P. R. J. (2001). "A fast algorithm for the maximum clique problem." Discrete Applied Mathematics. — State-of-the-art exact algorithm combining bounds, pruning, and efficient data structures.

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · 6.2 AIC · ⌖ 5.49 AIC · ⊞ 6.1K · ◷

• expires on Oct 2, 2026, 3:34 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 #63611.