1
$\begingroup$

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.

Illustration of augmenting path

$\endgroup$
2
  • 1
    $\begingroup$ If there is a larger matching it uses an edge incident with a new vertex, so you just need to look for an augmenting path starting with such an edge. $\endgroup$ Oct 28, 2022 at 11:29
  • $\begingroup$ Thank you very much $\endgroup$ Oct 30, 2022 at 5:32

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.