= Solution
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>: \b[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>.
Back to article page
