We know that finding minimum size vertex cover is hard (NP-hard). Same hold for connected vertex cover. But what about finding minimum size independent vertex cover?
1
-
1$\begingroup$ stackoverflow.com/q/10769971/781723 $\endgroup$– D.W. ♦Commented Jul 23 at 2:07
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The link provided by D.W. leads to the discussion about existence of independent vertex cover. It is easy to prove that independent vertex cover exists if and only if the graph is bipartite.
To find minimum independent vertex cover consider all connected components one by one and select in every component all vertices from a part of smaller size.
