Matching and Covering

Matching

Definition

A matching $M$ in a graph $G$ is a set of edges with no shared vertices.

Vertices incident to edges in $M$ are matched or saturated.

Types of Matchings

Maximum matching: Matching with maximum number of edges.

Perfect matching: Matching that saturates all vertices. (Exists only if $|V|$ is even)

Maximal matching: Matching that can't be extended by adding more edges. (Not necessarily maximum)

Hall's Marriage Theorem

For a bipartite graph $G = (X \cup Y, E)$:

A matching that saturates $X$ exists if and only if: $|N(S)| \geq |S| \text{ for all } S \subseteq X$

where $N(S)$ = set of neighbors of vertices in $S$.

Corollary

A $k$-regular bipartite graph has a perfect matching.

Matching in Bipartite Graphs

König's Theorem

In a bipartite graph: $\text{maximum matching size} = \text{minimum vertex cover size}$

Finding Maximum Matching

Hungarian Algorithm: $O(|V|^3)$

Hopcroft-Karp Algorithm: $O(|E|\sqrt{|V|})$

Alternating and Augmenting Paths

Alternating path: Path alternating between matching and non-matching edges.

Augmenting path: Alternating path from unmatched vertex to unmatched vertex.

Berge's Lemma: A matching is maximum iff there's no augmenting path.

Vertex Cover

Definition

A vertex cover is a set of vertices such that every edge has at least one endpoint in the set.

Minimum vertex cover: Vertex cover of minimum size.

Relationship to Independent Set

$S$ is a vertex cover iff $V - S$ is an independent set.

$\alpha(G) + \tau(G) = |V|$

where $\alpha(G)$ = independence number, $\tau(G)$ = vertex cover number.

Edge Cover

Definition

An edge cover is a set of edges such that every vertex is incident to at least one edge.

Only exists if graph has no isolated vertices.

Relationship to Matching

Gallai's Theorem: For graph $G$ with no isolated vertices: $|M^*| + |C^*| = |V|$

where $|M^*|$ = maximum matching size, $|C^*|$ = minimum edge cover size.

König-Egerváry Theorem

For bipartite graphs: $\nu(G) = \tau(G)$

where $\nu(G)$ = maximum matching size, $\tau(G)$ = minimum vertex cover size.

Stable Matching Problem

Input: $n$ men, $n$ women, each with complete preference rankings.

Goal: Find a stable matching (no pair would rather be together than with current partners).

Gale-Shapley Algorithm

while some man m is free and hasn't proposed to everyone:
    m proposes to his most preferred woman w he hasn't proposed to
    if w is free:
        w accepts
    else if w prefers m to current partner m':
        w accepts m, m' becomes free
    else:
        w rejects m

Properties

• Always finds a stable matching
• Men-proposing version is men-optimal, women-pessimal
• Runs in $O(n^2)$ time

Weighted Matching

Assignment Problem

Given bipartite graph with edge weights, find maximum-weight perfect matching.

Solved by:

• Hungarian Algorithm: $O(n^3)$
• Auction Algorithm

Applications

• Job assignment
• Resource allocation
• Transportation problems

Network Flow Connection

Maximum Bipartite Matching via Flow

1. Add source $s$ connected to all vertices in $X$
2. Add sink $t$ connected to all vertices in $Y$
3. Direct all edges from $X$ to $Y$
4. All capacities = 1
5. Maximum flow = maximum matching size

General Graph Matching

Tutte's Theorem

Graph $G$ has a perfect matching iff for every $S \subseteq V$: $o(G - S) \leq |S|$

where $o(G - S)$ = number of odd components in $G - S$.

Edmond's Blossom Algorithm

Finds maximum matching in general graphs in $O(|V|^3)$.

Applications

Job Assignment

Workers as one side, jobs as other. Edge if worker can do job.

Matching Markets

Doctors to hospitals, students to schools.

Resource Allocation

Tasks to machines with capacity constraints.