1
$\begingroup$

Assume that there is a maximal matching of size k in an bipartite graph, G=(U,V,E). I now want to utilize this maximal matching in order to find a maximal matching in the bipartite graph where we add some node u to U and some edges (u,v_1),...,(u,v_n), where v_1,...,v_n are vertices in V.

I have figured out that such an extension may yield a maximal matching of maximum size k+1. Thus I want to formulate an algorithm which finds a maximal matching of size k+1, if one exist. It is clear that if such a matching exist, then it must include the added vertex u. If there exist some v, adjacent to u that is not included in the optimal solution of size k, then we are done as we found a maximal matching of size k+1. In the case where there are no "available" adjacent vertices. Firstly we have to remove some pair which includes one of the occupied adjacent node and connect it with u instead. We now have to rearrange the matching in some clever way, but I'm not sure how to proceed from here, any suggestions?

$\endgroup$
0

1 Answer 1

0
$\begingroup$

Let $M$ be a maximum matching of graph $G = (V,E)$. Let $G'$ be a new graph after adding a new vertex $u$ and the corresponding edges to $G$. Let $M'$ be a maximum matching of $G'$.

Create a flow network on graph $G'$ by creating new source and sink vertices. Send flow of value $|M|$ through the matching edges in $M$. Create a residual graph corresponding to this flow. If there is an augmenting path in the residual graph, then $G'$ has a matching of size $|M|+1$, otherwise not. The overall running time is $O(|V|+|E|)$.

$\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.