Indian Computing Olympiad

Advanced graph algorithms

Bipartite matching

A disjoint set of edges in a graph such that no two edges share a vertex is called a matching.

• Maximal matching: A matching that cannot be extended further
• Maximum matching: A matching whose size, in number of edges is maximized
• Perfect matching:All vertices are part of some edge in the set

A bipartite graph is one in which we can separate the vertices into two disjoint sets, V0 and V1 so that all edges go only from V0 to V1—there is no edge within either set.

Finding a matching in a bipartite graph:

Start with an empty matching.

Assume we have selected some edges for our matching and we cannot find any disjoint edge to add to the current matching.

Say that a vertex is matched if it is covered by the current matching. Otherwise, it is unmatched.

For instance: u and v are unmatched below (the edges marked --- are in the current matching, the edges marked ... are not in the matching).

                a....d....v
               .|    |    ..
              . |    |    . .
             u  |    |    .  e
              . |    |    . /
               .|    |    ./
                b....c....f
      

To extend this matching further we identify an alternating (augmenting) path.

An alternating (augmenting) path is a path in the graph that

• starts and ends at unmatched vertices (i.e., they are not part of the current matching)
• Thus, the first and last edges in the path are not part of the current matching.
• the edges in the path alternate between matching edges and non-matching edges

An alternating (augmenting) path looks like the following.

       ..... ----- ..... ----- ..... ----- .....

            ..... = edges that do not belong to current matching
            ----- = edges that belong to current matching
      

For instance: u-a-b-c-d-v is an augmenting path

                a....d....v
               .|    |    ..
              . |    |    . .
             u  |    |    .  e
              . |    |    . /
               .|    |    ./
                b....c....f
      

If we find an alternating (augmenting) path, we invert the sense of all edges in the path---matching edges become non matching and vice versa. Thus,

       ..... _____ ..... _____ ..... _____ .....
      

becomes

        _____ ..... _____ ..... _____ ..... _____
      

and we increase the matching by one.

In the example above, we invert the path u-a-b-c-d-v to get

                a....d----v
               /.    .    ..
              / .    .    . .
             u  .    .    .  e
              . .    .    . /
               ..    .    ./
                b----c....f
      

We stop when no alternating (augmenting) paths can be found.

How do we find an alternating (augmenting) path?

To find an augmenting path, use BFS from an unmatched vertex, exploring only non-matching/matching edges at alternate levels. In other words, when exploring the neighbours of a matched vertex, choose only matching edges (actually, there will always be exactly one matching edge to explore).

This algorithm takes time M N (for each unmatched vertex, do a BFS to find an alternating path).

Can we overlap the M BFS computations for the M unmatched vertex and do them in parallel?

Initialize BFS queue with all M unmarked vertices, marking them as visited and at level 0. Now, we might have an augmenting path that passes from one unmarked vertex u via another unmarked vertex v. In this parallel BFS, we will not explore this path because when we reach v, we will find v already marked. However, notice that the suffix of the path starting from v is also an augmenting path on its own (the segment from u to v must be of even length, the total path is of odd length, so the suffix starting at v is a path of odd length that starts and ends at an unmarked vertex.) Thus, we can take the suffix starting at v as the augmenting path.