<p>This problem came up in my study of digraphs:</p>
<p>Given a connected bipartite graph <span class="math-container">$G = (A \cup B, E)$</span>, a <em><strong>vertex cover</strong></em> is a set <span class="math-container">$S$</span> of vertices such that every edge has some endpoint in <span class="math-container">$S$</span>.</p>
<p>Note that <span class="math-container">$A$</span> and <span class="math-container">$B$</span> are vertex covers. A <em><strong>non-trivial vertex cover</strong></em> is a vertex cover which does not contain <span class="math-container">$A$</span> and does not contain <span class="math-container">$B$</span>.</p>
<p>A set <span class="math-container">$F \subseteq E$</span> of edges <em><strong>intersects</strong></em> a vertex cover <span class="math-container">$S$</span> if the set <span class="math-container">$E[S] \cap F$</span> is not empty. That is, if there is an edge <span class="math-container">$e=(u,v) \in F$</span> such that both <span class="math-container">$u$</span> and <span class="math-container">$v$</span> are in <span class="math-container">$S$</span>.</p>
<p>I decided to call a set of edges which intersect all non-trivial vertex covers, a <em><strong>VC cover</strong></em>.</p>
<p>Is there a polynomial time algorithm to find a minimum cardinality VC cover?</p>

CC BY-SA 4.0
2021-03-03T07:20:17.167Z
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
CC BY-SA 4.0
2021-03-03T10:09:31.333Z
I guess it should be "which intersects all minimal vertex covers" or perhaps "which intersects all vertex covers of minimum cardinality".
Gamow
CC BY-SA 4.0
2021-03-03T12:55:08.517Z
Minimal: same problem, just take $A' \subseteq A$ minimal.
Minimum cardinality could work. Let's wait for the OP clarification.
holf
CC BY-SA 4.0
2021-03-04T02:12:23.873Z
hi, I changed the question a bit. I intended that a VC cover should intersect all 
*non-trivial* vertex covers. The set A is a trivial vertex cover.
Karagounis Z
CC BY-SA 4.0
2021-03-04T09:07:17.283Z
Same problem: if either $A$ or $B$ is not minimal, you have $S\subsetneq A$ (or $\subsetneq B$) that is a non trivial vertex cover and $E[S] = \emptyset$. Otherwise, both $A$ and $B$ are minimal. By minimality of $B$, there exists $x \in A$ of degree $1$. Let $y \in B$ be its only neighbor. Since $A$ is minimal, $y$ is also of degree $1$ (othw you could remove $x$ from $A$ and still be a VC). Thus $S'=A \setminus \{x\} \cup \{y\}$ is a non-trivial VC with $E[S'] = \emptyset$.
holf
CC BY-SA 4.0
2021-03-04T10:41:05.590Z
@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$.
Emil Jeřábek
CC BY-SA 4.0
2021-03-04T10:57:59.653Z
You are right of course, you need the whole $A$ to cover $A$ if you only allow vertices there. I was trying to cover only the vertices in $B$...
holf
CC BY-SA 4.0
2021-03-05T02:30:44.307Z
Just to check my understanding of the problem, in the case that $|A|=|B|$ and $E=A\times B$, then the (minimal) non-trivial vertex covers are the sets of the form $A\cup\{b\}$ such that $b\in B$, or $\{a\}\cup B$ such that $a\in A$, and the minimum-cardinality VC covers are the perfect matchings in $G$?
Neal Young
CC BY-SA 4.0
2021-03-06T02:45:48.060Z
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
Karagounis Z
<ds.algorithms><graph-algorithms><np-hardness>
Is this problem in P? Given a bipartite graph, find a minimum cardinality set of edges which intersect every vertex cover
Karagounis Z
# Is this problem in P? Given a bipartite graph, find a minimum cardinality set of edges which intersect every vertex cover

(Asked by: username_0 on 2021-03-03)

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?

**Tags:** ds.algorithms, graph-algorithms, np-hardness

> **Comments:**
> **username_1**: 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.  
> **username_2**: I guess it should be "which intersects all minimal vertex covers" or perhaps "which intersects all vertex covers of minimum cardinality".  
> **username_1**: Minimal: same problem, just take $A' \subseteq A$ minimal. Minimum cardinality could work. Let's wait for the OP clarification.  
> **username_0**: hi, I changed the question a bit. I intended that a VC cover should intersect all  *non-trivial* vertex covers. The set A is a trivial vertex cover.  
> **username_1**: Same problem: if either $A$ or $B$ is not minimal, you have $S\subsetneq A$ (or $\subsetneq B$) that is a non trivial vertex cover and $E[S] = \emptyset$. Otherwise, both $A$ and $B$ are minimal. By minimality of $B$, there exists $x \in A$ of degree $1$. Let $y \in B$ be its only neighbor. Since $A$ is minimal, $y$ is also of degree $1$ (othw you could remove $x$ from $A$ and still be a VC). Thus $S'=A \setminus \{x\} \cup \{y\}$ is a non-trivial VC with $E[S'] = \emptyset$.  
> **username_3**: @username_1 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$.  
> **username_1**: You are right of course, you need the whole $A$ to cover $A$ if you only allow vertices there. I was trying to cover only the vertices in $B$...  
> **username_4**: Just to check my understanding of the problem, in the case that $|A|=|B|$ and $E=A\times B$, then the (minimal) non-trivial vertex covers are the sets of the form $A\cup\{b\}$ such that $b\in B$, or $\{a\}\cup B$ such that $a\in A$, and the minimum-cardinality VC covers are the perfect matchings in $G$?  
> **username_0**: 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  

---

## 0 answers

