Matching

Given a collection of vertices that can be split into two groups (let’s say $U$ and $V$), we can define an edge $(u,v)$ to exist if $u$ is qualified for $v$.

Then, a matching is a collection of edges between $U$ and $V$ such that each vertex appears in at most one edge of the matching. A perfect matching occurs if every vertex is matched.

We can ask a few Optimization questions:

1. Given $(U,V,E)$, does there exist a perfect matching?
2. How fast can we find a perfect matching, if it exists?
3. If there is not, what is the maximum cardinality of a perfect matching within this set of vertices and edges?

Hall’s theorem

Assume that $G=(A,B,E)$ is bipartite. Then the claim is that there exists a perfect matching if and only if two conditions are met: first, that $|A|=|B|$, and second, that for any $U\subset A$, it is true that $|N(U)|\ge |U|$, where $N(U)$ is the set of all vertices that are neighbors of $U$.

Maximum matching

Algorithm

Create a source vertex $s$ that leads into all the vertices in one partition, and a sink vertex $t$ that all vertices in the other partition lead to. Create edges from all vertices from one partition, to all vertices in the other. Set the capacity of all edges to 1. Then, run a Maximum flow algorithm.

Runtime

• With FF: runtime becomes $O(m\cdot \text{max flow})=O(mn)$
• Capacity scaling: $O(m^2)$
• EK: $O(m^{2}n)$

What happened? Edmunds-Karp is supposed to be one of the fastest max flow algorithm, but it’s the slowest one here.

Analysis

For EK, there are still $O(n)$ stages and BFS still takes $O(m)$ time. However, since all edges have capacity of 1, when we push flow on a path, all edges on the path are saturated. This means we create $d(f)$ back edges every iteration. So, instead of max $O(m)$ iterations, we actually have $O\left(\frac{m}{d(f)}\right)$ of them.

$$\sum _{d=1}^{n}O(m)\cdot O\left(\frac{m}{d}\right)=O(m^2)\cdot \sum _{d=1}^n\frac{1}{d}\approx O(m^2\log n)$$

So we already have a speed up by just observing the nature of our bipartite graph.