v. Maximum Clique and Independent Set

Maximum Clique

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.

Proof: $|\mathrm{MVC}|=n-|\mathrm{MIS}|$

$S$ is an independent set iff no edge has both endpoints in $S$ iff every edge has at least one endpoint in $V\setminus S$ iff $V\setminus S$ is a vertex cover. So $S\mapsto V\setminus S$ is a bijection between independent sets and vertex covers, reversing the size order ($|V\setminus S|=n-|S|$) — maximising $|S|$ is the same problem as minimising $|V\setminus S|=n-|S|$, giving $|\mathrm{MVC}|=n-|\mathrm{MIS}|$ directly. $■$

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.

Proof: the tree DP is correct

$\mathrm{dp}[u][0]$ is the maximum weight of an independent set in $u$‘s subtree not using $u$; $\mathrm{dp}[u][1]$ is the maximum using $u$. If $u$ is used, none of its children can be (adjacency), so each child contributes its own $\mathrm{dp}[v][0]$ — forced, not a choice, giving $\mathrm{dp}[u][1]=w_u+{\sum }_v\mathrm{dp}[v][0]$. If $u$ is not used, each child is independently free to be used or not — whichever is better — giving $\mathrm{dp}[u][0]={\sum }_v\max (\mathrm{dp}[v][0],\mathrm{dp}[v][1])$. Both recurrences only combine answers from disjoint, already-fully-solved subtrees (no edges between different children’s subtrees, since it’s a tree), so the independence assumption underlying the sums is valid, and induction on subtree size gives correctness at the root. $■$

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.

Bron-Kerbosch

Purpose: Enumerate all maximal cliques of an undirected graph. With pivoting, it runs in $O(3^{n/3})$ — which is optimal, because a graph can have that many maximal cliques (Moon-Moser).

Algorithm

Recursive backtracking on three sets:

• $R$ — the clique built so far,
• $P$ — candidates that can still extend $R$,
• $X$ — vertices already processed (used to avoid reporting the same clique twice).

BronKerbosch(R, P, X):
    if P and X are both empty:
        report R as a maximal clique
    choose a pivot u from P ∪ X maximising |P ∩ N(u)|
    for each v in P \ N(u):
        BronKerbosch(R ∪ {v}, P ∩ N(v), X ∩ N(v))
        P ← P \ {v}
        X ← X ∪ {v}

Why the pivot. Any maximal clique must contain either $u$ or a vertex not adjacent to $u$. So it suffices to branch on $P\setminus N(u)$, and choosing $u$ to maximise $|P\cap N(u)|$ makes that set as small as possible. Without pivoting the algorithm still works but is dramatically slower.

Code

Bitset version — the one to use, since all set operations become single machine words:

int n;
vector<unsigned long long> adj;   // adj[v] = bitmask of neighbours (n <= 64)
vector<unsigned long long> cliques;
 
void bk(unsigned long long R, unsigned long long P, unsigned long long X) {
    if (!P && !X) { cliques.push_back(R); return; }
 
    // pivot: vertex of P|X with the most neighbours inside P
    int pivot = -1, best = -1;
    unsigned long long PX = P | X;
    for (unsigned long long t = PX; t; t &= t - 1) {
        int u = __builtin_ctzll(t);
        int c = __builtin_popcountll(P & adj[u]);
        if (c > best) { best = c; pivot = u; }
    }
 
    unsigned long long cand = P & ~adj[pivot];
    for (unsigned long long t = cand; t; t &= t - 1) {
        int v = __builtin_ctzll(t);
        bk(R | (1ULL << v), P & adj[v], X & adj[v]);
        P &= ~(1ULL << v);
        X |= (1ULL << v);
    }
}

Complexity

• Time: $O(3^{n/3})$ worst case with pivoting — matching the maximum possible number of maximal cliques
• With a degeneracy ordering at the top level: $O(dn{3}^{d/3})$ where $d$ is the graph degeneracy — near-linear on sparse real-world graphs
• Space: $O(n^2/64)$ for the adjacency bitsets, $O(n)$ recursion depth

Proof: Bron-Kerbosch is correct and the pivot is sound

Every reported $R$ is a clique: by construction, each vertex added to $R$ was drawn from $P\subseteq N(v)$ for every $v$ already in $R$, i.e. adjacent to all of $R$ before being added.
Maximality: reported exactly when $P\cup X=\varnothing$ — $P$ empty means no remaining candidate is adjacent to all of $R$ (so $R$ cannot be extended using an unprocessed vertex), and $X=\varnothing$ additionally confirms no already-processed vertex could have extended it either (ruling out the case where $R$ is extendable but only by a vertex this branch already tried and rejected elsewhere) — together, no vertex in the whole graph is adjacent to all of $R$, the definition of maximal.
No duplicates: once $v$ moves from $P$ to $X$ (after the branch including $v$ at this level completes), every subsequent branch at this level explicitly excludes $v$ from $P$ but still carries it in $X$; so if some later branch’s final $R$ would also admit $v$ as an extension, it finds $v\in X$ at its reporting check and is correctly suppressed as non-maximal from this branch’s perspective — $v$‘s clique was already (or will be) reported via the branch that included it.
The pivot is sound: fix any pivot $u\in P\cup X$. Every maximal clique extending $R$ either contains $u$ (handled when $v=u$ is tried as part of some other branch’s candidate set elsewhere, or trivially if $u$ ends up added through recursion) or does not contain $u$ — but if it doesn’t contain $u$, since $u\in P\cup X$ means $u$ is a valid candidate at this level, the clique must contain some vertex not adjacent to $u$ (else the clique plus $u$ would still be a clique, contradicting that the original was maximal without $u$ unless $u$ itself couldn’t extend it, which is exactly “not adjacent to some member”). So restricting the branching loop to $P\setminus N(u)$ still reaches every maximal clique — branches through $N(u)\cap P$ are redundant because any clique achievable there is also achievable (and will be found) via a branch that doesn’t go through $u$-adjacent vertices first. Choosing $u$ to maximise $|P\cap N(u)|$ minimises $|P\setminus N(u)|$, the number of branches taken, without losing completeness. $■$

Variants / Use Cases

• Maximum clique — take the largest reported clique, or use a dedicated branch-and-bound solver with a colouring bound (much faster when you only need the maximum)
• Maximum independent set — run on the complement graph
• Minimum vertex cover — $n$ minus the maximum independent set (König’s theorem gives a flow solution in bipartite graphs)
• Graph colouring lower bounds — the clique number bounds the chromatic number from below
• Community detection / social network analysis — the original motivation for degeneracy-ordered Bron-Kerbosch
• Maximum Clique and Independent Set — the topic page