Graph Matching: Augmenting Path

Introduction

Let \(G=(V, E)\) be an undirected graph. Matching in \(G\) is a subset of edges \(M \subseteq E\) such that at most one edge is incident to each vertex in \(V\).

A vertex is matched is it is incident to some edge in \(M\), otherwise it is called free or exposed.

Augmenting Paths

• Alternating path: a path in which the edges belong alternatively to the matching and not to the matching
• Augmenting path: an alternating path that starts from and ends on exposed vertices

Clearly, an augmenting path can be ‘flipped’ to increase the matching size by one, i.e., just make free vertex matched and make matched vertex free in this path.

Berge’s Theorem: The matching M is maximum iff there is no augmenting path w.r.t. \(M\). I personally think the proof is easy but quite powerful.

Thus, we can immediately use the theorem to design an algorithm: find augmenting path iteratively until no more can be found. The problem is how we can find the augmenting path.

Algorithm for bipartite graph

FIND-AUGMENTING-PATH(\(G=(V_1 \cup V_2, E), M\))

• \(V'_1\) = a set of free vertices in \(V_1\)
• \(V'_2\) = a set of free vertices in \(V_2\)
• Construct the directed graph \(G_M = (V_1 \cup V_2, E_M)\)
  • \(E_M\) is a set of directed edges such that it includes all arcs from \(V_1\) to \(V_2\), and all matching arcs from \(V_2\) to \(V_1\)
  • i.e., \(E_M = \\{(v_1, v_2) : v_1, v_2 \in E \setminus M, v_1 \in V_1, v_2 \in V_2\\} \cup \\{(v_2, v_1) : v_1, v_2 \in M, v_1 \in V_1, v_2 \in V_2\\}\)
• Find a simple path \(p\) from \(V'\_1\) to \(V'\_2\) in \(G_M\)

Note that the above graph \(G\_M\) is similar to the residual network in network flow. Apparently, \(p\) starts from a free vertex in \(V'\_1\) and ends at another free vertex in \(V'\_2\), thus it is an augmenting path.

Complexity

The maximum size of matching is upper bounded by \(\vert V\vert /2\), and each step, the matching size is incremented by one. Thus, the number of augmenting path found will be at most \(O(\vert V\vert )\). At each step, it takes \(O(\vert E\vert )\) to find a path. Thus the overall running time is \(O(\vert V\vert E\vert )\).