Lecture Notes on Matching in Graphs

Author

Your Name

Published

January 30, 2025

Introduction

This lecture introduces the concept of matching in graphs. We define matchings and explore various types, including perfect and weighted matchings. Related concepts such as exposed nodes are discussed. We examine matching in bipartite graphs, including the assignment problem and cardinality matching. We also delve into the applications of matching problems, their polynomial-time complexity, and compare the complexity between bipartite and non-bipartite matching. Finally, we cover linear programming formulations for bipartite matching, optimality conditions using alternating and augmenting paths, and the connection between maximum flow and bipartite matching using the Ford-Fulkerson algorithm.

Matching in Graphs

Definition of a Matching

Given an undirected graph $G = (\mathcal{V}, \mathcal{E})$, a matching $\mathcal{M} \subseteq \mathcal{E}$ is a subset of edges such that no two edges in $\mathcal{M}$ share a common vertex. Formally, for any two distinct edges $(i, j) \in \mathcal{M}$ and $(u, v) \in \mathcal{M}$, the cardinality of the set $\{i, j\} \cup \{u, v\}$ is equal to 4, which implies that $\{i, j\} \cap \{u, v\} = \emptyset$.

Examples of Matchings

Consider an example graph $G = (\mathcal{V}, \mathcal{E})$ with vertices $\mathcal{V} = \{1, 2, 3, 4, 5, 6, 7, 8\}$ and edges as depicted in Figure 1.

Example Graph (G)

Non-Perfect Matching

The set of edges $\mathcal{M}_1 = \{(2, 3), (4, 5), (6, 8)\}$ is a matching in $G$ because no two edges share a vertex.

Perfect Matching

The set of edges $\mathcal{M}_2 = \{(1, 8), (7, 5), (6, 3), (2, 4)\}$ is also a matching in $G$. It is a perfect matching because every vertex in $G$ is incident to exactly one edge in $\mathcal{M}_2$.

Exposed (Unmatched) Nodes

Given a matching $\mathcal{M}$ in a graph $G = (\mathcal{V}, \mathcal{E})$, a vertex $v \in \mathcal{V}$ is called exposed or unmatched if no edge in $\mathcal{M}$ is incident to $v$.

For $\mathcal{M}_1 = \{(2, 3), (4, 5), (6, 8)\}$, the exposed nodes are $\{1, 7\}$. For the perfect matching $\mathcal{M}_2$, there are no exposed nodes.

Necessary Condition for a Perfect Matching

A necessary condition for a graph $G = (\mathcal{V}, \mathcal{E})$ to have a perfect matching is that the number of vertices $|\mathcal{V}|$ is even.

Proof. Proof. In a perfect matching, every vertex is paired with exactly one other vertex. Therefore, the total number of vertices must be divisible by 2. ◻

However, having an even number of vertices is not a sufficient condition for the existence of a perfect matching.

Weighted Matching

In a weighted graph, each edge $e \in \mathcal{E}$ is associated with a cost or weight $c_e$. Let $c: \mathcal{E} \rightarrow \mathbb{R}$ be a cost function.

Cost of a Matching

The cost of a matching $\mathcal{M}$ in a weighted graph $G = (\mathcal{V}, \mathcal{E})$ with edge costs $c_e$ is defined as the sum of the costs of all edges in $\mathcal{M}$: \[c(\mathcal{M}) = \sum_{e \in \mathcal{M}} c_e\]

Assuming example costs for edges in $\mathcal{M}_1$ are $c_{(2,3)}=7, c_{(4,5)}=8, c_{(6,8)}=4$, then $c(\mathcal{M}_1) = 7 + 8 + 4 = 19$. Assuming example costs for edges in $\mathcal{M}_2$ are $c_{(1,8)}=15, c_{(7,5)}=4, c_{(6,3)}=18, c_{(2,4)}=57$, then $c(\mathcal{M}_2) = 15 + 4 + 18 + 57 = 94$.

Maximum Weight Matching Problem

The maximum weight matching problem is to find a matching $\mathcal{M}^*$ in a weighted graph $G = (\mathcal{V}, \mathcal{E})$ such that the cost $c(\mathcal{M}^*)$ is maximized: \[\max_{\mathcal{M} \subseteq \mathcal{E}} \sum_{e \in \mathcal{M}} c_e \quad \text{subject to } \mathcal{M} \text{ being a matching}\]

If all edge costs are non-negative, the minimum weight matching would trivially be the empty matching $\emptyset$, with a cost of 0.

Matching in Bipartite Graphs

A graph $G = (\mathcal{V}, \mathcal{E})$ is bipartite if its vertex set $\mathcal{V}$ can be partitioned into two disjoint sets $V_1$ and $V_2$ such that every edge in $\mathcal{E}$ connects a vertex in $V_1$ to a vertex in $V_2$.

The Assignment Problem

The assignment problem is a specific type of matching problem in bipartite graphs. It can be framed in terms of resources and tasks, where $V_1$ represents resources and $V_2$ represents tasks. An edge between a resource $r \in V_1$ and a task $t \in V_2$ indicates that resource $r$ can perform task $t$.

We may want to maximize the number of tasks performed (maximum cardinality matching) or, if there are weights associated with each edge, find a matching that maximizes the total weight. If $|V_1| = |V_2|$ and we seek a perfect matching of maximum weight, this is also referred to as the assignment problem.

Cardinality Matching

The cardinality matching problem is a special case of the maximum weight matching problem where all edge costs are equal to 1. The objective is to find a matching with the maximum number of edges, i.e., maximum cardinality.

Applications of Matching

Matching problems have numerous applications in various fields.

Resource Allocation

Matching can be used to optimally allocate resources to tasks, such as assigning workers to jobs, machines to processes, or students to projects.

Team Formation

In non-bipartite graphs, matching can model team formation based on compatibility or synergy between individuals.

Polynomial Time Complexity of Matching Problems

Matching problems, both in bipartite and non-bipartite graphs, are solvable in polynomial time.

Complexity Comparison: Bipartite vs. Non-Bipartite Matching

Finding a maximum matching in bipartite graphs is generally computationally easier than in non-bipartite graphs. The complexity of algorithms for bipartite matching is typically lower than for general graphs.

Linear Programming Formulation for Bipartite Matching

Consider a bipartite graph $G = (V_1 \cup V_2, E)$ with edge costs $C_{ij}$ for each edge $(i, j) \in E$.

Variables and Objective Function

For each edge $(i, j) \in E$, we define a binary variable $x_{ij}$: \[x_{ij} = \begin{cases} 1 & \text{if edge } (i, j) \text{ is in the matching} \\ 0 & \text{otherwise} \end{cases}\] The objective is to maximize the total weight of the matching: \[\text{Maximize } \sum_{(i, j) \in E} C_{ij} x_{ij}\]

Constraints

Degree Constraints

For each vertex $i \in V_1 \cup V_2$, the sum of $x_{ij}$ for all edges incident to $i$ must be less than or equal to 1, ensuring that each vertex is matched at most once: \[\sum_{j: (i, j) \in E} x_{ij} \leq 1 \quad \forall i \in V_1 \cup V_2\]

Integrality Constraints

Ideally, we would require $x_{ij} \in \{0, 1\}$. However, for bipartite matching, due to the total unimodularity of the constraint matrix, the solution to the linear program relaxation (where $x_{ij} \geq 0$) is guaranteed to be integer. Thus, we can use the constraints: \[x_{ij} \geq 0 \quad \forall (i, j) \in E\]

Total Unimodularity of the Constraint Matrix

The constraint matrix for the bipartite matching linear program is totally unimodular. This property ensures that if all entries in the constraint matrix and the right-hand side vector are integers, then all basic feasible solutions (and thus optimal solutions) are also integers. This is why we can solve the bipartite matching problem using linear programming and obtain integer solutions without explicitly enforcing integrality constraints.

Assignment Problem as a Linear Program

In the assignment problem, we have a complete bipartite graph between two sets of vertices $V_1 = \{1, 2, \dots, N\}$ and $V_2 = \{1, 2, \dots, N\}$ with costs $C_{ij}$ for assigning vertex $i \in V_1$ to vertex $j \in V_2$. We seek a perfect matching of maximum weight.

Variables and Objective Function

Variables $x_{ij}$ are defined as before: \[x_{ij} = \begin{cases} 1 & \text{if vertex } i \in V_1 \text{ is assigned to vertex } j \in V_2 \\ 0 & \text{otherwise} \end{cases}\] The objective function remains to maximize the total weight: \[\text{Maximize } \sum_{i=1}^{N} \sum_{j=1}^{N} C_{ij} x_{ij}\]

Assignment Constraints

For the assignment problem, we require a perfect matching. This means each vertex in $V_1$ must be matched to exactly one vertex in $V_2$, and vice versa. This leads to the following assignment constraints:

Each vertex $i \in V_1$ is assigned to exactly one vertex in $V_2$: \[\sum_{j=1}^{N} x_{ij} = 1 \quad \forall i = 1, 2, \dots, N\]
Each vertex $j \in V_2$ is assigned to exactly one vertex in $V_1$: \[\sum_{i=1}^{N} x_{ij} = 1 \quad \forall j = 1, 2, \dots, N\]
Non-negativity constraints: \[x_{ij} \geq 0 \quad \forall i, j\]

Again, due to total unimodularity, the optimal solution to this linear program will be integer, and thus binary (0 or 1).

Optimality Conditions for Matching

Alternating Paths

Given a matching $\mathcal{M}$ in a graph $G = (\mathcal{V}, \mathcal{E})$, an alternating path is a path in $G$ that alternately uses edges in $\mathcal{M}$ and edges not in $\mathcal{M}$.

Augmenting Paths

An augmenting path with respect to a matching $\mathcal{M}$ is an alternating path that starts and ends at exposed vertices (with respect to $\mathcal{M}$).

Augmenting Paths and Matching Improvement

If we find an augmenting path $P$ with respect to a matching $\mathcal{M}$, we can increase the size of the matching by "augmenting" along $P$. This is done by taking the symmetric difference of $\mathcal{M}$ and the edges of $P$: $\mathcal{M}' = \mathcal{M} \triangle E(P) = (\mathcal{M} \setminus E(P)) \cup (E(P) \setminus \mathcal{M})$. In simpler terms, edges of $P$ that were in $\mathcal{M}$ are removed, and edges of $P$ that were not in $\mathcal{M}$ are added to form a new matching $\mathcal{M}'$ with $|\mathcal{M}'| = |\mathcal{M}| + 1$.

Theorem: Maximum Matching iff No Augmenting Paths Exist

A matching $\mathcal{M}$ in a graph $G$ is a maximum matching if and only if there is no augmenting path with respect to $\mathcal{M}$.

Proof. Proof.

($\Rightarrow$) If there exists an augmenting path, then as shown above, we can increase the size of the matching, so $\mathcal{M}$ cannot be maximum.
($\Leftarrow$) Suppose $\mathcal{M}$ is not a maximum matching, and let $\mathcal{M}^*$ be a maximum matching. Consider the graph formed by the symmetric difference of $\mathcal{M}$ and $\mathcal{M}^*$, $H = G[\mathcal{M} \triangle \mathcal{M}^*]$. The connected components of $H$ are either even cycles or alternating paths. Since $|\mathcal{M}^*| > |\mathcal{M}|$, there must be more edges from $\mathcal{M}^*$ than from $\mathcal{M}$ in $H$. This implies that there must be at least one path component that starts and ends with edges from $\mathcal{M}^*$. Such a path is an augmenting path with respect to $\mathcal{M}$.

◻

Algorithm for Maximum Cardinality Matching

Based on the theorem, we can devise an algorithm for finding a maximum cardinality matching:

Start with an initial matching $\mathcal{M} = \emptyset$. Update the matching by augmenting along $P$: $\mathcal{M} = \mathcal{M} \triangle E(P)$. The current matching $\mathcal{M}$ is a maximum matching.

The main challenge is to efficiently find augmenting paths.

Maximum Flow and Bipartite Matching

For bipartite graphs, the maximum cardinality matching problem can be reduced to a maximum flow problem.

Transformation to a Flow Network

Given a bipartite graph $G = (V_1 \cup V_2, E)$, construct a flow network $G' = (V', A)$ as follows:

Add a source node $s$ and a sink node $t$.
$V' = V_1 \cup V_2 \cup \{s, t\}$.
For each vertex $u \in V_1$, add a directed edge $(s, u)$ to $A$.
For each vertex $v \in V_2$, add a directed edge $(v, t)$ to $A$.
For each edge $(u, v) \in E$ with $u \in V_1$ and $v \in V_2$, add a directed edge $(u, v)$ to $A$.

Capacity Assignment

Assign capacity 1 to all edges in the flow network $G'$.

Correspondence between Flow and Matching

There is a one-to-one correspondence between matchings in $G$ and integer flows in $G'$. The value of a maximum flow in $G'$ is equal to the cardinality of a maximum matching in $G$. An integer flow of value $f$ corresponds to a matching of cardinality $f$, and vice versa. If there is a flow of value $f$ from $s$ to $t$, then there are $f$ vertex-disjoint paths from $s$ to $t$. The edges in $E$ that are part of these paths form a matching of size $f$.

Ford-Fulkerson Algorithm for Bipartite Matching

We can use the Ford-Fulkerson algorithm to find the maximum flow in the constructed network, which corresponds to finding a maximum matching in the bipartite graph.

Simplified Labeling Algorithm

The lecture describes a simplified labeling algorithm derived from Ford-Fulkerson, tailored for bipartite matching. It starts with an initial matching (possibly empty) and iteratively searches for augmenting paths. The algorithm uses labels to explore paths and augment the matching when an augmenting path is found.

Initialization: Start with an initial matching $\mathcal{M}$ (e.g., $\mathcal{M} = \emptyset$).
Labeling:
1. Label all exposed vertices in $V_1$ with a special label (e.g., *).
2. Iteratively:
  - If there is a labeled vertex $u \in V_1$ and an unlabeled vertex $v \in V_2$ such that $(u, v) \in E$ and $(u, v) \notin \mathcal{M}$, label $v$ with $u$.
  - If there is a labeled vertex $v \in V_2$ and an unlabeled vertex $u \in V_1$ such that $(u, v) \in \mathcal{M}$, label $u$ with $v$.
Augmentation: If an exposed vertex in $V_2$ is labeled, an augmenting path has been found. Trace the path back from the exposed vertex in $V_2$ to an exposed vertex in $V_1$ using the labels. Augment the matching along this path.
Repeat: Repeat steps 2 and 3 until no more augmenting paths can be found.

Example Walkthrough

The lecture provides an example walkthrough of the algorithm on a specific bipartite graph, demonstrating how augmenting paths are found and how the matching is updated. (Refer to the transcription for the detailed example and the graph structure).

Identifying a Minimum Cut

In the context of the maximum flow and minimum cut theorem, a minimum cut in the flow network corresponds to a minimum vertex cover in the bipartite graph (related to König’s theorem). The capacity of the minimum cut is equal to the value of the maximum flow, and thus to the cardinality of the maximum matching. The set of vertices reachable from the source $s$ in the residual graph at the termination of the Ford-Fulkerson algorithm defines one side of the minimum cut.

Conclusion

In this lecture, we have explored the concept of matchings in graphs, focusing on definitions, examples, and properties of matchings, particularly in bipartite graphs. We discussed the maximum weight and maximum cardinality matching problems, their applications, and their polynomial time solvability. We also examined the linear programming formulation for bipartite matching and the optimality condition based on augmenting paths. Finally, we saw how the maximum flow problem and the Ford-Fulkerson algorithm can be used to solve the maximum cardinality matching problem in bipartite graphs. Further study could involve exploring specific algorithms for finding augmenting paths more efficiently, such as the Hopcroft-Karp algorithm for bipartite matching, and algorithms for maximum matching in general (non-bipartite) graphs, like Edmonds’ blossom algorithm.

--- title: "Lecture Notes on Matching in Graphs" author: "Your Name" date: "2025-01-30" format: html: toc: true # Table of Contents toc-depth: 2 code-tools: true theme: cosmo # Or "journal" for Distill-like minimalism --- # Introduction This lecture introduces the concept of matching in graphs. We define matchings and explore various types, including perfect and weighted matchings. Related concepts such as exposed nodes are discussed. We examine matching in bipartite graphs, including the assignment problem and cardinality matching. We also delve into the applications of matching problems, their polynomial-time complexity, and compare the complexity between bipartite and non-bipartite matching. Finally, we cover linear programming formulations for bipartite matching, optimality conditions using alternating and augmenting paths, and the connection between maximum flow and bipartite matching using the Ford-Fulkerson algorithm. # Matching in Graphs ## Definition of a Matching ::: tcolorbox Given an undirected graph $G = (\mathcal{V}, \mathcal{E})$, a **matching** $\mathcal{M} \subseteq \mathcal{E}$ is a subset of edges such that no two edges in $\mathcal{M}$ share a common vertex. Formally, for any two distinct edges $(i, j) \in \mathcal{M}$ and $(u, v) \in \mathcal{M}$, the cardinality of the set $\{i, j\} \cup \{u, v\}$ is equal to 4, which implies that $\{i, j\} \cap \{u, v\} = \emptyset$. ::: ## Examples of Matchings Consider an example graph $G = (\mathcal{V}, \mathcal{E})$ with vertices $\mathcal{V} = \{1, 2, 3, 4, 5, 6, 7, 8\}$ and edges as depicted in Figure [1](#fig:example_graph){reference-type="ref" reference="fig:example_graph"}. <figure id="fig:example_graph"> <figcaption>Example Graph <span class="math inline">$G$</span></figcaption> </figure> ### Non-Perfect Matching The set of edges $\mathcal{M}_1 = \{(2, 3), (4, 5), (6, 8)\}$ is a matching in $G$ because no two edges share a vertex. ### Perfect Matching The set of edges $\mathcal{M}_2 = \{(1, 8), (7, 5), (6, 3), (2, 4)\}$ is also a matching in $G$. It is a **perfect matching** because every vertex in $G$ is incident to exactly one edge in $\mathcal{M}_2$. ## Exposed (Unmatched) Nodes ::: tcolorbox Given a matching $\mathcal{M}$ in a graph $G = (\mathcal{V}, \mathcal{E})$, a vertex $v \in \mathcal{V}$ is called **exposed** or **unmatched** if no edge in $\mathcal{M}$ is incident to $v$. ::: For $\mathcal{M}_1 = \{(2, 3), (4, 5), (6, 8)\}$, the exposed nodes are $\{1, 7\}$. For the perfect matching $\mathcal{M}_2$, there are no exposed nodes. ## Necessary Condition for a Perfect Matching ::: tcolorbox A necessary condition for a graph $G = (\mathcal{V}, \mathcal{E})$ to have a perfect matching is that the number of vertices $|\mathcal{V}|$ is even. ::: ::: proof *Proof.* In a perfect matching, every vertex is paired with exactly one other vertex. Therefore, the total number of vertices must be divisible by 2. ◻ ::: However, having an even number of vertices is not a sufficient condition for the existence of a perfect matching. ## Weighted Matching In a **weighted graph**, each edge $e \in \mathcal{E}$ is associated with a cost or weight $c_e$. Let $c: \mathcal{E} \rightarrow \mathbb{R}$ be a cost function. ### Cost of a Matching ::: tcolorbox The **cost** of a matching $\mathcal{M}$ in a weighted graph $G = (\mathcal{V}, \mathcal{E})$ with edge costs $c_e$ is defined as the sum of the costs of all edges in $\mathcal{M}$: $$c(\mathcal{M}) = \sum_{e \in \mathcal{M}} c_e$$ ::: Assuming example costs for edges in $\mathcal{M}_1$ are $c_{(2,3)}=7, c_{(4,5)}=8, c_{(6,8)}=4$, then $c(\mathcal{M}_1) = 7 + 8 + 4 = 19$. Assuming example costs for edges in $\mathcal{M}_2$ are $c_{(1,8)}=15, c_{(7,5)}=4, c_{(6,3)}=18, c_{(2,4)}=57$, then $c(\mathcal{M}_2) = 15 + 4 + 18 + 57 = 94$. ### Maximum Weight Matching Problem ::: tcolorbox The **maximum weight matching problem** is to find a matching $\mathcal{M}^*$ in a weighted graph $G = (\mathcal{V}, \mathcal{E})$ such that the cost $c(\mathcal{M}^*)$ is maximized: $$\max_{\mathcal{M} \subseteq \mathcal{E}} \sum_{e \in \mathcal{M}} c_e \quad \text{subject to } \mathcal{M} \text{ being a matching}$$ ::: If all edge costs are non-negative, the minimum weight matching would trivially be the empty matching $\emptyset$, with a cost of 0. ## Matching in Bipartite Graphs A graph $G = (\mathcal{V}, \mathcal{E})$ is **bipartite** if its vertex set $\mathcal{V}$ can be partitioned into two disjoint sets $V_1$ and $V_2$ such that every edge in $\mathcal{E}$ connects a vertex in $V_1$ to a vertex in $V_2$. ### The Assignment Problem The **assignment problem** is a specific type of matching problem in bipartite graphs. It can be framed in terms of resources and tasks, where $V_1$ represents resources and $V_2$ represents tasks. An edge between a resource $r \in V_1$ and a task $t \in V_2$ indicates that resource $r$ can perform task $t$. We may want to maximize the number of tasks performed (maximum cardinality matching) or, if there are weights associated with each edge, find a matching that maximizes the total weight. If $|V_1| = |V_2|$ and we seek a perfect matching of maximum weight, this is also referred to as the assignment problem. ## Cardinality Matching ::: tcolorbox The **cardinality matching problem** is a special case of the maximum weight matching problem where all edge costs are equal to 1. The objective is to find a matching with the maximum number of edges, i.e., maximum cardinality. ::: ## Applications of Matching Matching problems have numerous applications in various fields. ### Resource Allocation Matching can be used to optimally allocate resources to tasks, such as assigning workers to jobs, machines to processes, or students to projects. ### Team Formation In non-bipartite graphs, matching can model team formation based on compatibility or synergy between individuals. ## Polynomial Time Complexity of Matching Problems Matching problems, both in bipartite and non-bipartite graphs, are solvable in polynomial time. ## Complexity Comparison: Bipartite vs. Non-Bipartite Matching Finding a maximum matching in bipartite graphs is generally computationally easier than in non-bipartite graphs. The complexity of algorithms for bipartite matching is typically lower than for general graphs. # Linear Programming Formulation for Bipartite Matching Consider a bipartite graph $G = (V_1 \cup V_2, E)$ with edge costs $C_{ij}$ for each edge $(i, j) \in E$. ## Variables and Objective Function For each edge $(i, j) \in E$, we define a binary variable $x_{ij}$: $$x_{ij} = \begin{cases} 1 & \text{if edge } (i, j) \text{ is in the matching} \\ 0 & \text{otherwise} \end{cases}$$ The objective is to maximize the total weight of the matching: $$\text{Maximize } \sum_{(i, j) \in E} C_{ij} x_{ij}$$ ## Constraints ### Degree Constraints For each vertex $i \in V_1 \cup V_2$, the sum of $x_{ij}$ for all edges incident to $i$ must be less than or equal to 1, ensuring that each vertex is matched at most once: $$\sum_{j: (i, j) \in E} x_{ij} \leq 1 \quad \forall i \in V_1 \cup V_2$$ ### Integrality Constraints Ideally, we would require $x_{ij} \in \{0, 1\}$. However, for bipartite matching, due to the total unimodularity of the constraint matrix, the solution to the linear program relaxation (where $x_{ij} \geq 0$) is guaranteed to be integer. Thus, we can use the constraints: $$x_{ij} \geq 0 \quad \forall (i, j) \in E$$ ## Total Unimodularity of the Constraint Matrix The constraint matrix for the bipartite matching linear program is totally unimodular. This property ensures that if all entries in the constraint matrix and the right-hand side vector are integers, then all basic feasible solutions (and thus optimal solutions) are also integers. This is why we can solve the bipartite matching problem using linear programming and obtain integer solutions without explicitly enforcing integrality constraints. ## Assignment Problem as a Linear Program In the assignment problem, we have a complete bipartite graph between two sets of vertices $V_1 = \{1, 2, \dots, N\}$ and $V_2 = \{1, 2, \dots, N\}$ with costs $C_{ij}$ for assigning vertex $i \in V_1$ to vertex $j \in V_2$. We seek a perfect matching of maximum weight. ### Variables and Objective Function Variables $x_{ij}$ are defined as before: $$x_{ij} = \begin{cases} 1 & \text{if vertex } i \in V_1 \text{ is assigned to vertex } j \in V_2 \\ 0 & \text{otherwise} \end{cases}$$ The objective function remains to maximize the total weight: $$\text{Maximize } \sum_{i=1}^{N} \sum_{j=1}^{N} C_{ij} x_{ij}$$ ### Assignment Constraints For the assignment problem, we require a perfect matching. This means each vertex in $V_1$ must be matched to exactly one vertex in $V_2$, and vice versa. This leads to the following assignment constraints: - Each vertex $i \in V_1$ is assigned to exactly one vertex in $V_2$: $$\sum_{j=1}^{N} x_{ij} = 1 \quad \forall i = 1, 2, \dots, N$$ - Each vertex $j \in V_2$ is assigned to exactly one vertex in $V_1$: $$\sum_{i=1}^{N} x_{ij} = 1 \quad \forall j = 1, 2, \dots, N$$ - Non-negativity constraints: $$x_{ij} \geq 0 \quad \forall i, j$$ Again, due to total unimodularity, the optimal solution to this linear program will be integer, and thus binary (0 or 1). # Optimality Conditions for Matching ## Alternating Paths ::: tcolorbox Given a matching $\mathcal{M}$ in a graph $G = (\mathcal{V}, \mathcal{E})$, an **alternating path** is a path in $G$ that alternately uses edges in $\mathcal{M}$ and edges not in $\mathcal{M}$. ::: ## Augmenting Paths ::: tcolorbox An **augmenting path** with respect to a matching $\mathcal{M}$ is an alternating path that starts and ends at exposed vertices (with respect to $\mathcal{M}$). ::: ## Augmenting Paths and Matching Improvement If we find an augmenting path $P$ with respect to a matching $\mathcal{M}$, we can increase the size of the matching by \"augmenting\" along $P$. This is done by taking the symmetric difference of $\mathcal{M}$ and the edges of $P$: $\mathcal{M}' = \mathcal{M} \triangle E(P) = (\mathcal{M} \setminus E(P)) \cup (E(P) \setminus \mathcal{M})$. In simpler terms, edges of $P$ that were in $\mathcal{M}$ are removed, and edges of $P$ that were not in $\mathcal{M}$ are added to form a new matching $\mathcal{M}'$ with $|\mathcal{M}'| = |\mathcal{M}| + 1$. ## Theorem: Maximum Matching iff No Augmenting Paths Exist ::: tcolorbox A matching $\mathcal{M}$ in a graph $G$ is a maximum matching if and only if there is no augmenting path with respect to $\mathcal{M}$. ::: ::: proof *Proof.* - ($\Rightarrow$) If there exists an augmenting path, then as shown above, we can increase the size of the matching, so $\mathcal{M}$ cannot be maximum. - ($\Leftarrow$) Suppose $\mathcal{M}$ is not a maximum matching, and let $\mathcal{M}^*$ be a maximum matching. Consider the graph formed by the symmetric difference of $\mathcal{M}$ and $\mathcal{M}^*$, $H = G[\mathcal{M} \triangle \mathcal{M}^*]$. The connected components of $H$ are either even cycles or alternating paths. Since $|\mathcal{M}^*| > |\mathcal{M}|$, there must be more edges from $\mathcal{M}^*$ than from $\mathcal{M}$ in $H$. This implies that there must be at least one path component that starts and ends with edges from $\mathcal{M}^*$. Such a path is an augmenting path with respect to $\mathcal{M}$. ◻ ::: ## Algorithm for Maximum Cardinality Matching Based on the theorem, we can devise an algorithm for finding a maximum cardinality matching: :::: tcolorbox ::: algorithmic Start with an initial matching $\mathcal{M} = \emptyset$. Update the matching by augmenting along $P$: $\mathcal{M} = \mathcal{M} \triangle E(P)$. The current matching $\mathcal{M}$ is a maximum matching. ::: :::: The main challenge is to efficiently find augmenting paths. # Maximum Flow and Bipartite Matching For bipartite graphs, the maximum cardinality matching problem can be reduced to a maximum flow problem. ## Transformation to a Flow Network Given a bipartite graph $G = (V_1 \cup V_2, E)$, construct a flow network $G' = (V', A)$ as follows: - Add a source node $s$ and a sink node $t$. - $V' = V_1 \cup V_2 \cup \{s, t\}$. - For each vertex $u \in V_1$, add a directed edge $(s, u)$ to $A$. - For each vertex $v \in V_2$, add a directed edge $(v, t)$ to $A$. - For each edge $(u, v) \in E$ with $u \in V_1$ and $v \in V_2$, add a directed edge $(u, v)$ to $A$. ## Capacity Assignment Assign capacity 1 to all edges in the flow network $G'$. ## Correspondence between Flow and Matching There is a one-to-one correspondence between matchings in $G$ and integer flows in $G'$. The value of a maximum flow in $G'$ is equal to the cardinality of a maximum matching in $G$. An integer flow of value $f$ corresponds to a matching of cardinality $f$, and vice versa. If there is a flow of value $f$ from $s$ to $t$, then there are $f$ vertex-disjoint paths from $s$ to $t$. The edges in $E$ that are part of these paths form a matching of size $f$. ## Ford-Fulkerson Algorithm for Bipartite Matching We can use the Ford-Fulkerson algorithm to find the maximum flow in the constructed network, which corresponds to finding a maximum matching in the bipartite graph. ### Simplified Labeling Algorithm The lecture describes a simplified labeling algorithm derived from Ford-Fulkerson, tailored for bipartite matching. It starts with an initial matching (possibly empty) and iteratively searches for augmenting paths. The algorithm uses labels to explore paths and augment the matching when an augmenting path is found. ::: tcolorbox 1. **Initialization:** Start with an initial matching $\mathcal{M}$ (e.g., $\mathcal{M} = \emptyset$). 2. **Labeling:** 1. Label all exposed vertices in $V_1$ with a special label (e.g., \*). 2. **Iteratively:** - If there is a labeled vertex $u \in V_1$ and an unlabeled vertex $v \in V_2$ such that $(u, v) \in E$ and $(u, v) \notin \mathcal{M}$, label $v$ with $u$. - If there is a labeled vertex $v \in V_2$ and an unlabeled vertex $u \in V_1$ such that $(u, v) \in \mathcal{M}$, label $u$ with $v$. 3. **Augmentation:** If an exposed vertex in $V_2$ is labeled, an augmenting path has been found. Trace the path back from the exposed vertex in $V_2$ to an exposed vertex in $V_1$ using the labels. Augment the matching along this path. 4. **Repeat:** Repeat steps 2 and 3 until no more augmenting paths can be found. ::: ### Example Walkthrough The lecture provides an example walkthrough of the algorithm on a specific bipartite graph, demonstrating how augmenting paths are found and how the matching is updated. (Refer to the transcription for the detailed example and the graph structure). ### Identifying a Minimum Cut In the context of the maximum flow and minimum cut theorem, a minimum cut in the flow network corresponds to a minimum vertex cover in the bipartite graph (related to König's theorem). The capacity of the minimum cut is equal to the value of the maximum flow, and thus to the cardinality of the maximum matching. The set of vertices reachable from the source $s$ in the residual graph at the termination of the Ford-Fulkerson algorithm defines one side of the minimum cut. # Conclusion In this lecture, we have explored the concept of matchings in graphs, focusing on definitions, examples, and properties of matchings, particularly in bipartite graphs. We discussed the maximum weight and maximum cardinality matching problems, their applications, and their polynomial time solvability. We also examined the linear programming formulation for bipartite matching and the optimality condition based on augmenting paths. Finally, we saw how the maximum flow problem and the Ford-Fulkerson algorithm can be used to solve the maximum cardinality matching problem in bipartite graphs. Further study could involve exploring specific algorithms for finding augmenting paths more efficiently, such as the Hopcroft-Karp algorithm for bipartite matching, and algorithms for maximum matching in general (non-bipartite) graphs, like Edmonds' blossom algorithm.