Smallest vertex cover which is also an independent set

Question

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!

Answer 1

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