Flow-based algorithm The simplest way to compute a maximum-cardinality matching is to follow the
Ford–Fulkerson algorithm. This algorithm solves the more general problem of
computing the maximum flow. A bipartite graph can be converted to a
flow network as follows. • Add a source vertex ; add an edge from to each vertex in . • Add a sink vertex ; add an edge from each vertex in to . • Assign a capacity of 1 to each edge. Since each edge in the network has integral capacity, there exists a maximum flow where all flows are integers; these integers must be either 0 or 1 since the all capacities are 1. Each integral flow defines a matching in which an edge is in the matching
if and only if its flow is 1. It is a matching because: • The incoming flow into each vertex in is at most 1, so the outgoing flow is at most 1 too, so at most one edge adjacent to each vertex in is present. • The outgoing flow from each vertex in is at most 1, so the incoming flow is at most 1 too, so at most one edge adjacent to each vertex in is present. The Ford–Fulkerson algorithm proceeds by repeatedly finding an augmenting path from some to some and updating the matching by taking the
symmetric difference of that path with (assuming such a path exists). As each path can be found in time, the running time is , and the maximum matching consists of the edges of that carry flow from to .
Advanced algorithms An improvement to this algorithm is given by the more elaborate
Hopcroft–Karp algorithm, which searches for multiple augmenting paths simultaneously. This algorithm runs in O(\sqrt{V}E) time. The algorithm of Chandran and Hochbaum • For
planar bipartite graphs, the problem can be solved in time where is the number of vertices, by reducing the problem to
maximum flow with multiple sources and sinks. == Algorithms for arbitrary graphs ==