3
$\begingroup$

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.

$\endgroup$

migrated from cstheory.stackexchange.com Jun 9 '12 at 17:59

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 4
    $\begingroup$ This problem is usually called set cover. $\endgroup$ – Tsuyoshi Ito Jun 9 '12 at 13:03
  • 2
    $\begingroup$ 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. $\endgroup$ – Jukka Suomela Jun 9 '12 at 13:46
  • $\begingroup$ You are right! I can see it now. Thanks. $\endgroup$ – hbm Jun 9 '12 at 14:46
  • 1
    $\begingroup$ @JukkaSuomela This comment should be either an edit to the question or an answer, depending on whether it solves the problem or not. $\endgroup$ – Raphael Jun 10 '12 at 10:52
1
$\begingroup$

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}$.

$\endgroup$

Your Answer

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