06 Matchings, Colorings

In this section, we shift our focus to matchings, a concept of paramount importance in graph theory and combinatorial optimization. Matchings deal with pairing vertices through edges, subject to certain constraints. They have wide-ranging applications, from assignment problems to network flow and beyond.

Matchings (1.6)

Consider a scenario where we have two sets of entities, say, jobs and machines. Each job requires a specific machine to be processed, and each machine can only process one job at a time. The question is, can we find a feasible assignment of jobs to machines such that all jobs are processed simultaneously? This problem can be elegantly modeled using matchings in graphs.

In graph-theoretic terms, a matching $M$ in a graph $G = (V, E)$ is a set of edges such that no two edges in $M$ share a common vertex. In other words, each vertex is incident to at most one edge in the matching. Formally, a set of edges $M \subseteq E$ is a matching if for any two distinct edges $e, f \in M$ , $e \cap f = \emptyset$ .

A vertex $v$ is said to be matched or covered by $M$ if there is an edge in $M$ incident to $v$ . A matching $M$ is called a perfect matching if every vertex in $V$ is matched by $M$ . This implies that in a perfect matching, every vertex is incident to exactly one edge in $M$ . Perfect matchings can only exist in graphs with an even number of vertices.

Definition 1.44: A matching in a graph $G = (V, E)$ is a set of edges $M \subseteq E$ such that no two edges in $M$ share a common vertex. Formally, for all $e, f \in M$ with $e \neq = f$ , $e \cap f = \emptyset$ .

A matching $M$ is called a perfect matching if every vertex $v \in V$ is incident to some edge in $M$ . Equivalently, $∣ M ∣ = ∣ V ∣/2$ .

Types of Matchings: Maximal vs. Maximum

When seeking to find a “large” matching in a graph, we encounter two distinct notions of maximality:

Inclusion-Maximal Matching: A matching $M$ is inclusion-maximal (or simply maximal matching) if no more edges can be added to $M$ without violating the matching property. In other words, for any edge $e \in E ∖ M$ , $M \cup {e}$ is not a matching.
Cardinality-Maximal Matching: A matching $M$ is cardinality-maximal (or simply maximum matching) if it has the largest possible number of edges among all matchings in $G$ . That is, for any other matching $M^{'}$ in $G$ , $∣ M ∣ \geq ∣ M^{'} ∣$ .

Every maximum matching is also inclusion-maximal, but the converse is not necessarily true. An inclusion-maximal matching is “locally” maximal in the sense that we cannot add any single edge to it. However, it may not be “globally” maximal; there might exist other matchings with more edges. Maximum matchings, on the other hand, are globally optimal in terms of the number of matched edges. Finding a maximum matching is generally more challenging than finding an inclusion-maximal matching.

Algorithms for Matchings (1.6.1)

Greedy Matching Algorithm

Finding an inclusion-maximal matching is straightforward using a greedy approach. The Greedy Matching Algorithm iteratively selects edges and adds them to the matching, ensuring that no two selected edges share a vertex.

Algorithm: Greedy Matching Algorithm

Algorithm: Greedy-Matching(G)
Input: Graph G = (V, E)
Output: Inclusion-maximal matching M
 
M = Ø // Initialize empty matching
while E is not empty:
    Choose an arbitrary edge e = {u, v} ∈ E
    M = M ∪ {e}  // Add e to matching
    Remove e and all incident edges from E
return M

The Greedy Matching Algorithm is simple and efficient, with a time complexity of $O (∣ E ∣)$ . However, it only guarantees an inclusion-maximal matching, which may not be a maximum matching.

Approximation Ratio of Greedy Matching: While the Greedy Matching Algorithm does not always produce a maximum matching, it provides a reasonable approximation. Satz 1.47 (Theorem 1.47) shows that the size of the matching produced by the Greedy Matching Algorithm is at least half the size of a maximum matching.

Theorem 1.47: The Greedy Matching Algorithm produces an inclusion-maximal matching $M_{G ree d y}$ in time $O (∣ E ∣)$ such that:

∣ M_{G ree d y} ∣ \geq \frac{1}{2} ∣ M_{ma x} ∣

where $M_{ma x}$ is a cardinality-maximal matching in $G$ .

Proof: The proof hinges on considering the symmetric difference (XOR) of $M_{G ree d y}$ and $M_{ma x}$ , $M_{G ree d y} \oplus M_{ma x}$ . By analyzing the properties of this symmetric difference and leveraging the inclusion-maximality of $M_{G ree d y}$ , we can establish the approximation bound. The details of the proof are provided in the script and offer a valuable example of how to analyze the performance of greedy algorithms in approximation problems.

Augmenting Paths for Maximum Matchings

To find a maximum matching, we need a more sophisticated approach than the simple greedy algorithm. The concept of augmenting paths provides a key tool for designing algorithms that find maximum matchings.

An augmenting path with respect to a matching $M$ is a path in the graph that starts and ends at unmatched vertices and alternates between edges that are not in $M$ and edges that are in $M$ . Augmenting paths provide a way to increase the size of a matching.

Satz 1.48 (Theorem 1.48, Berge’s Lemma): A matching $M$ in a graph $G = (V, E)$ is cardinality-maximal if and only if there is no augmenting path with respect to $M$ .

Proof: The proof shows that if a matching $M$ is not maximum, then an augmenting path must exist, and conversely, if no augmenting path exists, then the matching is maximum. The existence of an augmenting path implies that we can increase the size of the matching by “augmenting” along the path, swapping matched and unmatched edges along the augmenting path. This process increases the matching size by one.

Algorithm: Augmenting Path Algorithm (for Bipartite Graphs)

For bipartite graphs, augmenting paths can be efficiently found using a modified breadth-first search (BFS). The algorithm iteratively searches for augmenting paths and augments the matching until no more augmenting paths can be found.

Algorithm: augmenting_path(G = (A ∪ B, E), M)
Input: Bipartite graph G = (A ∪ B, E), matching M
Output: Augmenting path P (if exists) or indication that M is maximal
 
L0 = {unmatched vertices in A}
Mark vertices in L0 as visited
if L0 = Ø:
    return M is maximal
 
for i = 1 to n:
    if i is odd:
        Li = {unvisited neighbors of Li-1 via edges in E \ M} // Unmatched edges
    else: // i is even
        Li = {unvisited neighbors of Li-1 via edges in M} // Matched edges
    Mark vertices in Li as visited
    if Li contains an unmatched vertex v in B:
        Find path P from L0 to v by backtracking
        return P
 
return M is maximal

The algorithm constructs layers $L_{i}$ of vertices reachable from unmatched vertices in $A$ using alternating paths. If an unmatched vertex in $B$ is reached, an augmenting path is found. The algorithm has a time complexity of $O (∣ V ∣ \cdot ∣ E ∣)$ or $O (∣ V ∣ \cdot ∣ E ∣)$ with further optimizations (Hopcroft-Karp algorithm).

Hall’s Marriage Theorem (1.6.2)

For bipartite graphs, Hall’s Marriage Theorem (Satz 1.52) provides a necessary and sufficient condition for the existence of a perfect matching that matches all vertices in one partition (say, partition $A$ ).

Theorem 1.52 (Hall’s Marriage Theorem): For a bipartite graph $G = (A \cup B, E)$ , there exists a matching $M$ of cardinality $∣ M ∣ = ∣ A ∣$ (matching all vertices in $A$ ) if and only if for every subset $X \subseteq A$ , the neighborhood of $X$ , denoted $N (X)$ , satisfies the Hall’s condition:

∣ N (X) ∣ \geq ∣ X ∣ for all X \subseteq A

Hall’s condition essentially states that for any subset of vertices in $A$ , their collective neighborhood in $B$ must be at least as large as the subset itself. If this condition holds, a matching covering all vertices in $A$ is guaranteed to exist.

Satz 1.53: A consequence of Hall’s Theorem is that in a k-regular bipartite graph (where every vertex has degree $k$ ), the edge set can be decomposed into $k$ edge-disjoint perfect matchings.

Hall’s Marriage Theorem and its related concepts are fundamental tools in matching theory and have applications in various combinatorial problems.

Colorings (1.7)

Graph coloring is a fundamental concept in graph theory with wide-ranging applications, from map coloring to scheduling and resource allocation. Graph coloring involves assigning “colors” to vertices (or edges) of a graph subject to certain constraints.

Definition 1.56: A k-coloring of a graph $G = (V, E)$ is a function $c : V \to [k] = {1, 2, \dots, k}$ that assigns one of $k$ colors to each vertex such that no two adjacent vertices receive the same color. Formally, for every edge ${u, v} \in E$ , $c (u) \neq = c (v)$ .

The chromatic number $χ (G)$ of a graph $G$ is the minimum number of colors needed to color $G$ . A graph with chromatic number $k$ is called k-partite.

Properties of Graph Colorings

Chromatic Number of Complete Graphs: The chromatic number of a complete graph $K_{n}$ is $n$ , as every vertex must have a different color.
Chromatic Number of Cycles: Even cycles $C_{2 n}$ have a chromatic number of 2, while odd cycles $C_{2 n + 1}$ have a chromatic number of 3.
Chromatic Number of Trees: Trees with at least two vertices always have a chromatic number of 2 (they are bipartite).

Greedy Coloring Algorithm

A simple and widely used algorithm for graph coloring is the Greedy Coloring Algorithm. This algorithm iterates through the vertices in some order and assigns each vertex the smallest available color that is not already used by its neighbors.

Algorithm: Greedy Coloring Algorithm

Algorithm: Greedy-Färbung(G)
Input: Graph G = (V, E)
Output: Vertex coloring c
 
Choose an arbitrary vertex ordering: V = {v1, v2, ..., vn}
c[v1] = 1  // Color first vertex with color 1
 
for i = 2 to n:
    available_colors = {1, 2, ... , Δ(G) + 1} // All possible colors
    for each neighbor u of vi in {v1, ..., vi-1}:
        Remove color c[u] from available_colors
    c[vi] = min(available_colors) // Assign smallest available color

Theorem 1.60: For any connected graph $G = (V, E)$ , the Greedy Coloring Algorithm produces a coloring with at most $Δ (G) + 1$ colors, where $Δ (G)$ is the maximum degree of a vertex in $G$ . Furthermore, the algorithm runs in $O (∣ E ∣)$ time if the graph is represented using adjacency lists.

Brooks’ Theorem

Brooks’ Theorem provides a tighter bound on the chromatic number for most graphs.

Theorem 1.64 (Brooks’ Theorem): If $G = (V, E)$ is a connected graph that is neither a complete graph nor an odd cycle, then $χ (G) \leq Δ (G)$ .

Brooks’ Theorem states that for most graphs, we can color them with a maximum degree of colors, which is one less than the upper bound provided by the Greedy Coloring Algorithm. The exceptions are complete graphs and odd cycles, which require $Δ (G) + 1$ colors.

Mycielski’s Construction and Lower Bounds

While finding optimal graph colorings is generally NP-hard, Mycielski’s construction provides a way to construct triangle-free graphs with arbitrarily high chromatic numbers. This construction demonstrates that the chromatic number of a graph cannot be bounded solely by the absence of small cycles.

Satz 1.66 (Theorem 1.66, Mycielski’s Construction): For every $k \geq 2$ , there exists a triangle-free graph $G_{k}$ with chromatic number $χ (G_{k}) \geq k$ .

Mycielski’s construction iteratively builds larger triangle-free graphs with increasing chromatic numbers, starting from a simple edge. This construction is crucial in understanding the limitations of structural properties in bounding chromatic numbers.

3-Colorability and Approximation Algorithms

Determining whether a graph is 3-colorable is also NP-complete. However, for 3-colorable graphs, approximation algorithms exist that can color them with a bounded number of colors in polynomial time.

Satz 1.67 (Theorem 1.67): Every 3-colorable graph $G = (V, E)$ can be colored with $O (∣ V ∣)$ colors in $O (∣ E ∣)$ time.

This result demonstrates that while finding an optimal 3-coloring is hard, we can approximate the chromatic number for 3-colorable graphs relatively efficiently. The algorithm leverages the property that the neighborhood of any vertex in a 3-colorable graph is bipartite, allowing for efficient 2-coloring of neighborhoods and a recursive coloring strategy.

Graph coloring remains a vibrant area of research in graph theory and algorithm design, with ongoing efforts to develop more efficient algorithms and tighter bounds for graph coloring problems.

Prev: 05 Cycles, Euler Tours, Hamiltonian Cycles, Traveling Salesman Problem | Next: 01 Fundamentals, Probability Spaces and Events

CS Notes

Explorer