Skip to content

Clique problems

Catalogue of combinatorial problems · Catalogue (PDF)

  • Given an undirected graph \(G=(V,E)\), a clique is a subset of pairwise adjacent vertices; the objective is to maximize its cardinality \(\omega(G)\), or a weight of its vertices or edges.

  • A stable set of \(G\) is a clique of the complement graph \(\bar G\), so the maximum stable set problem belongs to the same family.

Problem Acronym Difference
Maximum clique problem MCP The central problem of the family.
Maximum stable set problem MSSP A subset is a clique of \(G\) if and only if it is a stable set of \(\overline{G}\): \(\omega(G) = \alpha(\overline{G})\) and \(\alpha(G) = \omega(\overline{G})\).
Vertex-weighted maximum clique problem VWMCP With all the weights \(w_v=1\) it is the MCP.
Edge-weighted maximum clique problem EWMCP With \(r_{uv}=1\) it is again the MCP, since \(r(K)=\binom{|K|}{2}\) grows with \(|K|\).