# No Neighbor Vertex Cover

Let $$G=(V,E)$$ be an undirected connected graph with a set of vertices $$|V|$$ and a set of edges $$|E|$$. A set cover $$D$$ satisfies $$D \subseteq V$$ and $$uv \in E \implies u \in D \lor v \in D$$. A variant of the vertex cover requires that exactly one vertex, $$u$$ or $$v$$, not both, is in $$D$$. In this sense, no vertices in $$D$$ are neighboring. The maximization problem seeks to maximize $$|D|$$ and the minimization problem seeks to minimize $$|D|$$. Are both problems solvable in polynomial time?

• Ask yourself: How does such a set look if $G$ is a bipartite graph? How about if $G$ is not bipartite? Commented Mar 10 at 14:36
• @Highheath turn the comment into an answer? Commented Mar 12 at 18:13
• Well, $D$ exists iff $G$ is bipartite, so it only makes sense to consider bipartite graphs for finding maximum/minimum such $D$. Commented Mar 12 at 19:58

We can see the following observations on the sets $$D$$ and $$C = V\setminus D$$:

Every edge in $$E$$ contains exactly one node in $$D$$

$$\rightarrow$$ Every edge in $$E$$ contains exactly one node in $$C$$

$$\rightarrow$$ Both $$D$$ and $$C$$ are vertex covers of $$G$$

$$\rightarrow$$ Both $$D$$ and $$C$$ are independent sets (the complement of a vertex cover is always an independent set)

$$\rightarrow (D,C)$$ is a 2-coloring of $$V$$, and as such, they only exist if $$G$$ is bipartite.

As Michal says in the other answer: If $$G$$ is connected, then the 2-coloring is unique and can be found in polynomial time.

Even if $$G$$ is not connected, maximizing the size of such a vertex cover is equal to taking the union of the biggest color class in each component, and can be found quickly as well.

This answers the problem only partially (in particular, for the minimization) Whether or not the set $$D$$ exists is equivalent to the fact that $$G$$ is bipartite. This can be tested in polynomial time.

To see the equivalence, note that $$G$$ is bipartite if and only if it does not contain an odd cycle. If $$G$$ is bipartite, each partition is a valid independent vertex cover. On the other hand, if $$G$$ is not bipartite, then consider the odd cycle $$C$$ of length $$2n+1$$ in $$G$$. Every independent set in $$C$$ is of size at most $$n$$, but every vertex cover is of size at least $$n+1$$, so no such set can exist for $$G$$.

Suppose that $$G$$ is conencted, otherwise do it per connected component.

We know that if $$G$$ is connected then the bipartition is, up to swapping the parts, unique and the minimum independent vertex cover is the smaller of the two parts.

• You should add a proof to the equivalence with the fact that $G$ is bipartite. Commented Mar 12 at 22:20
• @Highheath If my understanding is correct, finding a 2-coloring solves both problems. Commented Mar 15 at 12:03