2
$\begingroup$

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?

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

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
0
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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