5
$\begingroup$

This problem came up in my study of digraphs:

Given a connected bipartite graph $G = (A \cup B, E)$, a vertex cover is a set $S$ of vertices such that every edge has some endpoint in $S$.

Note that $A$ and $B$ are vertex covers. A non-trivial vertex cover is a vertex cover which does not contain $A$ and does not contain $B$.

A set $F \subseteq E$ of edges intersects a vertex cover $S$ if the set $E[S] \cap F$ is not empty. That is, if there is an edge $e=(u,v) \in F$ such that both $u$ and $v$ are in $S$.

I decided to call a set of edges which intersect all non-trivial vertex covers, a VC cover.

Is there a polynomial time algorithm to find a minimum cardinality VC cover?

Improve this question
$\endgroup$
9
  • $\begingroup$ I think you should work a bit more on your definitions. The problem stated as it is now is trivial: since $A$ is a vertex cover, a VC cover $F$ has non-empty intersection with $E[A]$. But $E[A]$ is empty. $\endgroup$ – holf Mar 3 at 7:20
  • $\begingroup$ I guess it should be "which intersects all minimal vertex covers" or perhaps "which intersects all vertex covers of minimum cardinality". $\endgroup$ – Gamow Mar 3 at 10:09
  • $\begingroup$ Minimal: same problem, just take $A' \subseteq A$ minimal. Minimum cardinality could work. Let's wait for the OP clarification. $\endgroup$ – holf Mar 3 at 12:55
  • 2
    $\begingroup$ @holf I don’t understand your argument. For example, if $|A|,|B|\ge2$ and $G$ is the complete bipartite graph, then $A$ and $B$ are both minimal vertex covers, but there is no vertex of degree $1$. In general, $A$ is a minimal vertex cover if and only if there are no isolated vertices in $A$, and similarly for $B$. $\endgroup$ – Emil Jeřábek Mar 4 at 10:41
  • 2
    $\begingroup$ No, the vertex covers you gave are trivial vertex covers because they contain A or contain B. In a complete bipartite graph, you can actually see that there are no non-trivial vertex covers, as any vertex cover must contain A or B (note that the graph is connected). Hope this clarifies things $\endgroup$ – Karagounis Z Mar 6 at 2:45

Your Answer

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

Browse other questions tagged or ask your own question.