3
$\begingroup$

The vertex cover and independent set as a subset of nodes are always considered in a dual relationship. Have they been looked at together? What I mean is: start from a minimum vertex cover, and if it is not an independent set, add or remove vertices to make it one. So for instance, if there is an edge whose both endpoints are included in the vertex cover, remove one of them and add other nodes to maintain the covering property, but also achieve independence.

Does this kind of a subset of nodes have a name, and has it been studied? At least for acyclic graphs, it seems like there should be a "minimum deviation" way to convert a minimum vertex cover to a vertex cover which is also an independent set.

Thanks!

$\endgroup$
13
$\begingroup$

This is the "Independent Vertex Cover" problem. It is solvable in polynomial time. To see this, note that for every edge, exactly one endpoint of the edge must be in a vertex cover. We can reduce the problem to 2-SAT, as follows: make a variable $x_i$ for each vertex $i$, and for each edge $(i,j)$, include clauses of length two of the form $x_i \oplus x_j = 1$.

See also https://stackoverflow.com/questions/10769971/algorithm-for-independent-vertex-cover

$\endgroup$
  • 5
    $\begingroup$ This solution finds an independent vertex cover, but not necessarily the minimum one asked for here. To find the minimum one, observe that an IVC must (in each connected component of the graph) be one side of a bipartition, and find the smaller of the two sides in each component. $\endgroup$ – David Eppstein Oct 3 '16 at 5:21
  • $\begingroup$ Yes, since vertex covers and independent sets are complements of each other, it's easy to find the minimum here... $\endgroup$ – Ryan Williams Oct 3 '16 at 6:07

Your Answer

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

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