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, 2021 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, 2021 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, 2021 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, 2021 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, 2021 at 2:45

0

Reset to default

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.