Chapter V Vertex Cover

Touch every edge

Cover an edge by grabbing one of its endpoints. Now do that for every edge with as few grabs as possible.

A vertex cover is a set of vertices that touches every edge:

C \subseteq V such that {u, v} \cap C \neq = \emptyset for every {u, v} \in E . (1)

The decision version asks: does a cover of size at most k satisfying (1) exist? Vertex cover is the complement of independent set:

C is a vertex cover ⟺ V ∖ C is an independent set, (2)

so it reduces directly from clique on the complement graph.

Two facts make vertex cover the friendly face of NP-completeness. First, a trivial 2-approximation: greedily pick both endpoints of any uncovered edge. Second, a fixed-parameter tractable exact algorithm running in time

O (1. 2^{k} \cdot n), (3)

which is fast when the answer k is small, regardless of n.

Figures, in plain terms

(1)

C ⊆ V picks a subset of vertices to call the cover. The job is to pick C so that every edge has at least one endpoint in it.

{u, v} ∩ C ≠ ∅ uses two symbols. The braces {u, v} are an edge — an unordered pair of vertices. The ∩ is the intersection ("elements in both"). And ≠ ∅ says "is not empty."

So {u, v} ∩ C ≠ ∅ reads: "the two endpoints of this edge, intersected with the cover, give back at least one vertex." In plain words, at least one endpoint of this edge is in the cover.

The trailing for every {u, v} ∈ E demands the condition holds on every edge of the graph, not just some.

(2)

The two-headed arrow ⟺ means if and only if — both sides imply each other.

V \ C is set difference: the vertices in V but not in C. The backslash is "minus" for sets.

The right side says V \ C is an independent set — no two vertices in it share an edge.

The whole identity says: choosing a vertex cover and choosing an independent set are the same act, viewed from opposite sides. If you cover every edge with C, the leftover vertices V \ C touch no edges among themselves.

(3)

Same big-O as chapter 3, but the exponent now uses k, not n. Here k is the answer size — how big a cover the problem asks for.

The catch: even if n is enormous (a graph with millions of vertices), this runtime depends on k. So when the cover is small (say k ≤ 30), the algorithm runs in roughly 1.2³⁰ ≈ 240 steps per vertex — fast.

This is the FPT (fixed-parameter tractable) trick: trade an n-sized parameter for a k-sized one when k is the natural difficulty knob.