Maximum Clique and Independent Set

A clique is a set of pairwise adjacent vertices; an independent set is a set of pairwise non-adjacent vertices. They are the same problem on complementary graphs:

$\text{clique in }G=\text{independent set in }\overline{G}.$

And minimum vertex cover is the complement of a maximum independent set:

$|\mathrm{MVC}|=n-|\mathrm{MIS}|.$

All three are NP-hard in general.

The tractable cases

Graph class	Complexity
Bipartite	P — König: MVC = max matching, MIS = $n$ − max matching
Tree	P — linear tree DP
Interval graph	P — greedy by right endpoint
Chordal graph	P — perfect elimination ordering
Perfect graph	P (via SDP; impractical but polynomial)
Planar	still NP-hard, but has a PTAS
Bounded treewidth	P — DP over a tree decomposition
General	NP-hard, inapproximable within $n^{1-\epsilon }$

Check for bipartiteness first. A great many “select a maximum set with no two conflicting” problems are secretly bipartite matching.

Tree DP for maximum weight independent set

void dfs(int u, int p) {
    dp[u][0] = 0; dp[u][1] = w[u];
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        dp[u][0] += max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0];                          // v cannot be chosen
    }
}
// answer: max(dp[root][0], dp[root][1])

$O(n)$. See Tree DP.

Exact algorithms for general graphs

Method	Time	Feasible $n$
Brute force over subsets	$O(2^n{n}^2)$	20
Bron-Kerbosch with pivoting	$O(3^{n/3})$	40-60
Bron-Kerbosch with bitsets	$O(3^{n/3})$, tiny constant	100-150
Branch and bound with a colouring bound	exponential, strong pruning	100-1000 (sparse)
Meet in the middle	$O(2^{n/2})$	40-50
Degeneracy-ordered Bron-Kerbosch	$O(dn{3}^{d/3})$	large sparse graphs

$3^{n/3}$ is the maximum possible number of maximal cliques (Moon-Moser), so Bron-Kerbosch is worst-case optimal for enumeration.

Meet in the middle for max independent set

Split the vertices into halves $A$ and $B$ ($n/2$ each):

1. Enumerate all independent subsets of $A$.
2. For each subset $S\subseteq A$, compute the set of $B$-vertices compatible with it (a bitmask AND).
3. Precompute, for every subset of $B$, the maximum-weight independent subset within it — an $O(2^{n/2})$ SOS-style DP over supersets.
4. Combine.

$O(2^{n/2}\cdot n)$ — handles $n\approx 45$. See Meet in the Middle.

The colouring bound

The key pruning for branch and bound: greedily colour the candidate set; a clique within it cannot exceed the number of colours used.

// order candidates by greedy colouring; prune when
// current_clique_size + colours_remaining <= best

Cheap to compute, and far tighter than “candidate count”. It is what makes modern max-clique solvers handle graphs with hundreds of vertices.

Bitset representation

For $n\le 128$, store each vertex’s neighbourhood as a bitset. Then $P\cap N(u)$ is one AND, and iterating the candidates uses _Find_next:

bitset<128> adj[128];
bitset<128> newP = P & adj[v];                          // O(n/64)

This is a 64× speedup and is what turns Bron-Kerbosch from "$n\le 40$" into "$n\le 150$". See Bitset Optimization.

Approximation and hardness

Problem	Best known	Hardness
Max clique	$O(n/{\log }^{2}n)$	$n^{1-\epsilon }$ inapproximable
Max independent set	same	same
Min vertex cover	2	no better than 1.36 (2 under UGC)
MIS on bounded-degree $\Delta$	$O(\Delta \log \log \Delta /\log \Delta )$

Independent set is one of the hardest problems to approximate; vertex cover, its complement, is one of the easiest. The asymmetry comes from the objective: a 2-approximation for a small cover corresponds to a terrible approximation for the large complementary set.

Parameterized results

Vertex cover is FPT: $O(1.28^k+kn)$ for a cover of size $k$, via branching on an uncovered edge plus kernelisation to $O(k^2)$ vertices. Independent set (parameterized by solution size) is W[1]-hard — no FPT algorithm expected. See Parameterized Complexity.

See also: Bron-Kerbosch · Bipartite Matching · Parameterized Complexity