Maximum Matching in Bipartite Graphs: Theory and Algorithms

CSCE-411 Design and Analysis of Algorithms Spring 2025 Instructor: Jianer Chen Office: PETR 428 Phone: 845-4259 Email: chen@cse.tamu.edu Notes 31: Maximum matching in bipartite graphs

Graph Matching (on undirected graphs) Definition. An edge set M in an undirected graph G is a matching in G if no two edges in M share a common end. The Maximum Matching Problem. Given an undirected graph G, construct a maximum matching in G. Definition. An augmenting path (w.r.t a matching M) starts and ends at unmatched vertices and goes alternatively with edges not in M and in M Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G.

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. An augmenting path P w.r.t. M will give a matching larger than M G G Graph-Matching(G) 1. M = ; 2. while (there is an aug. path P) use P to make M larger; 3. Return (M)

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Finding an augmenting path: start from unmatched vertices, try to find an augmenting path that connects two unmatched vertices. level 0 1 An augmenting path P w.r.t. M will give a matching larger than M G 2 3 4 G Pretty much similar to BFS but: at even levels, expand all possible ways, but at odd levels, expand on a single matching edge. Graph-Matching(G) 1. M = ; 2. while (there is an aug. path P) use P to make M larger; 3. Return (M)

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Finding an augmenting path: start from unmatched vertices, try to find an augmenting path that connects two unmatched vertices. level 0 1 Augment(G, M) \\ Q is a queue 1. for (each vertex v of G) level[v] = -1; 2. for (each unmatched vertex v) level[v] = 0; dad[v] = -1; Q v; 3. while (Q ) v Q; if (level[v] is even) for (each edge [v, w]) if (level[w] == -1) level[w] = level[v]+1; dad[w] = v; Q w; else if (level[v] == level[w]) return an augmenting path; else \\ level[v] is odd let [v, w] be the edge in M; if (level[v] == level[w]) return an augmenting path; else level[w] = level[v]+1; dad[w] = v; Q w; 4. Return (false) 2 3 4 Pretty much similar to BFS but: at even levels, expand all possible ways, but at odd levels, expand on a single matching edge.

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Finding an augmenting path: start from unmatched vertices, try to find an augmenting path that connects two unmatched vertices. level 0 1 Augment(G, M) \\ Q is a queue 1. for (each vertex v of G) level[v] = -1; 2. for (each unmatched vertex v) level[v] = 0; dad[v] = -1; Q v; 3. while (Q ) v Q; if (level[v] is even) for (each edge [v, w]) if (level[w] == -1) level[w] = level[v]+1; dad[w] = v; Q w; else if (level[v] == level[w]) return an augmenting path; else \\ level[v] is odd let [v, w] be the edge in M; if (level[v] == level[w]) return an augmenting path; else level[w] = level[v]+1; dad[w] = v; Q w; 4. Return (false) 2 3 4 Pretty much similar to BFS but: at even levels, expand all possible ways, but at odd levels, expand on a single matching edge.

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Finding an augmenting path: start from unmatched vertices, try to find an augmenting path that connects two unmatched vertices. level 0 1 Augment(G, M) \\ Q is a queue 1. for (each vertex v of G) level[v] = -1; 2. for (each unmatched vertex v) level[v] = 0; dad[v] = -1; Q v; 3. while (Q ) v Q; if (level[v] is even) for (each edge [v, w]) if (level[w] == -1) level[w] = level[v]+1; dad[w] = v; Q w; else if (level[v] == level[w]) return an augmenting path; else \\ level[v] is odd let [v, w] be the edge in M; if (level[v] == level[w]) return an augmenting path; else level[w] = level[v]+1; dad[w] = v; Q w; 4. Return (false) 2 3 4 Pretty much similar to BFS but: at even levels, expand all possible ways, but at odd levels, expand on a single matching edge. The matching M can be given as an array M[1..n] such that M[i] = j (also M[j] = i) means that the edge [i, j] is in M. Time = O(n+m)

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. A tricky problem for this algorithm: Tracing two vertices at the same level may encounter a common ancestor. Augment(G, M) \\ Q is a queue 1. for (each vertex v of G) level[v] = -1; 2. for (each unmatched vertex v) level[v] = 0; dad[v] = -1; Q v; 3. while (Q ) v Q; if (level[v] is even) for (each edge [v, w]) if (level[w] == -1) level[w] = level[v]+1; dad[w] = v; Q w; else if (level[v] == level[w]) return an augmenting path; else \\ level[v] is odd let [v, w] be the edge in M; if (level[v] == level[w]) return an augmenting path; else level[w] = level[v]+1; dad[w] = v; Q w; 4. Return (false) Time = O(n+m)

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. A tricky problem for this algorithm: Tracing two vertices at the same level may encounter a common ancestor. Augment(G, M) \\ Q is a queue 1. for (each vertex v of G) level[v] = -1; 2. for (each unmatched vertex v) level[v] = 0; dad[v] = -1; Q v; 3. while (Q ) v Q; if (level[v] is even) for (each edge [v, w]) if (level[w] == -1) level[w] = level[v]+1; dad[w] = v; Q w; else if (level[v] == level[w]) return an augmenting path; else \\ level[v] is odd let [v, w] be the edge in M; if (level[v] == level[w]) return an augmenting path; else level[w] = level[v]+1; dad[w] = v; Q w; 4. Return (false) level 0 1 2 3 4 Time = O(n+m)

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. A tricky problem for this algorithm: Tracing two vertices at the same level may encounter a common ancestor. Augment(G, M) \\ Q is a queue 1. for (each vertex v of G) level[v] = -1; 2. for (each unmatched vertex v) level[v] = 0; dad[v] = -1; Q v; 3. while (Q ) v Q; if (level[v] is even) for (each edge [v, w]) if (level[w] == -1) level[w] = level[v]+1; dad[w] = v; Q w; else if (level[v] == level[w]) return an augmenting path; else \\ level[v] is odd let [v, w] be the edge in M; if (level[v] == level[w]) return an augmenting path; else level[w] = level[v]+1; dad[w] = v; Q w; 4. Return (false) level 0 1 2 3 4 Time = O(n+m)

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. A tricky problem for this algorithm: Tracing two vertices at the same level may encounter a common ancestor. Augment(G, M) \\ Q is a queue 1. for (each vertex v of G) level[v] = -1; 2. for (each unmatched vertex v) level[v] = 0; dad[v] = -1; Q v; 3. while (Q ) v Q; if (level[v] is even) for (each edge [v, w]) if (level[w] == -1) level[w] = level[v]+1; dad[w] = v; Q w; else if (level[v] == level[w]) return an augmenting path; else \\ level[v] is odd let [v, w] be the edge in M; if (level[v] == level[w]) return an augmenting path; else level[w] = level[v]+1; dad[w] = v; Q w; 4. Return (false) level 0 1 2 3 4 This bug was not even realized by early research. Time = O(n+m)

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. A tricky problem for this algorithm: Tracing two vertices at the same level may encounter a common ancestor. Augment(G, M) \\ Q is a queue 1. for (each vertex v of G) level[v] = -1; 2. for (each unmatched vertex v) level[v] = 0; dad[v] = -1; Q v; 3. while (Q ) v Q; if (level[v] is even) for (each edge [v, w]) if (level[w] == -1) level[w] = level[v]+1; dad[w] = v; Q w; else if (level[v] == level[w]) return an augmenting path; else \\ level[v] is odd let [v, w] be the edge in M; if (level[v] == level[w]) return an augmenting path; else level[w] = level[v]+1; dad[w] = v; Q w; 4. Return (false) level 0 1 2 3 4 This bug was not even realized by early research. If the graph is bipartite, then this will not happen. Time = O(n+m)

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. A tricky problem for this algorithm: Tracing two vertices at the same level may encounter a common ancestor. Augment(G, M) \\ Q is a queue 1. for (each vertex v of G) level[v] = -1; 2. for (each unmatched vertex v) level[v] = 0; dad[v] = -1; Q v; 3. while (Q ) v Q; if (level[v] is even) for (each edge [v, w]) if (level[w] == -1) level[w] = level[v]+1; dad[w] = v; Q w; else if (level[v] == level[w]) return an augmenting path; else \\ level[v] is odd let [v, w] be the edge in M; if (level[v] == level[w]) return an augmenting path; else level[w] = level[v]+1; dad[w] = v; Q w; 4. Return (false) level 0 1 2 3 4 This bug was not even realized by early research. If the graph is bipartite, then this will not happen. But, can we have other problems? Time = O(n+m)

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Can we have other problems, for bipartite graphs? Augment(G, M) \\ Q is a queue 1. for (each vertex v of G) level[v] = -1; 2. for (each unmatched vertex v) level[v] = 0; dad[v] = -1; Q v; 3. while (Q ) v Q; if (level[v] is even) for (each edge [v, w]) if (level[w] == -1) level[w] = level[v]+1; dad[w] = v; Q w; else if (level[v] == level[w]) return an augmenting path; else \\ level[v] is odd let [v, w] be the edge in M; if (level[v] == level[w]) return an augmenting path; else level[w] = level[v]+1; dad[w] = v; Q w; 4. Return (false) Time = O(n+m)

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Can we have other problems, for bipartite graphs? Augment(G, M) \\ Q is a queue 1. for (each vertex v of G) level[v] = -1; 2. for (each unmatched vertex v) level[v] = 0; dad[v] = -1; Q v; 3. while (Q ) v Q; if (level[v] is even) for (each edge [v, w]) if (level[w] == -1) level[w] = level[v]+1; dad[w] = v; Q w; else if (level[v] == level[w]) return an augmenting path; else \\ level[v] is odd let [v, w] be the edge in M; if (level[v] == level[w]) return an augmenting path; else level[w] = level[v]+1; dad[w] = v; Q w; 4. Return (false) level 0 1 2 3 4 Time = O(n+m)

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Can we have other problems, for bipartite graphs? Augment(G, M) \\ Q is a queue 1. for (each vertex v of G) level[v] = -1; 2. for (each unmatched vertex v) level[v] = 0; dad[v] = -1; Q v; 3. while (Q ) v Q; if (level[v] is even) for (each edge [v, w]) if (level[w] == -1) level[w] = level[v]+1; dad[w] = v; Q w; else if (level[v] == level[w]) return an augmenting path; else \\ level[v] is odd let [v, w] be the edge in M; if (level[v] == level[w]) return an augmenting path; else level[w] = level[v]+1; dad[w] = v; Q w; 4. Return (false) level 0 1 2 3 4 Time = O(n+m)

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Can we have other problems, for bipartite graphs? Augment(G, M) \\ Q is a queue 1. for (each vertex v of G) level[v] = -1; 2. for (each unmatched vertex v) level[v] = 0; dad[v] = -1; Q v; 3. while (Q ) v Q; if (level[v] is even) for (each edge [v, w]) if (level[w] == -1) level[w] = level[v]+1; dad[w] = v; Q w; else if (level[v] == level[w]) return an augmenting path; else \\ level[v] is odd let [v, w] be the edge in M; if (level[v] == level[w]) return an augmenting path; else level[w] = level[v]+1; dad[w] = v; Q w; 4. Return (false) level 0 1 2 3 4 Time = O(n+m)

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Can we have other problems, for bipartite graphs? Augment(G, M) \\ Q is a queue 1. for (each vertex v of G) level[v] = -1; 2. for (each unmatched vertex v) level[v] = 0; dad[v] = -1; Q v; 3. while (Q ) v Q; if (level[v] is even) for (each edge [v, w]) if (level[w] == -1) level[w] = level[v]+1; dad[w] = v; Q w; else if (level[v] == level[w]) return an augmenting path; else \\ level[v] is odd let [v, w] be the edge in M; if (level[v] == level[w]) return an augmenting path; else level[w] = level[v]+1; dad[w] = v; Q w; 4. Return (false) level 0 1 2 3 4 If there is a horizontal edge, then there is an augmenting path (in bipartite graphs). Time = O(n+m)

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Can we have other problems, for bipartite graphs? Augment(G, M) \\ Q is a queue 1. for (each vertex v of G) level[v] = -1; 2. for (each unmatched vertex v) level[v] = 0; dad[v] = -1; Q v; 3. while (Q ) v Q; if (level[v] is even) for (each edge [v, w]) if (level[w] == -1) level[w] = level[v]+1; dad[w] = v; Q w; else if (level[v] == level[w]) return an augmenting path; else \\ level[v] is odd let [v, w] be the edge in M; if (level[v] == level[w]) return an augmenting path; else level[w] = level[v]+1; dad[w] = v; Q w; 4. Return (false) level 0 1 2 3 4 If there is a horizontal edge, then there is an augmenting path (in bipartite graphs). If there is an augmenting path, must there be a horizontal edge? Time = O(n+m)

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Can we have other problems, for bipartite graphs? Augment(G, M) \\ Q is a queue 1. for (each vertex v of G) level[v] = -1; 2. for (each unmatched vertex v) level[v] = 0; dad[v] = -1; Q v; 3. while (Q ) v Q; if (level[v] is even) for (each edge [v, w]) if (level[w] == -1) level[w] = level[v]+1; dad[w] = v; Q w; else if (level[v] == level[w]) return an augmenting path; else \\ level[v] is odd let [v, w] be the edge in M; if (level[v] == level[w]) return an augmenting path; else level[w] = level[v]+1; dad[w] = v; Q w; 4. Return (false) level 0 1 2 3 4 If there is a horizontal edge, then there is an augmenting path (in bipartite graphs). If there is an augmenting path, must there be a horizontal edge? Yes, there is a shortest augmenting path that has a horizontal edge. Time = O(n+m)

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Can we have other problems, for bipartite graphs? Augment(G, M) \\ Q is a queue 1. for (each vertex v of G) level[v] = -1; 2. for (each unmatched vertex v) level[v] = 0; dad[v] = -1; Q v; 3. while (Q ) v Q; if (level[v] is even) for (each edge [v, w]) if (level[w] == -1) level[w] = level[v]+1; dad[w] = v; Q w; else if (level[v] == level[w]) return an augmenting path; else \\ level[v] is odd let [v, w] be the edge in M; if (level[v] == level[w]) return an augmenting path; else level[w] = level[v]+1; dad[w] = v; Q w; 4. Return (false) level 0 1 2 3 4 If there is a horizontal edge, then there is an augmenting path (in bipartite graphs). If there is an augmenting path, must there be a horizontal edge? Yes, there is a shortest augmenting path that has a horizontal edge. What edges are missing in the above figure? Time = O(n+m)

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Can we have other problems, for bipartite graphs? Augment(G, M) \\ Q is a queue 1. for (each vertex v of G) level[v] = -1; 2. for (each unmatched vertex v) level[v] = 0; dad[v] = -1; Q v; 3. while (Q ) v Q; if (level[v] is even) for (each edge [v, w]) if (level[w] == -1) level[w] = level[v]+1; dad[w] = v; Q w; else if (level[v] == level[w]) return an augmenting path; else \\ level[v] is odd let [v, w] be the edge in M; if (level[v] == level[w]) return an augmenting path; else level[w] = level[v]+1; dad[w] = v; Q w; 4. Return (false) edges connecting level 0 1 * 2 even levels? X 2 3 4 If there is a horizontal edge, then there is an augmenting path (in bipartite graphs). If there is an augmenting path, must there be a horizontal edge? Yes, there is a shortest augmenting path that has a horizontal edge. What edges are missing in the above figure? Time = O(n+m)

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Can we have other problems, for bipartite graphs? Augment(G, M) \\ Q is a queue 1. for (each vertex v of G) level[v] = -1; 2. for (each unmatched vertex v) level[v] = 0; dad[v] = -1; Q v; 3. while (Q ) v Q; if (level[v] is even) for (each edge [v, w]) if (level[w] == -1) level[w] = level[v]+1; dad[w] = v; Q w; else if (level[v] == level[w]) return an augmenting path; else \\ level[v] is odd let [v, w] be the edge in M; if (level[v] == level[w]) return an augmenting path; else level[w] = level[v]+1; dad[w] = v; Q w; 4. Return (false) edges connecting level 0 1 * 2 even levels? X * 2 odd levels? The edge must not be in M 2 3 4 If there is a horizontal edge, then there is an augmenting path (in bipartite graphs). If there is an augmenting path, must there be a horizontal edge? Yes, there is a shortest augmenting path that has a horizontal edge. What edges are missing in the above figure? Time = O(n+m)

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Can we have other problems, for bipartite graphs? Augment(G, M) \\ Q is a queue 1. for (each vertex v of G) level[v] = -1; 2. for (each unmatched vertex v) level[v] = 0; dad[v] = -1; Q v; 3. while (Q ) v Q; if (level[v] is even) for (each edge [v, w]) if (level[w] == -1) level[w] = level[v]+1; dad[w] = v; Q w; else if (level[v] == level[w]) return an augmenting path; else \\ level[v] is odd let [v, w] be the edge in M; if (level[v] == level[w]) return an augmenting path; else level[w] = level[v]+1; dad[w] = v; Q w; 4. Return (false) edges connecting level 0 1 * 2 even levels? X * 2 odd levels? The edge must not be in M 2 3 * Lower even to higher odd? must be adjacent 4 If there is a horizontal edge, then there is an augmenting path (in bipartite graphs). If there is an augmenting path, must there be a horizontal edge? Yes, there is a shortest augmenting path that has a horizontal edge. What edges are missing in the above figure? Time = O(n+m)

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Can we have other problems, for bipartite graphs? Augment(G, M) \\ Q is a queue 1. for (each vertex v of G) level[v] = -1; 2. for (each unmatched vertex v) level[v] = 0; dad[v] = -1; Q v; 3. while (Q ) v Q; if (level[v] is even) for (each edge [v, w]) if (level[w] == -1) level[w] = level[v]+1; dad[w] = v; Q w; else if (level[v] == level[w]) return an augmenting path; else \\ level[v] is odd let [v, w] be the edge in M; if (level[v] == level[w]) return an augmenting path; else level[w] = level[v]+1; dad[w] = v; Q w; 4. Return (false) edges connecting level 0 1 * 2 even levels? X * 2 odd levels? The edge must not be in M 2 3 * Lower even to higher odd? must be adjacent 4 * Lower odd to higher even? If there is a horizontal edge, then there is an augmenting path (in bipartite graphs). If there is an augmenting path, must there be a horizontal edge? Yes, there is a shortest augmenting path that has a horizontal edge. What edges are missing in the above figure? Time = O(n+m)

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Can we have other problems, for bipartite graphs? Augment(G, M) \\ Q is a queue 1. for (each vertex v of G) level[v] = -1; 2. for (each unmatched vertex v) level[v] = 0; dad[v] = -1; Q v; 3. while (Q ) v Q; if (level[v] is even) for (each edge [v, w]) if (level[w] == -1) level[w] = level[v]+1; dad[w] = v; Q w; else if (level[v] == level[w]) return an augmenting path; else \\ level[v] is odd let [v, w] be the edge in M; if (level[v] == level[w]) return an augmenting path; else level[w] = level[v]+1; dad[w] = v; Q w; 4. Return (false) edges connecting level 0 1 A shortest aug. path must connect two unmatched vertices, so it must cross two tree paths by a horizontal edge. * 2 even levels? X * 2 odd levels? The edge must not be in M 2 3 * Lower even to higher odd? must be adjacent 4 * Lower odd to higher even? If there is a horizontal edge, then there is an augmenting path (in bipartite graphs). If there is an augmenting path, must there be a horizontal edge? Yes, there is a shortest augmenting path that has a horizontal edge. What edges are missing in the above figure? Time = O(n+m)

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Can we have other problems, for bipartite graphs? Augment(G, M) \\ Q is a queue 1. for (each vertex v of G) level[v] = -1; 2. for (each unmatched vertex v) level[v] = 0; dad[v] = -1; Q v; 3. while (Q ) v Q; if (level[v] is even) for (each edge [v, w]) if (level[w] == -1) level[w] = level[v]+1; dad[w] = v; Q w; else if (level[v] == level[w]) return an augmenting path; else \\ level[v] is odd let [v, w] be the edge in M; if (level[v] == level[w]) return an augmenting path; else level[w] = level[v]+1; dad[w] = v; Q w; 4. Return (false) edges connecting level 0 1 A shortest aug. path must connect two unmatched vertices, so it must cross two tree paths by a horizontal edge. * 2 even levels? X * 2 odd levels? The edge must not be in M 2 3 * Lower even to higher odd? must be adjacent 4 * Lower odd to higher even? Therefore, the algorithm works correctly for bipartite graphs. Time = O(n+m)

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. The matching algorithm for bipartite graphs Augment(G, M) \\ Q is a queue 1. for (each vertex v of G) level[v] = -1; 2. for (each unmatched vertex v) level[v] = 0; dad[v] = -1; Q v; 3. while (Q ) v Q; if (level[v] is even) for (each edge [v, w]) if (level[w] == -1) level[w] = level[v]+1; dad[w] = v; Q w; else if (level[v] == level[w]) return an augmenting path; else \\ level[v] is odd let [v, w] be the edge in M; if (level[v] == level[w]) return an augmenting path; else level[w] = level[v]+1; dad[w] = v; Q w; 4. Return (false) Bipartite-Matching(G) 1. Let M consists of any single edge; 2. while (P = Augment(G, M) false) Let M = M P; 3. Return (M). Time = O(n m) The matching M can be given as an array M[1..n] such that M[i] = j (also M[j] = i) means that the edge [i, j] is in M. Time = O(n+m)

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. The matching algorithm for bipartite graphs Augment(G, M) \\ Q is a queue 1. for (each vertex v of G) level[v] = -1; 2. for (each unmatched vertex v) level[v] = 0; dad[v] = -1; Q v; 3. while (Q ) v Q; if (level[v] is even) for (each edge [v, w]) if (level[w] == -1) level[w] = level[v]+1; dad[w] = v; Q w; else if (level[v] == level[w]) return an augmenting path; else \\ level[v] is odd let [v, w] be the edge in M; if (level[v] == level[w]) return an augmenting path; else level[w] = level[v]+1; dad[w] = v; Q w; 4. Return (false) Bipartite-Matching(G) 1. Let M consists of any single edge; 2. while (P = Augment(G, M) false) Let M = M P; 3. Return (M). Time = O(n m) Theorem. There is an O(nm)-time algorithm that, on a bipartite graph G with n vertices and m edges, constructs a maximum matching in G. The matching M can be given as an array M[1..n] such that M[i] = j (also M[j] = i) means that the edge [i, j] is in M. Time = O(n+m)

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Remarks. The matching algorithm for bipartite graphs Bipartite-Matching(G) 1. Let M consists of any single edge; 2. while (P = Augment(G, M) false) Let M = M P; 3. Return (M). Time = O(n m) Theorem. There is an O(nm)-time algorithm that, on a bipartite graph G with n vertices and m edges, constructs a maximum matching in G. The matching M can be given as an array M[1..n] such that M[i] = j (also M[j] = i) means that the edge [i, j] is in M.

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Remarks. 1. In step 1 of the algorithm, you can start with a maximal matching, which will reduce to time complexity to at least one half. The matching algorithm for bipartite graphs Bipartite-Matching(G) 1. Let M consists of any single edge; 2. while (P = Augment(G, M) false) Let M = M P; 3. Return (M). Time = O(n m) Theorem. There is an O(nm)-time algorithm that, on a bipartite graph G with n vertices and m edges, constructs a maximum matching in G. The matching M can be given as an array M[1..n] such that M[i] = j (also M[j] = i) means that the edge [i, j] is in M.

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Remarks. 1. In step 1 of the algorithm, you can start with a maximal matching, which will reduce to time complexity to at least one half. The matching algorithm for bipartite graphs Bipartite-Matching(G) 1. Let M consists of any single edge; 2. while (P = Augment(G, M) false) Let M = M P; 3. Return (M). 2. The best algorithm for bipartite graph matching runs in time O(m n). Time = O(n m) Theorem. There is an O(nm)-time algorithm that, on a bipartite graph G with n vertices and m edges, constructs a maximum matching in G. The matching M can be given as an array M[1..n] such that M[i] = j (also M[j] = i) means that the edge [i, j] is in M.

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Remarks. 1. In step 1 of the algorithm, you can start with a maximal matching, which will reduce to time complexity to at least one half. The matching algorithm for bipartite graphs Bipartite-Matching(G) 1. Let M consists of any single edge; 2. while (P = Augment(G, M) false) Let M = M P; 3. Return (M). 2. The best algorithm for bipartite graph matching runs in time O(m n). Time = O(n m) 3. Maximum matching for general graphs becomes much more complicated, but still can be solvable in time O(m n). Theorem. There is an O(nm)-time algorithm that, on a bipartite graph G with n vertices and m edges, constructs a maximum matching in G. The matching M can be given as an array M[1..n] such that M[i] = j (also M[j] = i) means that the edge [i, j] is in M.

Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Remarks. 1. In step 1 of the algorithm, you can start with a maximal matching, which will reduce to time complexity to at least one half. The matching algorithm for bipartite graphs Bipartite-Matching(G) 1. Let M consists of any single edge; 2. while (P = Augment(G, M) false) Let M = M P; 3. Return (M). 2. The best algorithm for bipartite graph matching runs in time O(m n). Time = O(n m) 3. Maximum matching for general graphs becomes much more complicated, but still can be solvable in time O(m n). Theorem. There is an O(nm)-time algorithm that, on a bipartite graph G with n vertices and m edges, constructs a maximum matching in G. 4. Maximum weighted matching (for bipartite and general) graphs has also been studied. The matching M can be given as an array M[1..n] such that M[i] = j (also M[j] = i) means that the edge [i, j] is in M.