2
$\begingroup$

Given a graph $G$ and integer $k$, find a vertex coverage set of size $k$ that is also an independent set. I need to either prove this problem is np-complete or find a polynomial solution. Any idea?

$\endgroup$
3
  • 3
    $\begingroup$ If $S$ is a vertex cover then $\overline{S}$ is an independent set (otherwise, there is an edge not covered by $S$). Hence if $S$ is an independent set, all edges in the graph must go between $S$ and $\overline{S}$, that is, the graph is bipartite. Hope this helps. $\endgroup$ Dec 5, 2019 at 20:19
  • $\begingroup$ Does what you say prove or disprove that the decision problem is np-complete ? That was the question. $\endgroup$
    – Gil
    Dec 5, 2019 at 20:46
  • 1
    $\begingroup$ Right, but it's your exercise, and I'm not planning to solve it for you. $\endgroup$ Dec 5, 2019 at 20:48

1 Answer 1

0
$\begingroup$

This problem is called the independent vertex cover problem and it is solvable in polynomial time. Note that the set $S$ must be a vertex cover means that each edge has an endpoint in the set. On the other side, being an independent set means that each edge has at most one endpoint in the set. Hence, each edge has exactly one endpoint in the set. That means we are looking for the smallest possible subset of vertices $S$ such that $(S, V\setminus S)$ is a bipartition of the graph. This can be done in linear time since each connected component has either non or exactly one bipartition.

Here is also another solution of the problem based on a reduction to the 2-sat problem (also using the fact that each edge has exactly one endpoint in the set).

https://cstheory.stackexchange.com/questions/36707/smallest-vertex-cover-which-is-also-an-independent-set

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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