# Is this problem in P? Given a bipartite graph, find a minimum cardinality set of edges which intersect every vertex cover

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?

• 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.
– holf
Mar 3, 2021 at 7:20
• I guess it should be "which intersects all minimal vertex covers" or perhaps "which intersects all vertex covers of minimum cardinality". Mar 3, 2021 at 10:09
• Minimal: same problem, just take $A' \subseteq A$ minimal. Minimum cardinality could work. Let's wait for the OP clarification.
– holf
Mar 3, 2021 at 12:55
• @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$. Mar 4, 2021 at 10:41
• 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 Mar 6, 2021 at 2:45