Matching basics

A **matching** in an undirected graph is a set of edges that share no vertex. Every vertex is touched by at most one chosen edge. A vertex that is an end of a chosen edge is **matched** (its other end is its **mate**); every other vertex is **free**, also called unmatched or exposed.

The **size** of a matching is its number of edges, not its number of matched vertices. A matching of size k matches exactly 2k vertices, so a graph with n vertices has a matching of size at most n / 2. A **perfect** matching leaves no vertex free (only possible when n is even); a **near-perfect** matching leaves exactly one.

In this chapter a matching is stored in one of two equivalent ways: as a list of edges {a, b}, or as an array mate[v] holding the partner of v or -1 for a free vertex. The array form makes the questions the algorithms ask, such as “is v free?” and “who is v paired with?”, constant-time.

1// a matching is a list of edges {a, b}; it is valid when no vertex appears twice
2static boolean isMatching(int n, int[][] matching) {
3    boolean[] used = new boolean[n];
4    for (int[] e : matching) {
5        if (e[0] == e[1] || used[e[0]] || used[e[1]]) return false;
6        used[e[0]] = true;
7        used[e[1]] = true;
8    }
9    return true;
10}
11static List<Integer> freeVertices(int n, int[][] matching) {          // the unmatched vertices
12    boolean[] used = new boolean[n];
13    for (int[] e : matching) { used[e[0]] = true; used[e[1]] = true; }
14    List<Integer> free = new ArrayList<>();
15    for (int v = 0; v < n; v++) if (!used[v]) free.add(v);
16    return free;
17}

An **alternating path** is a path whose edges alternate between edges that are **not** in the matching and edges that **are**. Starting from a free vertex, the first edge is a non-matching edge, the second is a matching edge, the third non-matching, and so on.

Think of it as a re-pairing proposal. Moving along a non-matching edge says “let these two be partners”; the next matching edge says “then this vertex loses its old partner”, and that partner needs a new one, which the following non-matching edge supplies. An alternating path is exactly a chain of such swaps.

In a bipartite graph an alternating search from a free left vertex has a rigid shape: it leaves a left vertex along any non-matching edge, arrives at a right vertex, and must leave along that vertex's unique matching edge back to the left side. This is the search the next lessons use.

• Edge number 1, 3, 5, … (counting from 1) are non-matching edges; edge number 2, 4, 6, … are matching edges.
• An alternating path may start at a matched vertex too; it is **augmenting** only when both ends are free.
• An alternating **cycle** returns to its start; flipping it keeps the size but changes which edges are used.

1// mate[v] = partner of v, or -1 when v is free; the path is a vertex sequence
2static boolean isAlternating(int[] path, int[] mate) {                // free, matched, free, matched, ...
3    for (int i = 0; i + 1 < path.length; i++) {
4        boolean matched = mate[path[i]] == path[i + 1];
5        if (matched != (i % 2 == 1)) return false;                    // odd-numbered edges must be matching edges
6    }
7    return true;
8}

An **augmenting path** is an alternating path that starts at a free vertex and ends at a different free vertex. It therefore has an odd number of edges: k matching edges and k + 1 non-matching edges for some k ≥ 0.

**Flipping** the path swaps the roles of its edges: the k + 1 non-matching edges become matching edges and the k matching edges stop being matching edges. Interior vertices stay matched (they just get a new mate) and the two free end vertices become matched. The matching grows by exactly one edge.

**Berge's theorem** states the whole idea in one line: a matching is maximum if and only if the graph has no augmenting path for it. Every matching algorithm in this chapter is therefore a way of searching for augmenting paths until none is left. Open the animation and load “Greedy gets stuck; a path of length 5 fixes it”: after the greedy step the matching has 2 edges, a single augmenting path of 5 edges is found from vertex 0, and flipping it gives 3.

1static boolean isAugmenting(int[] path, int[] mate) {                 // mate[v] = partner or -1
2    if (path.length < 2 || path.length % 2 == 1) return false;        // an augmenting path has an odd number of edges
3    if (mate[path[0]] != -1 || mate[path[path.length - 1]] != -1) return false;   // both ends are free
4    for (int i = 0; i + 1 < path.length; i++)
5        if ((mate[path[i]] == path[i + 1]) != (i % 2 == 1)) return false;          // edges alternate: free, matched, free, ...
6    return true;
7}
8static void augment(int[] path, int[] mate) {                         // flip the path: one more matched edge
9    for (int i = 0; i + 1 < path.length; i += 2) {
10        mate[path[i]] = path[i + 1];
11        mate[path[i + 1]] = path[i];
12    }
13}

1@SuppressWarnings("unchecked")
2static int maxMatching(int left, int right, int[][] edges) {          // edges {leftVertex, rightVertex}
3    List<Integer>[] adj = new List[left];
4    for (int u = 0; u < left; u++) adj[u] = new ArrayList<>();
5    for (int[] e : edges) adj[e[0]].add(e[1]);
6    int[] matchL = new int[left], matchR = new int[right];
7    Arrays.fill(matchL, -1);
8    Arrays.fill(matchR, -1);
9    int size = 0;
10    for (int[] e : edges) {                                           // 1. greedy: a maximal matching, edges in input order
11        if (matchL[e[0]] == -1 && matchR[e[1]] == -1) { matchL[e[0]] = e[1]; matchR[e[1]] = e[0]; size++; }
12    }
13    for (int root = 0; root < left; root++) {                         // 2. try to augment from every free left vertex
14        if (matchL[root] != -1) continue;
15        int[] parent = new int[right];                                // parent[v]: left vertex from which v was reached
16        Arrays.fill(parent, -1);
17        Deque<Integer> queue = new ArrayDeque<>(List.of(root));
18        int end = -1;
19        while (!queue.isEmpty() && end == -1) {                       // alternating BFS
20            int u = queue.poll();
21            for (int v : adj[u]) {
22                if (parent[v] != -1) continue;
23                parent[v] = u;                                        // arrive at v by a non-matching edge
24                if (matchR[v] == -1) { end = v; break; }              // free right vertex: augmenting path found
25                queue.add(matchR[v]);                                 // leave v by its matching edge
26            }
27        }
28        if (end == -1) continue;                                      // no augmenting path from root, ever
29        for (int v = end; v != -1; ) {                                // flip the path
30            int u = parent[v], previous = matchL[u];
31            matchL[u] = v;
32            matchR[v] = u;
33            v = previous;
34        }
35        size++;
36    }
37    return size;
38}

A matching is **maximal** when no further edge can be added without breaking the matching: every edge has at least one matched end. A matching is **maximum** when no other matching is larger. Maximum implies maximal, but not the other way round.

The greedy rule “scan the edges and take every edge whose ends are both free” always produces a maximal matching, and it is fast, but it can be unlucky. With edges 0-0′, 0-1′, 1-0′ (left vertices 0, 1, right vertices 0′, 1′) greedy takes 0-0′ first and is then stuck at size 1, although 0-1′ and 1-0′ form a matching of size 2. Run the animation with “Greedy is stuck at 1; one swap reaches 2” to see the augmenting path 1 → 0′ → 0 → 1′ repair it.

The damage greedy can do is bounded: every maximal matching has at least **half** the size of a maximum matching, because each edge of a maximum matching shares a vertex with some edge of a maximal one, and each edge of the maximal matching can block at most two of them. So greedy is a 2-approximation, which is fine for rough answers but not for exact ones.

1static int[][] greedyMaximal(int n, int[][] edges) {                  // takes edges in the given order
2    boolean[] used = new boolean[n];
3    List<int[]> matching = new ArrayList<>();
4    for (int[] e : edges) {
5        if (e[0] != e[1] && !used[e[0]] && !used[e[1]]) {
6            used[e[0]] = true;
7            used[e[1]] = true;
8            matching.add(e);
9        }
10    }
11    return matching.toArray(new int[0][]);
12}
13static boolean isMaximal(int n, int[][] edges, int[][] matching) {    // no edge could still be added
14    boolean[] used = new boolean[n];
15    for (int[] e : matching) { used[e[0]] = true; used[e[1]] = true; }
16    for (int[] e : edges) if (e[0] != e[1] && !used[e[0]] && !used[e[1]]) return false;
17    return true;
18}