Lecture Notes: Maximum Bipartite Matching and Constraint Propagation

Author

Your Name

Published

February 5, 2025

Introduction

This lecture introduces the concept of maximum bipartite matching and its application to constraint propagation, focusing on the all different constraint. We will formalize the idea of augmenting paths in bipartite graphs, leading to a polynomial-time algorithm for finding maximum matchings. Key concepts include:

Berge’s Theorem: This theorem provides a necessary and sufficient condition for a matching to be a maximum matching.
Reging’s Theorem: This theorem connects maximum matchings to hyper arc consistency in constraint satisfaction problems, specifically for the all different constraint.

These concepts form the basis for efficient constraint propagation techniques in constraint satisfaction problems.

Augmenting Paths and Maximum Matching

A matching $M$ in a bipartite graph $G=(X \cup Y, E)$ is a subset of edges $M \subseteq E$ such that no two edges in $M$ share a common vertex.

A vertex is considered free with respect to a matching $M$ if it is not incident to any edge in $M$.

An augmenting path $P$ for a matching $M$ is a path in $G$ that:

Starts at a free vertex (with respect to $M$).
Alternates between edges not in $M$ and edges in $M$.
Ends at another free vertex (with respect to $M$).

Let $P$ be an augmenting path for a matching $M$. We can augment $M$ by taking the symmetric difference: \[\label{eq:augment_matching}M' = (M \setminus P) \cup (P \setminus M)\] This operation increases the size of the matching by one.

Lemma 1. If $P$ is an augmenting path for a matching $M$, then $M' = (M \setminus P) \cup (P \setminus M)$ is a matching, and $|M'| = |M| + 1$.

Proof. Proof. Let $M$ be a matching and $P$ be an augmenting path. Let $P$ be represented as $Y_0, X_1, Y_1, X_2, \dots, Y_k, X_0$, where $Y_0$ and $X_0$ are free vertices. The edges $(Y_i, X_{i+1})$ are not in $M$, and the edges $(X_i, Y_i)$ are in $M$. $M'$ is formed by removing the edges of $P$ that are in $M$ and adding the edges of $P$ that are not in $M$. Since $P$ is an augmenting path, the vertices $Y_0, X_1, Y_1, \dots, Y_k, X_0$ are distinct. Also, $Y_0$ and $X_0$ are free, so they are not incident to any edge in $M$. Thus, $M'$ is a matching. The size of $M'$ is $|M| + 1$ because we remove $k$ edges from $M$ and add $k+1$ edges. ◻

A maximum matching is a matching $M$ such that there is no matching $M'$ with $|M'| > |M|$. The size of a maximum matching in a bipartite graph $G=(X \cup Y, E)$ is at most $\min(|X|, |Y|)$.

Theorem 2 (Berge, 1957). A matching $M$ in a bipartite graph $G$ is a maximum matching if and only if there is no augmenting path for $M$.

Proof. Proof. $(\Rightarrow)$ Suppose $M$ is a maximum matching. If there were an augmenting path $P$ for $M$, then we could form a larger matching $M' = (M \setminus P) \cup (P \setminus M)$, contradicting the maximality of $M$.

$(\Leftarrow)$ We will prove the contrapositive. Suppose $M$ is not a maximum matching. Then there exists a matching $M'$ with $|M'| > |M|$. Consider the graph $H = (X \cup Y, M \oplus M')$, where $\oplus$ denotes the symmetric difference. In $H$, each vertex has a degree of at most 2. Thus, $H$ consists of disjoint paths and cycles. Since $|M'| > |M|$, there must be at least one path in $H$ where the number of edges from $M'$ exceeds the number of edges from $M$. This path is an augmenting path for $M$. ◻

The core idea is that if a matching is not maximal, we can always find an augmenting path that allows us to increase the size of the matching. Berge’s theorem formalizes this concept, providing a powerful tool for understanding and finding maximum matchings.

Naive Algorithm for Maximum Matching

$M \gets \emptyset$ $M \gets (M \setminus P) \cup (P \setminus M)$ $M$

The core of this algorithm is the repeated search for augmenting paths. An augmenting path can be found in $O(|E|)$ time using a modified Breadth-First Search (BFS) or Depth-First Search (DFS). The algorithm terminates when no more augmenting paths can be found, which occurs after at most $\min(|X|, |Y|)$ iterations.

Theorem 3. The naive algorithm finds a maximum matching in $O(\min(|X|, |Y|) \cdot |E|)$ time.

Proof. Proof. Each iteration of the while loop requires finding an augmenting path, which takes $O(|E|)$ time. The loop iterates at most $\min(|X|, |Y|)$ times, as each iteration increases the size of the matching by one, and the maximum size of a matching is bounded by $\min(|X|, |Y|)$. Therefore, the overall time complexity is $O(\min(|X|, |Y|) \cdot |E|)$. ◻

While this naive algorithm is correct, its time complexity can be a bottleneck for large graphs. The Hopcroft-Karp algorithm improves this to $O(\sqrt{|V|} \cdot |E|)$, where $|V| = |X| + |Y|$ is the total number of vertices in the graph.

The naive algorithm’s complexity is $O(\min(|X|, |Y|) \cdot |E|)$, which can be inefficient for large graphs. The Hopcroft-Karp algorithm offers a significant improvement with a complexity of $O(\sqrt{|V|} \cdot |E|)$.

Application to All Different Constraint

The all different constraint on a set of variables $X_1, \dots, X_k$ with corresponding domains $D_1, \dots, D_k$ specifies that the values assigned to the variables must be pairwise distinct. That is, if $X_i = v_i$ for $i=1,\dots,k$, then $v_i \neq v_j$ for all $i \neq j$.

We can represent the all different constraint as a bipartite graph $G = (X \cup D, E)$, where:

$X = \{X_1, \dots, X_k\}$ is the set of variables.
$D = \bigcup_{i=1}^k D_i$ is the union of all domains.
$E = \{(X_i, v) \mid v \in D_i \}$ is the set of edges connecting each variable to the values in its domain.

An edge $(X_i, v)$ exists if the value $v$ is in the domain of variable $X_i$.

A constraint is hyper arc consistent if for every variable $X_i$ and every value $v \in D_i$, there exists a solution to the constraint where $X_i$ is assigned the value $v$. In other words, every value in the domain of every variable must be part of at least one valid solution.

Theorem 4 (Reging, 1994). An all different constraint is hyper arc consistent if and only if every edge in the corresponding bipartite graph belongs to a matching of size $k$, where $k$ is the number of variables.

Proof. Proof. The proof involves two directions:

$(\Rightarrow)$ If the all different constraint is hyper arc consistent, then for every edge $(X_i, v)$, there exists a solution where $X_i = v$. This solution corresponds to a matching of size $k$ in the bipartite graph, which includes the edge $(X_i, v)$.
$(\Leftarrow)$ If every edge belongs to a matching of size $k$, then for any variable $X_i$ and any value $v \in D_i$, there exists a matching of size $k$ that includes the edge $(X_i, v)$. This matching corresponds to a solution to the all different constraint where $X_i = v$. Therefore, the constraint is hyper arc consistent.

◻

Reging’s theorem establishes a crucial link between maximum matchings and hyper arc consistency for the all different constraint. It implies that to achieve hyper arc consistency, we need to ensure that every possible assignment (edge) is part of at least one valid solution (maximum matching of size $k$).

Filtering Algorithm Based on Maximum Matching

Theorem 5 (Reging, 1994). An edge $e$ belongs to some but not all maximum matchings if and only if, for an arbitrary maximum matching $M$, $e$ belongs to:

An even length alternating path starting at a free vertex (with respect to $M$), or
An even length alternating cycle.

Proof. Proof. $(\Rightarrow)$ Suppose $e$ belongs to some but not all maximum matchings. Let $M$ be a maximum matching containing $e$, and $M'$ be a maximum matching not containing $e$. Consider the graph $H = (X \cup Y, M \oplus M')$, where $\oplus$ denotes the symmetric difference. The edge $e$ is in this symmetric difference. Since the degrees of vertices in $H$ are at most 2, $e$ must be part of a path or a cycle.

If $e$ is part of a cycle, this cycle must be even and alternating (edges alternate between $M$ and $M'$).
If $e$ is part of a path, this path must be even and start/end at a free vertex. If the path was odd, it would be an augmenting path for either $M$ or $M'$, contradicting their maximality.

$(\Leftarrow)$ If $e$ is in an even length alternating cycle or an even length alternating path starting at a free vertex in some maximum matching $M$, we can obtain another maximum matching $M'$ by swapping edges along the path or cycle. This new matching $M'$ will not contain $e$ if $e$ was in $M$, or will contain $e$ if $e$ was not in $M$. ◻

This theorem provides the basis for an efficient filtering algorithm. The algorithm involves the following steps:

Find an arbitrary maximum matching $M$ in the bipartite graph.
For each edge $e$ in the graph:
1. Check if $e$ is part of $M$. If yes, keep the edge.
2. If $e$ is not in $M$, check if $e$ belongs to an even length alternating path starting at a free vertex or an even length alternating cycle with respect to $M$. If yes, keep the edge.
3. If neither of the above conditions are met, remove the edge from the graph (and thus the corresponding value from the domain of the variable).

The filtering algorithm leverages the properties of alternating paths and cycles to efficiently identify and remove edges that cannot be part of any solution, thus enforcing hyper arc consistency.

Conclusion

In this lecture, we have explored the concept of maximum bipartite matching and its crucial connection to constraint propagation, particularly for the all different constraint. We have seen how:

Augmenting paths can be used to iteratively increase the size of a matching.
Berge’s theorem provides a necessary and sufficient condition for a matching to be maximum, stating that a matching is maximum if and only if there are no augmenting paths.
Reging’s theorem allows us to efficiently filter the domains of variables in an all different constraint by leveraging the properties of maximum matchings. Specifically, it states that an all different constraint is hyper arc consistent if and only if every edge in the corresponding bipartite graph belongs to a matching of size $k$, where $k$ is the number of variables.
Reging’s filtering theorem provides a way to identify edges that belong to some but not all maximum matchings. An edge belongs to some but not all maximum matchings if and only if it is part of an even alternating path starting at a free vertex or an even alternating cycle.

The filtering algorithm, based on these theorems, has a polynomial time complexity, making it a practical and efficient method for enforcing hyper arc consistency in constraint satisfaction problems.

Augmenting paths are fundamental for finding maximum matchings.
Berge’s theorem provides a theoretical foundation for maximum matching algorithms.
Reging’s theorems connect maximum matching to hyper arc consistency and provide a basis for efficient filtering.
The filtering algorithm based on maximum matching is a polynomial-time method for enforcing hyper arc consistency for the all different constraint.

Follow-up Questions:

How can the Hopcroft-Karp algorithm be used to improve the efficiency of finding a maximum matching?
What are some other global constraints where similar techniques based on graph theory can be applied?
How can the data structures used in the filtering algorithm be optimized for backtracking in constraint solvers?
Explore the implementation details of the circuit and cumulative global constraints mentioned in the lecture.

--- title: "Lecture Notes: Maximum Bipartite Matching and Constraint Propagation" author: "Your Name" date: "2025-02-05" format: html: toc: true # Table of Contents toc-depth: 2 code-tools: true theme: cosmo # Or "journal" for Distill-like minimalism --- # Introduction {#sec:introduction} This lecture introduces the concept of maximum bipartite matching and its application to constraint propagation, focusing on the *all different* constraint. We will formalize the idea of augmenting paths in bipartite graphs, leading to a polynomial-time algorithm for finding maximum matchings. Key concepts include: - **Berge's Theorem**: This theorem provides a necessary and sufficient condition for a matching to be a maximum matching. - **Reging's Theorem**: This theorem connects maximum matchings to hyper arc consistency in constraint satisfaction problems, specifically for the *all different* constraint. These concepts form the basis for efficient constraint propagation techniques in constraint satisfaction problems. # Augmenting Paths and Maximum Matching {#sec:augmenting_paths} :::: tcolorbox ::: definition []{#def:matching label="def:matching"} A *matching* $M$ in a bipartite graph $G=(X \cup Y, E)$ is a subset of edges $M \subseteq E$ such that no two edges in $M$ share a common vertex. ::: :::: :::: tcolorbox ::: definition []{#def:free_vertex label="def:free_vertex"} A vertex is considered *free* with respect to a matching $M$ if it is not incident to any edge in $M$. ::: :::: :::: tcolorbox ::: definition []{#def:augmenting_path label="def:augmenting_path"} An *augmenting path* $P$ for a matching $M$ is a path in $G$ that: 1. Starts at a free vertex (with respect to $M$). 2. Alternates between edges not in $M$ and edges in $M$. 3. Ends at another free vertex (with respect to $M$). ::: :::: Let $P$ be an augmenting path for a matching $M$. We can augment $M$ by taking the symmetric difference: $$\label{eq:augment_matching}M' = (M \setminus P) \cup (P \setminus M)$$ This operation increases the size of the matching by one. ::: {.lemma:augmenting_path_increases_matching .lemma} **Lemma 1**. *If $P$ is an augmenting path for a matching $M$, then $M' = (M \setminus P) \cup (P \setminus M)$ is a matching, and $|M'| = |M| + 1$.* ::: ::: proof *Proof.* Let $M$ be a matching and $P$ be an augmenting path. Let $P$ be represented as $Y_0, X_1, Y_1, X_2, \dots, Y_k, X_0$, where $Y_0$ and $X_0$ are free vertices. The edges $(Y_i, X_{i+1})$ are not in $M$, and the edges $(X_i, Y_i)$ are in $M$. $M'$ is formed by removing the edges of $P$ that are in $M$ and adding the edges of $P$ that are not in $M$. Since $P$ is an augmenting path, the vertices $Y_0, X_1, Y_1, \dots, Y_k, X_0$ are distinct. Also, $Y_0$ and $X_0$ are free, so they are not incident to any edge in $M$. Thus, $M'$ is a matching. The size of $M'$ is $|M| + 1$ because we remove $k$ edges from $M$ and add $k+1$ edges. ◻ ::: :::: tcolorbox ::: definition []{#def:maximum_matching label="def:maximum_matching"} A *maximum matching* is a matching $M$ such that there is no matching $M'$ with $|M'| > |M|$. The size of a maximum matching in a bipartite graph $G=(X \cup Y, E)$ is at most $\min(|X|, |Y|)$. ::: :::: :::: tcolorbox ::: {.thm:berge .theorem} **Theorem 2** (Berge, 1957). *A matching $M$ in a bipartite graph $G$ is a maximum matching if and only if there is no augmenting path for $M$.* ::: :::: ::: proof *Proof.* $(\Rightarrow)$ Suppose $M$ is a maximum matching. If there were an augmenting path $P$ for $M$, then we could form a larger matching $M' = (M \setminus P) \cup (P \setminus M)$, contradicting the maximality of $M$. $(\Leftarrow)$ We will prove the contrapositive. Suppose $M$ is not a maximum matching. Then there exists a matching $M'$ with $|M'| > |M|$. Consider the graph $H = (X \cup Y, M \oplus M')$, where $\oplus$ denotes the symmetric difference. In $H$, each vertex has a degree of at most 2. Thus, $H$ consists of disjoint paths and cycles. Since $|M'| > |M|$, there must be at least one path in $H$ where the number of edges from $M'$ exceeds the number of edges from $M$. This path is an augmenting path for $M$. ◻ ::: ::: tcolorbox The core idea is that if a matching is not maximal, we can always find an augmenting path that allows us to increase the size of the matching. Berge's theorem formalizes this concept, providing a powerful tool for understanding and finding maximum matchings. ::: # Naive Algorithm for Maximum Matching {#sec:naive_algorithm} :::: algorithm ::: algorithmic $M \gets \emptyset$ $M \gets (M \setminus P) \cup (P \setminus M)$ $M$ ::: :::: The core of this algorithm is the repeated search for augmenting paths. An augmenting path can be found in $O(|E|)$ time using a modified Breadth-First Search (BFS) or Depth-First Search (DFS). The algorithm terminates when no more augmenting paths can be found, which occurs after at most $\min(|X|, |Y|)$ iterations. :::: tcolorbox ::: {.thm:naive_complexity .theorem} **Theorem 3**. *The naive algorithm finds a maximum matching in $O(\min(|X|, |Y|) \cdot |E|)$ time.* ::: :::: ::: proof *Proof.* Each iteration of the **while** loop requires finding an augmenting path, which takes $O(|E|)$ time. The loop iterates at most $\min(|X|, |Y|)$ times, as each iteration increases the size of the matching by one, and the maximum size of a matching is bounded by $\min(|X|, |Y|)$. Therefore, the overall time complexity is $O(\min(|X|, |Y|) \cdot |E|)$. ◻ ::: While this naive algorithm is correct, its time complexity can be a bottleneck for large graphs. The Hopcroft-Karp algorithm improves this to $O(\sqrt{|V|} \cdot |E|)$, where $|V| = |X| + |Y|$ is the total number of vertices in the graph. ::: tcolorbox The naive algorithm's complexity is $O(\min(|X|, |Y|) \cdot |E|)$, which can be inefficient for large graphs. The Hopcroft-Karp algorithm offers a significant improvement with a complexity of $O(\sqrt{|V|} \cdot |E|)$. ::: # Application to All Different Constraint {#sec:all_different_constraint} :::: tcolorbox ::: definition []{#def:all_different label="def:all_different"} The *all different* constraint on a set of variables $X_1, \dots, X_k$ with corresponding domains $D_1, \dots, D_k$ specifies that the values assigned to the variables must be pairwise distinct. That is, if $X_i = v_i$ for $i=1,\dots,k$, then $v_i \neq v_j$ for all $i \neq j$. ::: :::: We can represent the all different constraint as a bipartite graph $G = (X \cup D, E)$, where: - $X = \{X_1, \dots, X_k\}$ is the set of variables. - $D = \bigcup_{i=1}^k D_i$ is the union of all domains. - $E = \{(X_i, v) \mid v \in D_i \}$ is the set of edges connecting each variable to the values in its domain. An edge $(X_i, v)$ exists if the value $v$ is in the domain of variable $X_i$. :::: tcolorbox ::: definition []{#def:hyper_arc_consistency label="def:hyper_arc_consistency"} A constraint is *hyper arc consistent* if for every variable $X_i$ and every value $v \in D_i$, there exists a solution to the constraint where $X_i$ is assigned the value $v$. In other words, every value in the domain of every variable must be part of at least one valid solution. ::: :::: :::: tcolorbox ::: {.thm:regin_hyper_arc_consistency .theorem} **Theorem 4** (Reging, 1994). *An all different constraint is hyper arc consistent if and only if every edge in the corresponding bipartite graph belongs to a matching of size $k$, where $k$ is the number of variables.* ::: :::: ::: proof *Proof.* The proof involves two directions: - $(\Rightarrow)$ If the all different constraint is hyper arc consistent, then for every edge $(X_i, v)$, there exists a solution where $X_i = v$. This solution corresponds to a matching of size $k$ in the bipartite graph, which includes the edge $(X_i, v)$. - $(\Leftarrow)$ If every edge belongs to a matching of size $k$, then for any variable $X_i$ and any value $v \in D_i$, there exists a matching of size $k$ that includes the edge $(X_i, v)$. This matching corresponds to a solution to the all different constraint where $X_i = v$. Therefore, the constraint is hyper arc consistent. ◻ ::: ::: tcolorbox Reging's theorem establishes a crucial link between maximum matchings and hyper arc consistency for the all different constraint. It implies that to achieve hyper arc consistency, we need to ensure that every possible assignment (edge) is part of at least one valid solution (maximum matching of size $k$). ::: # Filtering Algorithm Based on Maximum Matching {#sec:filtering_algorithm} :::: tcolorbox ::: {.thm:regin_filtering .theorem} **Theorem 5** (Reging, 1994). *An edge $e$ belongs to **some but not all** maximum matchings if and only if, for an arbitrary maximum matching $M$, $e$ belongs to:* 1. *An even length alternating path starting at a free vertex (with respect to $M$), or* 2. *An even length alternating cycle.* ::: :::: ::: proof *Proof.* $(\Rightarrow)$ Suppose $e$ belongs to some but not all maximum matchings. Let $M$ be a maximum matching containing $e$, and $M'$ be a maximum matching not containing $e$. Consider the graph $H = (X \cup Y, M \oplus M')$, where $\oplus$ denotes the symmetric difference. The edge $e$ is in this symmetric difference. Since the degrees of vertices in $H$ are at most 2, $e$ must be part of a path or a cycle. - If $e$ is part of a cycle, this cycle must be even and alternating (edges alternate between $M$ and $M'$). - If $e$ is part of a path, this path must be even and start/end at a free vertex. If the path was odd, it would be an augmenting path for either $M$ or $M'$, contradicting their maximality. $(\Leftarrow)$ If $e$ is in an even length alternating cycle or an even length alternating path starting at a free vertex in some maximum matching $M$, we can obtain another maximum matching $M'$ by swapping edges along the path or cycle. This new matching $M'$ will not contain $e$ if $e$ was in $M$, or will contain $e$ if $e$ was not in $M$. ◻ ::: This theorem provides the basis for an efficient filtering algorithm. The algorithm involves the following steps: 1. Find an arbitrary maximum matching $M$ in the bipartite graph. 2. For each edge $e$ in the graph: 1. Check if $e$ is part of $M$. If yes, keep the edge. 2. If $e$ is not in $M$, check if $e$ belongs to an even length alternating path starting at a free vertex or an even length alternating cycle with respect to $M$. If yes, keep the edge. 3. If neither of the above conditions are met, remove the edge from the graph (and thus the corresponding value from the domain of the variable). ::: tcolorbox The filtering algorithm leverages the properties of alternating paths and cycles to efficiently identify and remove edges that cannot be part of any solution, thus enforcing hyper arc consistency. ::: # Conclusion {#sec:conclusion} In this lecture, we have explored the concept of maximum bipartite matching and its crucial connection to constraint propagation, particularly for the *all different* constraint. We have seen how: - **Augmenting paths** can be used to iteratively increase the size of a matching. - **Berge's theorem** provides a necessary and sufficient condition for a matching to be maximum, stating that a matching is maximum if and only if there are no augmenting paths. - **Reging's theorem** allows us to efficiently filter the domains of variables in an *all different* constraint by leveraging the properties of maximum matchings. Specifically, it states that an *all different* constraint is hyper arc consistent if and only if every edge in the corresponding bipartite graph belongs to a matching of size $k$, where $k$ is the number of variables. - **Reging's filtering theorem** provides a way to identify edges that belong to some but not all maximum matchings. An edge belongs to some but not all maximum matchings if and only if it is part of an even alternating path starting at a free vertex or an even alternating cycle. The filtering algorithm, based on these theorems, has a polynomial time complexity, making it a practical and efficient method for enforcing hyper arc consistency in constraint satisfaction problems. ::: tcolorbox - Augmenting paths are fundamental for finding maximum matchings. - Berge's theorem provides a theoretical foundation for maximum matching algorithms. - Reging's theorems connect maximum matching to hyper arc consistency and provide a basis for efficient filtering. - The filtering algorithm based on maximum matching is a polynomial-time method for enforcing hyper arc consistency for the *all different* constraint. ::: **Follow-up Questions:** - How can the Hopcroft-Karp algorithm be used to improve the efficiency of finding a maximum matching? - What are some other global constraints where similar techniques based on graph theory can be applied? - How can the data structures used in the filtering algorithm be optimized for backtracking in constraint solvers? - Explore the implementation details of the `circuit` and `cumulative` global constraints mentioned in the lecture.