1
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.