The maximum clique problem (MCP)¶
Definition 1: The maximum clique problem
Given:
-
a simple graph \(G = (V,E)\), where
\[ V = \{1,2,\dots,n\} \]is the set of \(n\) vertices, and
\[ E \subseteq \big\{\, \{u,v\} : u,v \in V,~ u \neq v \,\big\} \]is the set of \(m\) edges,
the Maximum Clique Problem (MCP) asks to find a clique \(K \subseteq V\) of \(G\) whose number of vertices is maximum. Its optimal value is the clique number \(\omega(G)\).
Assumptions
-
We consider nontrivial instances: the graph has at least one edge and at least one non-edge. Formally:
\[ 1 \le m < \binom{n}{2}. \] -
The assumption can be made without loss of generality: if the graph has no edge, every single vertex is a maximum clique and \(\omega(G)=1\); if the graph is complete, \(V\) itself is a clique and \(\omega(G)=n\).
What the course does on this problem¶
| Technique | Where |
|---|---|
| Definition | Ch. 5 «Clique problems» |
| Formulations | Ch. 12 «Formulations of clique problems» |
| Limits of approximation | Ch. 38 «Maximum clique: limits of approximation» |
| Exercises | Ch. 4 (2 exercises); Ch. 5 (5 exercises); Ch. 12 (5 exercises); Ch. 38 (4 exercises) |
Properties¶
-
NP-hard: deciding whether a clique with \(k\) vertices exists is one of the \(21\) NP-complete problems of Karp (Ch. 5).
-
Upper bounds: degree \(\Delta+1\), edges, degree count \(k^{\max}\) and coloring \(\chi(G)\) (Ch. 5).
-
A first clique by hand: start from a vertex of maximum degree and add vertices adjacent to all those chosen (Ch. 5).
Formulations¶
-
The model \(\ILP_{\MCP}\) has one binary variable per vertex and one constraint \(x_u+x_v\le1\) per non-edge (Ch. 12).
-
\(x_v=\frac12\) for all vertices is feasible, so \(z(\LP_{\MCP})\ge n/2\): the LP bound can be arbitrarily weak (Ch. 12).
-
Clique inequalities on the stable sets of \(G\) strengthen the model, and the dual of their relaxation is a VCP relaxation: \(\omega(G)\le z(\LP^{\mathrm{CL}}_{\MCP})\le\chi(G)\) (Ch. 12).