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?
$\begingroup$
$\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$– Yuval FilmusCommented 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$– GilCommented 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$– Yuval FilmusCommented Dec 5, 2019 at 20:48
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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).
answered Dec 8, 2019 at 2:39