# Restricted version of vertex cover

I am interested in the complexity of the restricted version of the vertex cover problem below:

Instance: A bipartite graph $$G =(L, R, E)$$ and an integer $$K$$.

Question: Is there $$S \subset L$$, $$|S| \leq K$$ and every vertex in $$R$$ has a neighbor in $$S$$ $$( S$$ is vertex cover for $$R)$$

Vertex cover is $$\mathsf{P}$$ if $$S \subset L \cup R$$ and cover $$L \cup R$$; and it is $$\mathsf{NP}$$-complete for nonbipartite graphs. However, the problem I am looking at does not fit in either cases. Any pointers where I could find an answer will be appreciated.

• This problem is usually called set cover. – Tsuyoshi Ito Jun 9 '12 at 13:03
• Indeed, this is not a restricted version of the vertex cover problem, it is something much more difficult. A vertex cover is a subset of nodes that "covers" all edges, while you are looking for a subset of nodes that "dominates" all other nodes. As @TsuyoshiIto said, it is simply a graph representation of the set cover problem. Alternatively, you can interpret it as a variant of the dominating set problem. – Jukka Suomela Jun 9 '12 at 13:46
• You are right! I can see it now. Thanks. – hbm Jun 9 '12 at 14:46
• @JukkaSuomela This comment should be either an edit to the question or an answer, depending on whether it solves the problem or not. – Raphael Jun 10 '12 at 10:52

Let us call your problem as $\mathsf{RESVC}$. $\mathsf{RESVC}$ is NP-Complete.

• Given a subset $S \in L$ its easy to verify in poly. time whether it forms a valid cover of size k. Hence, $\mathsf{RESVC} \in \mathsf{NP}$

• $\mathsf{RESVC}$ is also NP-hard because the decision version of the Minimum Dominating set problem reduces to it. And, we know that the decision version of Minimum Dominating set is NP-complete. The reduction goes as follows:

$\qquad \displaystyle \mathsf{D\text{-}MIN\text{-}DOM\text{-}SET} = \{ \langle G,k \rangle : G \text{ has a dominating set } S \text{ s.t. } |S| \leq k \}$

Reduce the instance $\langle G,k \rangle$ of above language to $\langle G',k \rangle$ as follows:

Lets say $G = (V,E)$ and $V = \{v_1,v_2,\dots,v_n\}$ and define $G' = (L \cup R, E')$ with

• $L = \{v_{11},v_{21},...,v_{n1}\}$
• $R = \{v_{12},v_{22},...,v_{n2}\}$
• $E' = \{(v_{i1},v_{j2}) : (v_i,v_j) \in E \vee (v_j,v_i) \in E\} \cup \{(v_{i1},v_{i2})\}$

Now, it is easy to see that $\langle G',k \rangle \in \mathsf{RESVC}$ if and only if $\langle G,k \rangle \in \mathsf{D\text{-}MIN\text{-}DOM\text{-}SET}$.