---
title: "Independent Sets, Cliques, and Treewidth"
summary: 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.
difficulty: hard
tags: [independent set, clique, treewidth, np-hard]
prereq: [complexity/npc-graphs, trees/distance]
see: [complexity/escape, trees/distance]
---

## The two problems, and how they differ

:::definition label="The problems"
**Independent set**: $\alpha(G) = \max |S|$ with no edge inside $S$. **Clique**: $\omega(G) = \alpha(\bar G)$. **Vertex cover**: $\tau(G) = \min |C|$ touching every edge, with $\alpha + \tau = n$ always. All three are NP-hard in general (@complexity/npc-graphs), and all three become polynomial on the four graph classes below.
:::

## Where it becomes easy

:::props title="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 — @trees/distance verbatim, $O(n)$; also maximum matching by König gives $\alpha$ on *bipartite* graphs, and on a tree the two approaches agree (Kőnig + matching DP),
- **bipartite graphs**: $\alpha = n - \nu$ where $\nu$ is the maximum matching (König's theorem, @matching/konig) — the cover side is polynomial, so the independent set is too,
- **chordal graphs** (every cycle of length ≥ 4 has a chord): $\chi = \omega$ and both are found by a **perfect elimination ordering** (PEO) — repeatedly delete a vertex whose later neighbours form a clique; maximum clique = $\max_v (\deg_{\text{later}}(v) + 1)$, and $\alpha$ = 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 $2^{k+1}$ states per bag, $O(2^k 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

:::theorem title="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 $\ge \sum_v \frac{1}{\deg(v)+1} \ge \frac{n}{\bar d + 1}$ (**Caro–Wei / Turán**). No polynomial-time algorithm achieves a better than $O(n \log\log 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.
:::

:::proof of the bound
Order the vertices uniformly at random and select each vertex that comes before all of its neighbours: the probability is exactly $\frac{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

```cpp max-independent-tree.cpp
// 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

:::note title="Treewidth in one paragraph, since it is the useful generalisation"
A **tree decomposition** of $G$ is a tree of bags $B_1..B_t \subseteq 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 |B_i| - 1$, and $\mathrm{tw}(G)$ is the minimum. Trees have tw 1, series-parallel 2, outerplanar 2, planar graphs up to $\Theta(\sqrt n)$, cliques $n-1$. Then: any "MSO-definable" or "state-per-vertex" problem is $O(f(k) \cdot n)$ on graphs of tw $k$, by the same DP over the decomposition — which is precisely why @complexity/escape's "parameterise by structure instead of by $n$" works. Computing treewidth is NP-hard, but 4-approximation is easy and exact $O(2^k n)$ algorithms exist for fixed $k$ (minimal triangulations / elimination orderings: $\mathrm{tw}(G) = \min_{\text{orderings}} \max_v (\text{later neighbours forming a clique} - 1)$, i.e. the chordal-completion problem).
:::

## Four missteps

:::warning title="The four missteps"
1. **Confusing maximal with maximum**: a maximal independent set (cannot be extended) has size $\ge \frac{n}{\Delta + 1}$ and is computable in $O(n+m)$, but it can be $\Delta$ times smaller than $\alpha$ — several problems accept "maximal" and their solutions are just the greedy loop, so read the word carefully,
2. **Using $\alpha + \tau = 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,
3. **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^\omega)$ or $O(m^{3/2})$ — not an independent-set DP,
4. **Assuming DP over subsets for $\alpha$ is fine at $n = 40$**: it is $2^n$ — @complexity/escape's measure-and-conquer gives $O(1.1996^n)$, and the practical bound for a contest is $n \le 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(2^{n/2} n)$, which does pass at $n \le 46$).
:::

## Two variants, two worlds

:::example title="Hardness is fragile: 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 $n^{1-\varepsilon}$. "Maximum independent set in a **planar** graph" has a PTAS; the same problem on $K_5$-minor-free graphs also does; on general graphs even $n^{1-\varepsilon}$-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.
:::

:::problems
- [[CSES 1130]] Tree Matching | https://cses.fi/problemset/task/1130 | easy | the two-state DP in its simplest form (the dual of independent set on a tree)
- [[CSES 1696]] School Dance | https://cses.fi/problemset/task/1696 | core | the bipartite route to $\alpha = n - \nu$: solve it with matching and compare with the DP
:::