[proofplan]
We first verify that $\mathrm{SET\ COVER}$ lies in NP by using the selected indices of the subfamily as a certificate and checking coverage by direct incidence scanning. For NP-hardness, we reduce from the classical Karp theorem that $\mathrm{VERTEX\ COVER}$ is NP-complete. Given a graph, we enumerate its vertices, make the universe equal to the edge set, and associate to each vertex-index the set of edges incident with that vertex. Vertex covers then correspond exactly to set covers of the constructed universe, giving a polynomial-time many-one reduction.
[/proofplan]
[step:Verify membership in NP using the selected subfamily as the certificate]
Let an instance of $\mathrm{SET\ COVER}$ be denoted by
\begin{align*}
(U,(S_i)_{i=1}^m,k),
\end{align*}
where $U$ is a finite set, $S_i \subset U$ for each $i \in \{1,\dots,m\}$, and $k \in \mathbb{Z}_{\geq 0}$.
A certificate is a subset $I \subset \{1,\dots,m\}$. The verifier first checks that $|I| \leq k$. It then checks, for every element $u \in U$, whether there exists an index $i \in I$ such that $u \in S_i$. If every $u \in U$ passes this test, the verifier accepts; otherwise it rejects.
The size check is polynomial in the input length. The coverage check can be performed by scanning the incidence representation of the family $(S_i)_{i=1}^m$, and hence it uses time polynomial in the input length. Therefore $\mathrm{SET\ COVER} \in \mathrm{NP}$.
[guided]
We must show that a proposed solution can be checked in polynomial time. For the instance
\begin{align*}
(U,(S_i)_{i=1}^m,k),
\end{align*}
the natural certificate is the list of indices
\begin{align*}
I \subset \{1,\dots,m\}
\end{align*}
corresponding to the chosen subfamily.
The verifier performs two checks. First, it computes $|I|$ and verifies $|I| \leq k$. Second, it verifies the covering condition: for each element $u \in U$, it searches the selected sets $S_i$ with $i \in I$ and checks whether at least one of them contains $u$. In symbols, the verifier accepts exactly when
\begin{align*}
\forall u \in U,\ \exists i \in I \text{ such that } u \in S_i.
\end{align*}
This condition is equivalent to
\begin{align*}
U = \bigcup_{i \in I} S_i,
\end{align*}
because every selected set is already a subset of $U$. The verifier only scans the input incidence data and the certificate, so its running time is bounded by a polynomial in the input length. Hence $\mathrm{SET\ COVER}$ belongs to $\mathrm{NP}$.
[/guided]
[/step]
[step:Construct a polynomial-time reduction from vertex cover]
We reduce from $\mathrm{VERTEX\ COVER}$, using the classical Karp theorem that $\mathrm{VERTEX\ COVER}$ is NP-complete.
Let an instance of $\mathrm{VERTEX\ COVER}$ be
\begin{align*}
(G,k),
\end{align*}
where $G=(V,E)$ is a finite simple undirected graph and $k \in \mathbb{Z}_{\geq 0}$. Choose an enumeration of the finite vertex set,
\begin{align*}
V=\{v_1,\dots,v_m\}.
\end{align*}
Define a $\mathrm{SET\ COVER}$ instance
\begin{align*}
(U,(S_i)_{i=1}^m,k)
\end{align*}
as follows. Set
\begin{align*}
U := E.
\end{align*}
For each index $i \in \{1,\dots,m\}$, define the subset
\begin{align*}
S_i := \{e \in E : e \text{ is incident with } v_i\} \subset U.
\end{align*}
This construction creates one set for each vertex and one incidence membership for each endpoint-edge incidence. Since a finite simple undirected graph has exactly two endpoint-edge incidences per edge, the constructed set system has $m=|V|$ sets and at most $2|E|$ listed memberships. Therefore the map
\begin{align*}
(G,k) \mapsto (E,(S_i)_{i=1}^m,k)
\end{align*}
is computable in polynomial time in the size of the graph encoding.
[/step]
[step:Send every vertex cover to a set cover]
Assume that $C \subset V$ is a vertex cover of $G$ with $|C| \leq k$. Define the selected index set
\begin{align*}
J := \{i \in \{1,\dots,m\} : v_i \in C\}.
\end{align*}
Because the enumeration $V=\{v_1,\dots,v_m\}$ lists each vertex once, $|J|=|C| \leq k$.
We prove that
\begin{align*}
E = \bigcup_{i \in J} S_i.
\end{align*}
Let $e \in E$. Since $C$ is a vertex cover, the edge $e$ has at least one endpoint $v_i \in C$ for some $i \in \{1,\dots,m\}$. By the definition of $J$, this index $i$ belongs to $J$. By the definition of $S_i$, the edge $e$ belongs to $S_i$. Hence $e \in \bigcup_{i \in J} S_i$. Since $e \in E$ was arbitrary, $E \subset \bigcup_{i \in J} S_i$. The reverse inclusion holds because every $S_i$ is a subset of $E$. Therefore $\{S_i : i \in J\}$ covers $U=E$, and its size is at most $k$.
[/step]
[step:Send every set cover back to a vertex cover]
Assume that the constructed $\mathrm{SET\ COVER}$ instance has a cover indexed by a set $I \subset \{1,\dots,m\}$ such that $|I| \leq k$ and
\begin{align*}
E = \bigcup_{i \in I} S_i.
\end{align*}
Define
\begin{align*}
C := \{v_i \in V : i \in I\}.
\end{align*}
Because the enumeration $V=\{v_1,\dots,v_m\}$ lists each vertex once, $|C|=|I| \leq k$.
We show that $C$ is a vertex cover of $G$. Let $e \in E$. Since the selected sets cover $E$, there exists $i \in I$ such that $e \in S_i$. By the definition of $S_i$, the edge $e$ is incident with $v_i$. Since $v_i \in C$, the edge $e$ has an endpoint in $C$. As $e \in E$ was arbitrary, every edge of $G$ is incident with some vertex in $C$. Thus $C$ is a vertex cover.
[/step]
[step:Conclude NP-completeness from the equivalence of the two instances]
The previous two steps prove the equivalence
\begin{align*}
(G,k) \in \mathrm{VERTEX\ COVER}
\end{align*}
if and only if
\begin{align*}
(E,(S_i)_{i=1}^m,k) \in \mathrm{SET\ COVER}.
\end{align*}
Thus the construction is a polynomial-time many-one reduction from $\mathrm{VERTEX\ COVER}$ to $\mathrm{SET\ COVER}$, preserving yes-instances and no-instances. Since $\mathrm{VERTEX\ COVER}$ is NP-complete, this proves that $\mathrm{SET\ COVER}$ is NP-hard. Together with $\mathrm{SET\ COVER} \in \mathrm{NP}$, established above, $\mathrm{SET\ COVER}$ is NP-complete.
[/step]
