Coloring & Covering

Shortest Paths & Bipartite Check solved one coloring question - "can two colors do it?" - with a BFS. This page is what lies just past that question, and the honest answer is: a cliff. Two colors is linear. Three colors is NP-complete. The same cliff runs through a whole family of "pick a special set of vertices" problems, and the practical skill is recognising which side of it you are on before you start coding.

Mnemonic

Two colors is a traversal; three colors is a search. The moment a problem asks for a third group, stop looking for a clever linear algorithm - either the graph has special structure (bipartite, a tree, an interval graph) or you are doing backtracking with n small.

1. Graph coloring and the chromatic number

A proper coloring assigns a color to every vertex so that no edge joins two vertices of the same color. The chromatic number X(G) is the fewest colors that suffices.

X(G)	Exactly when	Cost to decide
0	the graph has no vertices	trivial
1	the graph has no edges	O(E) - just look
<= 2	the graph is bipartite, i.e. contains no odd cycle	O(V + E) - the 2-coloring BFS
<= 3	no simple characterisation exists	NP-complete
<= k for k >= 3	same	NP-complete

That jump from linear to NP-complete between 2 and 3 is one of the sharpest in all of computer science, and it is worth knowing precisely because problem setters use it: a problem that wants two groups is a traversal problem wearing a disguise, and a problem that wants three is either small or structured.

2 + 3 = 5: the independent set and the vertex cover are exactly each other's complement.

Greedy coloring

Walk the vertices in some order and give each the smallest color no neighbour already has. It is three lines, it always produces a valid coloring, and it is not guaranteed to be optimal.

def greedy_coloring(num_nodes, adj, order=None):

color = [-1] * num_nodes

for u in (order or range(num_nodes)):

taken = {color[v] for v in adj[u] if color[v] != -1}

c = 0

while c in taken: # smallest color no neighbour holds

c += 1

color[u] = c

return color

Two bounds are worth remembering:

• Greedy never uses more than max_degree + 1 colors, because when you color u at most deg(u) colors are taken, so one of the first deg(u) + 1 is free. That gives X(G) <= max_degree + 1 for free.
• Brooks' theorem tightens it: X(G) <= max_degree for every connected graph except a complete graph and an odd cycle, which are the only two that genuinely need max_degree + 1.

⚠

Greedy coloring depends on vertex order

Greedy's result depends entirely on the vertex order, and a bad order can be arbitrarily bad. There is always some order for which greedy uses exactly X(G) colors - and finding it is as hard as the coloring problem itself, so that fact is not usable. Order heuristics (largest degree first, or smallest-last) help in practice and prove nothing. If a problem needs the minimum, greedy is not an answer; if it needs any valid coloring or a bound, greedy is the whole answer.

"What is the minimum number of meeting rooms for these intervals" is exactly X(G) on the graph whose vertices are the meetings and whose edges join overlapping pairs. That graph is an interval graph, and interval graphs are one of the special structures where coloring is easy: sort by start time and greedily reuse any room that is free, and you provably use the minimum - which equals the maximum number of intervals overlapping at any single point. So the NP-hardness of coloring is real but not universal, and recognising the structure is what makes the difference between a sort and a search.

2. Independent sets, cliques, and vertex covers

Three ways to pick a special subset of vertices. All three are NP-hard in general, and all three are the same problem wearing different clothes.

Set	Rule	You usually want
Independent set	no two chosen vertices are adjacent	the maximum one - "the largest group of mutual strangers", "the most non-conflicting tasks"
Clique	every two chosen vertices are adjacent	the maximum one - "the largest group who all know each other"
Vertex cover	every edge has at least one endpoint chosen	the minimum one - "the fewest guards covering every corridor"
Dominating set	every vertex is chosen or adjacent to a chosen one	the minimum one - "the fewest transmitters covering every house"

Two identities tie them together, and both are one-line proofs:

• Independent set in G = clique in the complement of G. "No edges inside" becomes "all edges inside" when you flip which pairs are joined. So the two problems are the same problem, and any algorithm for one solves the other by complementing the input (Graph Anatomy).
• S is an independent set exactly when V \ S is a vertex cover. If no edge lies inside S, then every edge has an endpoint outside S, and conversely. Hence max independent set + min vertex cover = |V| - so finding either one gives you the other by subtraction.

Mnemonic

Independent set and vertex cover are complements; independent set and clique are complements of the graph. One identity flips the set, the other flips the edges. Both mean you never need three algorithms - you need one, plus the right flip.

⚠

"Maximal" and "maximum" aren't the same word

"Maximal" and "maximum" are different words and problems conflate them deliberately. A maximal independent set is one you cannot extend by adding any single vertex - greedy finds one in O(V + E). A maximum independent set is the largest one that exists - NP-hard. In the 5-cycle above, {1} extended greedily might stop at {1, 3} (size 2, which happens to be maximum) or, on a bigger graph, at a maximal set far smaller than the maximum. If a problem says "maximal," the greedy answer is correct; if it says "maximum" or "largest," it is not.

Where these become tractable

The NP-hardness is about general graphs. Three structures escape it, and between them they cover most problems you will actually be handed:

Structure	What becomes easy	How
Bipartite graph	minimum vertex cover, maximum independent set, maximum matching	Konig's theorem: min vertex cover = max matching, computable by flow (Flows & Matching)
Tree / forest	all four sets above	DP over the tree: for each vertex, the best answer given "I am in the set" or "I am not" - two values per vertex, one postorder pass
Interval graph	coloring, independent set, clique	sort by endpoint and be greedy; the interval structure makes greedy provably optimal
**Small n (about 20)**	all of them	enumerate subsets as bitmasks (bit-manipulation core techniques)

The maximum-independent-set-on-a-tree DP is the shape to remember, because it generalises.

At each vertex you keep two numbers: the best you can do in this subtree if you take this vertex (so you must skip its children), and the best if you skip it (so children are free). Combine bottom-up, answer at the root. That "take it / skip it, computed in postorder" pattern is the same one behind house-robber-on-a-tree, minimum-cost-to-cover-a-tree, and most tree-shaped optimisation.

3. The NP-hard map

Worth keeping in one place, because the useful skill is instant recognition rather than recall of any algorithm:

Problem	Status on a general graph	The escape hatch
2-coloring / bipartite check	O(V + E)	none needed
k-coloring, k >= 3	NP-complete	greedy for a valid-but-not-minimal coloring; exact only for small n
Maximum independent set / clique	NP-hard	trees, bipartite graphs, interval graphs, small n
Minimum vertex cover	NP-hard	bipartite (Konig), trees, and a 2-approximation by taking both ends of a maximal matching
Minimum dominating set	NP-hard	trees, small n
Hamiltonian path / cycle, TSP	NP-complete / NP-hard	bitmask DP for n about 20 (Eulerian & Hamiltonian)
Longest simple path	NP-hard	DAGs, where it is O(V + E)
Maximum matching	polynomial	not hard at all - see the next page
Maximum cut	NP-hard	a 0.5-approximation by random assignment
Minimum cut	polynomial	max-flow-min-cut

⚠

Symmetric-looking pairs hide the real traps

The pairs that look symmetric but are not are where the real traps live. Maximum matching is polynomial while maximum independent set is NP-hard. Minimum cut is polynomial while maximum cut is NP-hard. Shortest path is polynomial while longest simple path is NP-hard. In each pair, the easy one has a structure (augmenting paths, flow duality, no need to avoid revisits) that the hard one destroys. Assuming that "the other direction must be similar" is the single most expensive wrong instinct in this area.

Where to go next

• Flows & Matching - the polynomial half of this page: matching, min cut, and the duality theorems that make bipartite covering problems easy.
• Shortest Paths & Bipartite Check - the 2-coloring BFS this page starts from.