Past exam of the computer science course of the University of Oxford / 2018 / Algorithms / 2 / b

Construct a set cover problem instance whose universe is the set of edges $E$. For each vertex $v\in V$, supply the set $S_v$ of all edges incident to $v$. A collection $\{S_v:v\in C\}$ covers the universe if and only if every edge has an endpoint in $C$, which is precisely the vertex cover condition.

The correspondence preserves cardinality: a vertex cover of size $k$ is a feasible solution of the set cover problem using $k$ of these sets, and conversely. If two labelled vertices produce identical sets, one can keep their labels or discard duplicate choices without changing the optimum. The construction has size $O(|V|+|E|)$ when incidences are listed, so it is a polynomial-time reduction.