NP-Complete problem proof

Question

I have an exam in two days and I am not sure if I have understood correctly the way of proving np-completness and how to pick a known np-hard problem to reduce it. Bellow I present a problem which I need help with to understand how to prove it's NP-complete. Any help will be much appreciated!

[Background] A directed graph is consisting of people, with an edge from person A to person B if person A is a follower of person B. For any set S of people, we say that S reaches all people who are followers of at least one person in S. Everyone is a follower of themselves so any set of people S reaches at least itself.

The answer of the algorithm is YES if there exists a set S of at most k people reaching at least m people, and NO otherwise.

Prove that this is a NP-complete problem by reducing a known NP-hard problem.

So the first step is to prove that the problem is a NP problem and if I understand correctly I can prove that by finding a cefrtificate that is proved as a solution of the probem in polynomial time. However, I have problems in picking a known NP-hard problem and reducing.

Answer 1

Consider an instance $G=(V,E)$ of vertex cover with $n=|V|$ and $m=|E|$, and build a directed graph $G' = (V', E')$ in which:

• $V' = V \cup ( E \times \{0, 1, \dots, n\} )$.
• For each $e = (u,v) \in E$, $E'$ contains all edges $(u,e')$ and $(v,e')$ for $e' \in \{e\} \times \{0, 1, \dots, n\}$.

Claim: If there is a set of at most $k$ observers that reaches at least $(n+1)m$ people in $G'$, then there is a vertex cover of size at most $k$ in $G$.

Proof: The existence of a set a set of $k$ observers that reaches at least $(n+1)m$ people in $G'$ implies the existence of a set $S \subseteq V$ of at most $k$ observers that reaches at least $(n+1)m$ people in $G'$.

For every edge $e=(u,v) \in E$, $\{u,v\} \cap S \neq \emptyset$. Indeed, if $\{u,v\} \cap S = \emptyset$, then none of the vertices in $e \times \{0, \dots, n\}$ is reached by $S$ in $G'$, showing that $S$ reaches at most $(n+1)m+n - (n+1) = (n+1)m-1$ people in $G'$. Therefore $S$ is a vertex cover for $G$. $\square$

Claim: If there is a vertex cover $C$ of size at most $k$ in $G$, then there is a set of at most $k$ observers that reaches at least $(n+1)m$ people in $G'$.

Proof: For each edge $e = (u,v) \in E$, let $x \in \{u,v\} \cap S$. All vertices $\{e\} \times \{0, \dots, n\}$ in $G'$ are reached by $x$ and hence by $C$. Therefore $C$ reaches at least $m \cdot (n+1)$ people in $G$. $\square$

This shows that your problem is NP-hard.