<p>Just delete D together with its indicent edges and check if you can find a vertex cover for the remaining graph that is one smaller than that for the whole graph. If so, you can add D to it to get a minimum vertex cover that includes D; otherwise, there is no such vertex cover. (This doesn't depend on the bipartiteness at all.)</p>

CC BY-SA 3.0
2011-08-12T08:42:02.633Z
2011-08-12T08:42:02.633Z
Falk Hüffner
<p>I know that I can find the minimum vertex cover of a bipartite graph by first finding the maximum matching and then using <a href="http://en.wikipedia.org/wiki/K%C3%B6nig%27s_theorem_%28graph_theory%29#Algorithm" rel="nofollow">Konig's Theorem</a> to turn this matching into a vertex cover of the same order.  </p>

<p>The result obtained is only one of what could be many valid vertex covers. In the following graph, {A,B}, {C,D}, and {B,C} are all valid covers. Applying the Konig method yields the cover {A,B}.*  </p>

<pre><code>(A)=====(C)
       /
     /
   /
(B)=====(D)
</code></pre>

<p>How would you check for the existence of a minimum vertex cover that includes a given important vertex, say, vertex D?</p>

<p>My first guess is to <em>flip</em> the graph and find another minimum vertex cover. In the above case, this would yield {C,D}. If neither solution contains the important vertex, it's not part of any minimum cover.  However, I haven't been able to prove this to myself.</p>

<p>*A little elaboration: edge AC and BD form the matching. In the algorithm described above, you start by treating the graph asymmetrically, labeling the sides L (left) and R (right). Initially, all L and none of the R vertices are part of the vertex cover. Now build a new set T of vertices by traversing according to the following rule: Start at the exposed vertices (not part of any matching) on the left side, travel right along all unmatched edges, then travel left along all matched edges, continuing back and forth until path termination. All visited vertices are added to set T.  Set T is subtracted from L and added to R to produce the vertex cover solution. In the example graph, there is NO traversal, since there are no exposed vertices on the left side.</p>

<graph-theory>
Bipartite vertex cover with a Very Important Vertex
Matt M.
# Bipartite vertex cover with a Very Important Vertex

(Asked by: username_0 on 2011-08-12)

I know that I can find the minimum vertex cover of a bipartite graph by first finding the maximum matching and then using Konig's Theorem to turn this matching into a vertex cover of the same order.  
The result obtained is only one of what could be many valid vertex covers. In the following graph, {A,B}, {C,D}, and {B,C} are all valid covers. Applying the Konig method yields the cover {A,B}.*  
(A)=====(C)
       /
     /
   /
(B)=====(D)

How would you check for the existence of a minimum vertex cover that includes a given important vertex, say, vertex D?
My first guess is to flip the graph and find another minimum vertex cover. In the above case, this would yield {C,D}. If neither solution contains the important vertex, it's not part of any minimum cover.  However, I haven't been able to prove this to myself.
*A little elaboration: edge AC and BD form the matching. In the algorithm described above, you start by treating the graph asymmetrically, labeling the sides L (left) and R (right). Initially, all L and none of the R vertices are part of the vertex cover. Now build a new set T of vertices by traversing according to the following rule: Start at the exposed vertices (not part of any matching) on the left side, travel right along all unmatched edges, then travel left along all matched edges, continuing back and forth until path termination. All visited vertices are added to set T.  Set T is subtracted from L and added to R to produce the vertex cover solution. In the example graph, there is NO traversal, since there are no exposed vertices on the left side.

**Tags:** graph-theory

---

## 1 answers

### Answer by username_1 on 2011-08-12. Score: 8 | Accepted answer

Just delete D together with its indicent edges and check if you can find a vertex cover for the remaining graph that is one smaller than that for the whole graph. If so, you can add D to it to get a minimum vertex cover that includes D; otherwise, there is no such vertex cover. (This doesn't depend on the bipartiteness at all.)


---

