As so you all know, we have Hopcroft–Karp Algorithm for maximum matching between two sides in a bipartite graph. It runs in $O(\sqrt{V} \times E)$ where $V$ is the vertex set and $E$ is the edges set.
I am looking for an algorithm that will fit more efficiently for a dynamic graph.
At each iteration i
, for graph G
in that iteration (Denote G_i
) I'm adding one node maximum for each side, and connecting some edges between the existing nodes and the new nodes that are being added. This will be graph G_(i+1)
.
The Question:
Given a maximum matching in G_i
can I efficiently calculate maximum matching in G_(i+1)
(and avoid running Hopcroft–Karp Algorithm every time)?
What I have tried:
For starters, the matching in G_(i+1)
can only increase by one since I am adding at most one node to each side. If some edge connects to some node that is not in the matching, I just add both nodes to the matching of G_(i+1)
, Otherwise, I am trying to do what we did in Hopcroft–Karp Algorithm, Finding an augmenting path.
An augmenting path is a simple path that starts with a node v
that doesn't appear in the matching and ends with node u
that is on the opposite side of v
. The path itself is alternating between an edge in the matching and an edge not in the matching.