<p>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$. </p>

<p>See also <a href="https://stackoverflow.com/questions/10769971/algorithm-for-independent-vertex-cover">https://stackoverflow.com/questions/10769971/algorithm-for-independent-vertex-cover</a></p>

CC BY-SA 3.0
2016-10-03T05:21:15.130Z
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.
David Eppstein
CC BY-SA 3.0
2016-10-03T06:07:32.193Z
Yes, since vertex covers and independent sets are complements of each other, it's easy to find the minimum here...
Ryan Williams
CC BY-SA 3.0
2016-10-03T04:50:40.387Z
2016-10-03T04:50:40.387Z
2017-05-23T12:40:09.333Z
Ryan Williams
<p>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.</p>

<p>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.</p>

<p>Thanks!</p>

<graph-theory><planar-graphs>
Smallest vertex cover which is also an independent set
elexhobby
# Smallest vertex cover which is also an independent set

(Asked by: username_0 on 2016-10-03)

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!

**Tags:** graph-theory, planar-graphs


---

## 1 answers

### Answer by username_1 on 2016-10-03. Score: 15 | Accepted answer

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>

> **Comments:**
> **username_2**: 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.  
> **username_1**: Yes, since vertex covers and independent sets are complements of each other, it's easy to find the minimum here...  

---

