# NP-Complete problem proof

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.

• Please credit the source of all copied material in the question. See cs.stackexchange.com/help/referencing.
– D.W.
Commented Apr 22, 2020 at 4:17
• – D.W.
Commented Apr 22, 2020 at 4:19

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.