> For the complete documentation index, see [llms.txt](https://evarga.gitbook.io/sh-intro-to-algs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://evarga.gitbook.io/sh-intro-to-algs/part-vi-graph-algorithms/25.-matchings-in-bipartite-graphs.md).

# 25. Matchings in Bipartite Graphs

## Exercises

### 25.1-1

Figure 25.3 already shows the first iteration with two $$M$$-augmenting paths of length 3. This creates a new matching $$M'$$ where only vertex $$l\_4 \in L$$ is unmatched. The next $$M'$$-augmenting path of length 5 $$l\_4 \to r\_2 \to l\_2 \to r\_1 \to l\_3 \to r\_6$$ creates a maximum matching (only vertex $$r\_8 \in R$$ is unmatched).

### 25.1-2

**Available in the latest revision of the IM.**

### 25.1-3

**Available in the latest revision of the IM.**

### 25.1-4

**Available in the latest revision of the IM.**

### ★ 25.1-5

**Available in the latest revision of the IM.**

### 25.1-6

**Available in the latest revision of the IM.**

### 25.2-1

Wikipedia provides [implementation details and time analysis](https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm#Implementation_details_and_time_analysis) of the Gale–Shapley algorithm, which also serves as a [constructive proof](https://en.wikipedia.org/wiki/Constructive_proof) that the required runtime complexity is attainable. The only difference is that instead of women and men it talks in terms of employers and applicants.

### 25.2-2

**Available in the latest revision of the IM.**

### 25.2-3

**Available in the latest revision of the IM.**

### 25.2-4

**Available in the latest revision of the IM.**

### 25.2-5

**Available in the latest revision of the IM.**

### 25.3-1

**Available in the latest revision of the IM.**

### 25.3-2

**Available in the latest revision of the IM.**

### 25.3-3

**Available in the latest revision of the IM.**

### 25.3-4

**Available in the latest revision of the IM.**

### 25.3-5

**Available in the latest revision of the IM.**

### 25.3-6

**Available in the latest revision of the IM.**

## Problems

### 25-1 Perfect matchings in a regular bipartite graph

#### a.

Read the proof of Theorem 13.1.1 in the chapter about [Euler Tours and Trails](https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_\(Morris\)/03%3A_Graph_Theory/13%3A_Euler_and_Hamilton/13.01%3A_Euler_Tours_and_Trails) from the online book authored by Joy Morris.

#### b.

See part (a) as well as [Hierholzer's algorithm](https://en.wikipedia.org/wiki/Eulerian_path#Hierholzer's_algorithm) on Wikipedia.

#### c. 🌟

{% hint style="success" %}
Illustrates a nice usage of the divide-and-conquer algorithm deisgn method.
{% endhint %}

**Available in the latest revision of the IM.**

### 25-2 Reducing the running time of the Hungarian algorithm to $$O(n^3)$$

**Available in the latest revision of the IM.**

### 25-3 Other matching problems

**Available in the latest revision of the IM.**

### 25-4 Fractional matchings

#### a.

The stated inequality applies to all graphs (not only bipartite), as explained in the article about [fractional matching](https://en.wikipedia.org/wiki/Fractional_matching) on Wikipedia.

#### b.

This is a special case of part (c), where all edge weights are 1.

#### c.

For the same reason as in part (a), we have

$$
∑*{(u, v)∈E} w(u, v) x^\*(u, v) \ge ∑*{(u, v)∈M^\*} w(u, v).
$$

Following the hint from the book, the coresponding [weighted conversion algorithm](https://en.wikipedia.org/wiki/Fractional_matching#Maximum-weight_fractional_matching) (described in the same article as in part (a)) entails

$$
∑*{(u, v)∈E} w(u, v) x^\*(u, v) \le ∑*{(u, v)∈M^\*} w(u, v).
$$

Thus, in a weighted bipartite graph, the maximum value of a weighted fractional matching is equal to the value of a maximum weighted matching.

#### d.

The simplest example is a triangle graph (an odd cycle with 3 vertices: $$v\_1, v\_2, v\_3$$).

* **Maximum Integer Matching**: Because the graph only has three vertices, any two edges will share a vertex. Therefore, you can only select exactly 1 edge without violating the matching constraint. Thus, $$\vert{}M^\*\vert{}=1$$.
* **Maximum Fractional Matching**: You can assign a fractional value of $$0.5$$ to all three edges. For any given vertex, exactly two edges connect to it, so the sum of the incident edges is $$0.5 + 0.5 = 1$$. This perfectly satisfies the fractional matching constraint. The total value of this fractional matching is $$0.5 + 0.5 + 0.5 = 1.5$$.

Because $$1.5 > 1$$, the maximum fractional matching strictly exceeds the maximum integer matching.

### 25-5 Computing vertex labels

To compute the feasible vertex labeling $$h$$, we can construct an auxiliary directed graph and use the Bellman-Ford algorithm to find shortest paths. The conditions (25.6) and (25.7) can be algebraically mapped to the shortest-path properties, as mentioned in the book.

#### Algorithm

1. Given the complete bipartite graph $$G = (L \cup R, E)$$ and the maximum-weight perfect matching $$M^\*$$, construct a new directed graph $$G' = (V', E')$$.
2. Set the vertices to $$V' = L \cup R \cup {s}$$, where $$s$$ is a newly added super-source vertex.
3. Construct the directed edges $$E'$$ and assign their weights $$w'$$ as follows:
   * For every $$l \in L$$, add an edge $$s \to l$$ with $$w'(s, l) = 0$$.
   * For every edge $$(l, r) \in E$$, add a forward edge $$l \to r$$ with weight $$w'(l, r) = -w(l, r)$$.
   * For every edge $$(l, r) \in M^\*$$, add a backward edge $$r \to l$$ with weight $$w'(r, l) = w(l, r)$$.
4. Run the Bellman-Ford algorithm to compute $$d(v) = \delta(s,v)$$ for all $$v \in L \cup R$$.
5. Assign the vertex labels $$h$$ as follows:
   * For each $$l \in L$$, set $$l.h = d(l)$$.
   * For each $$r \in R$$, set $$r.h = -d(r)$$.

#### Proof of Correctness

For Bellman-Ford to produce valid shortest paths $$d(v)$$, the graph $$G'$$ must not contain any negative-weight cycles. Assume, for the sake of contradiction, that $$G'$$ contains a negative-weight cycle $$C$$. Because edges strictly alternate between $$L$$ and $$R$$, the cycle $$C$$ must consist of forward edges (not necessarily in $$M^*$$) and backward edges (strictly in $$M^*$$). The total weight of this cycle is:

$$
\sum\_{(r,l) \in C} w'(r, l) + \sum\_{(l,r) \in C} w'(l, r) < 0.
$$

Substituting our defined weights:

$$
\sum\_{(r,l) \in C} w(l, r) - \sum\_{(l,r) \in C} w(l, r) < 0 \implies \sum\_{\text{backward} \in M^*} w(l, r) < \sum\_{\text{forward} \notin M^*} w(l, r).
$$

If we remove the backward edges of $$C$$ from $$M^*$$ and replace them with the forward edges of $$C$$, we generate a new perfect matching. Because the weight of the forward edges strictly exceeds the backward edges, this new perfect matching has a strictly greater total weight than $$M^*$$. This contradicts the premise that $$M^\*$$ is a maximum-weight perfect matching. Therefore, $$G'$$ contains no negative-weight cycles, and the shortest paths $$d(v)$$ are well-defined.

By the triangle inequality for shortest paths (Lemma 22.10), for any directed edge $$u \to v$$, the shortest path distances satisfy $$d(v) \le d(u) + w'(u, v)$$. Applying this to the forward edges $$l \to r$$ for all $$(l, r) \in E$$:

$$
d(r) \le d(l) + w'(l, r) \implies d(r) \le d(l) - w(l, r).
$$

Substitute the assigned labels:

$$
-r.h \le l.h - w(l, r) \implies l.h + r.h \ge w(l, r) \quad \checkmark
$$

This satisfies condition (25.6) for all edges.

For edges $$(l, r) \in M^\*$$, $$G'$$ includes a backward edge $$r \to l$$ with weight $$w'(r, l) = w(l, r)$$. Applying the triangle inequality to these backward edges:

$$
d(l) \le d(r) + w'(r, l) \implies d(l) \le d(r) + w(l, r).
$$

Substitute the assigned labels:

$$
l.h \le -r.h + w(l, r) \implies l.h + r.h \le w(l, r).
$$

Because condition (25.6) already guarantees $$l.h + r.h \ge w(l, r)$$ for all edges in $$E$$, we have:

$$
((l.h + r.h \ge w(l, r)) ,\land, (l.h + r.h \le w(l, r))) \implies l.h + r.h = w(l, r) \quad \checkmark
$$

This satisfies condition (25.7) for all edges in $$M^\*$$.