1
$\begingroup$

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.

$\endgroup$
2
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.