Chapter 14 · Special Topics
Independent Sets, Cliques, and Treewidth
Why maximum independent set is hopeless in general, what makes it easy on trees, chordal graphs and bounded-treewidth graphs, and the two approximations that are worth coding.
#The two problems, and how they differ
Independent set: α(G) = max |S| with no edge inside S. Clique: ω(G) = α(bar G). Vertex cover: τ(G) = min |C| touching every edge, with α + τ = n always. All three are NP-hard in general (The NP-complete Graph Problems Worth Knowing), and all three become polynomial on the four graph classes below.
#Where it becomes easy
Where it becomes easy — and the exact reason
- trees / forests: DP with two states per vertex,
dp[v][0/1]= best with v excluded/included, combined over children — Distance, Radius, Eccentricity verbatim, O(n); also maximum matching by König gives α on bipartite graphs, and on a tree the two approaches agree (Kőnig + matching DP), - bipartite graphs: α = n - ν where ν is the maximum matching (König's theorem, Kőnig's Theorem and Minimum Covers) — the cover side is polynomial, so the independent set is too,
- chordal graphs (every cycle of length ≥ 4 has a chord): χ = ω and both are found by a perfect elimination ordering (PEO) — repeatedly delete a vertex whose later neighbours form a clique; maximum clique = maxv (deglater(v) + 1), and α = the minimum number of cliques covering V; all in O(n+m) via maximum cardinality search (lexBFS choosing the vertex with the most already-numbered neighbours),
- bounded treewidth k: DP over a tree decomposition with 2k+1 states per bag, O(2k n) — the single most powerful "easy" case, because it also handles dominating set, colouring, Steiner tree, Hamiltonian cycle (for fixed k) with the same skeleton,
- interval graphs (a chordal special case): greedy by right endpoint gives maximum independent set in O(n log n), and it is the "select the most non-overlapping intervals" problem — not a graph algorithm at all, once you see the structure.
#Greedy guarantees and their limits
Repeatedly take the vertex of minimum degree, delete it and its neighbours: the result is an independent set of size ≥ ∑v (1)/(deg(v)+1) ≥ (n)/(bar d + 1) (Caro–Wei / Turán). No polynomial-time algorithm achieves a better than O(n loglog n / log n) approximation ratio unless P = NP, and on general graphs the greedy bound is within a logarithmic factor of the best possible — so greedy is "the right answer" up to logs.
Order the vertices uniformly at random and select each vertex that comes before all of its neighbours: the probability is exactly (1)/(deg(v)+1) (of the vertices in N[v], each is equally likely to be first), so the expected selected set has that size and is independent by construction. ∎
#Trees: the two-state DP
// O(n) on a tree; the same two-state skeleton works for vertex cover and dominating set
// (dominating set needs three states: in / covered-by-child / must-be-covered-by-parent)
long long dp[n][2];
void dfs(int v, int p) {
dp[v][0] = 0; dp[v][1] = 1;
for (int to : g[v]) if (to != p) {
dfs(to, v);
dp[v][0] += max(dp[to][0], dp[to][1]); // v out: child free
dp[v][1] += dp[to][0]; // v in: children must be out
}
}#Treewidth, in one paragraph
A tree decomposition of G is a tree of bags B1..Bt ⊆ V with (i) every vertex in some bag, (ii) every edge inside some bag, (iii) for each vertex, the bags containing it induce a connected subtree. The width is max |Bi| - 1, and tw(G) is the minimum. Trees have tw 1, series-parallel 2, outerplanar 2, planar graphs up to Θ(√n), cliques n-1. Then: any "MSO-definable" or "state-per-vertex" problem is O(f(k) · n) on graphs of tw k, by the same DP over the decomposition — which is precisely why Escape Routes: What To Do When It Is NP-Hard's "parameterise by structure instead of by n" works. Computing treewidth is NP-hard, but 4-approximation is easy and exact O(2k n) algorithms exist for fixed k (minimal triangulations / elimination orderings: tw(G) = minorderings maxv (later neighbours forming a clique - 1), i.e. the chordal-completion problem).
#Four missteps
- Confusing maximal with maximum: a maximal independent set (cannot be extended) has size ≥ (n)/(Δ + 1) and is computable in O(n+m), but it can be Δ times smaller than α — several problems accept "maximal" and their solutions are just the greedy loop, so read the word carefully,
- Using α + τ = n on edges instead of vertices: the edge analogue is a different identity — in a graph with no isolated vertices, (maximum matching size) + (minimum edge-cover size) = n, while "minimum set of edges touching every vertex" and "maximum independent set" are unrelated by a formula. And "minimum set of edges touching every edge" (an edge cover of the line graph) is vertex-cover territory again, so name which object you mean,
- Forgetting the complement: on sparse graphs, clique problems are easier on bar G only if bar G is also structured; "find a triangle" is O(nω) or O(m3/2) — not an independent-set DP,
- Assuming DP over subsets for α is fine at n = 40: it is 2n — Escape Routes: What To Do When It Is NP-Hard's measure-and-conquer gives O(1.1996n), and the practical bound for a contest is n ≤ 45 with meet-in-the-middle on a bipartition of the vertex set (maximum independent set = maximum clique in the complement = "largest set with no edge" solved by splitting into two halves and using subset convolution over one side, O(2n/2 n), which does pass at n ≤ 46).
#Two variants, two worlds
"Maximum independent set in a disk intersection graph" admits a PTAS (shifted-quadrature / separator-based schemes — planar-like structure again), while "in 3-uniform hypergraphs" is hard to approximate within n1-ε. "Maximum independent set in a planar graph" has a PTAS; the same problem on K5-minor-free graphs also does; on general graphs even n1-ε-approximation is NP-hard (Håstad). The lesson for a contestant: if the statement's graph has a geometric or planar flavour, the structure (separators, four-colour, Euler's bound) is the intended tool, and the general NP-hardness is irrelevant.