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?