Bipartite Graphs - Learning Module

Loading content...

0/276

Applications — Matching Problems

Where Bipartite Graphs Change Everything

Recognizing that a problem has a bipartite structure isn't just an academic observation — it fundamentally changes what's computationally possible. Problems that are NP-hard on general graphs often become polynomial-time solvable on bipartite graphs. Algorithms that run in O(V³) can drop to O(V²) or even O(V√V).

This page explores the crown jewel of bipartite graph applications: matching problems. From assigning jobs to workers, to scheduling courses in time slots, to optimizing resource allocation — matching is everywhere in computer science and operations research. The bipartite structure makes these problems tractable, and understanding the algorithms opens doors to solving real-world optimization challenges.

What You Will Learn

You will master the theory and practice of bipartite matching, from basic definitions to the Hopcroft-Karp algorithm. You'll understand König's theorem and its implications, learn Hall's marriage theorem for perfect matching existence, and explore diverse real-world applications including job assignment, scheduling, and network flow.

Introduction to Matching in Graphs

Before diving into bipartite-specific algorithms, let's establish the fundamental concepts of graph matching that apply to all graphs.

Definition: Matching

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 appears in at most one edge of M.

Alternatively: M ⊆ E where for all distinct edges e₁, e₂ ∈ M, we have e₁ ∩ e₂ = ∅ (as sets of vertices).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
Graph G:
    A ───── B
    │       │
    │       │
    C ───── D
    │       │
    │       │
    E ───── F
 
Possible Matchings:
 
M₁ = {(A,B), (C,D), (E,F)}     ← Size 3, Maximum Matching
    A ══════ B                   (matched edges shown with ═)
    │        │
    C ══════ D
    │        │
    E ══════ F
 
M₂ = {(A,C), (B,D)}            ← Size 2, Not Maximum
    A        B
    ║        ║
    C        D
    │        │
    E ───── F
 
M₃ = {(A,B)}                   ← Size 1, Valid but small
    A ══════ B
    │        │
    C        D
    │        │
    E ───── F
 
Invalid (NOT a matching):
{(A,B), (A,C)}                 ← Vertex A appears in TWO edges!

Key Matching Terminology:

Matched Vertex: A vertex that is an endpoint of some edge in M.

Unmatched/Free Vertex: A vertex not covered by any edge in M.

Maximum Matching: A matching of maximum possible size (most edges).

Perfect Matching: A matching where every vertex is matched. Requires |V| to be even, and the matching has size |V|/2.

Maximal Matching: A matching that cannot be extended by adding more edges (but may not be maximum). Every maximum matching is maximal, but not vice versa.

Maximal ≠ Maximum

A common confusion: Maximal means 'can't add more edges' while Maximum means 'largest possible size.' A maximal matching can be arbitrarily smaller than maximum. Example: in a path A-B-C-D, matching {(B,C)} is maximal (can't add A-B or C-D without overlap) but not maximum ({(A,B), (C,D)} is larger).

Bipartite Matching — The Core Problem

In bipartite graphs, matching takes on special significance. The two partitions often represent distinct entity types (workers and jobs, students and courses), and finding a good matching has immediate practical value.

Bipartite Matching Problem

Given a bipartite graph G = (U ∪ W, E), find a matching M of maximum size. Since all edges connect U to W, each edge in M pairs exactly one vertex from U with one vertex from W.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Job Seekers (U)              Employers (W)
┌─────────────┐              ┌─────────────┐
│             │              │             │
│   Alice ●━━━━━━━━━━━━━━━━━━● Google     │
│         │╲                 │             │
│   Bob   ●━━━━━━━━━━━━━━━━━━● Meta       │
│         │  ╲               │╱            │
│  Carol  ●━━━━━━━━━━━━━━━━━━● Amazon     │
│         │    ╲            ╱│             │
│   Dave  ●━━━━━━━━━╳━━━━━━━━● Microsoft  │
│             │              │             │
└─────────────┘              └─────────────┘
 
Maximum Matching (size 4):
  Alice ─── Google
  Bob   ─── Meta
  Carol ─── Amazon
  Dave  ─── Microsoft
 
Every job seeker gets a unique employer assignment!
 
Note: The matching uses 4 edges out of many possible edges,
and each person/company appears in exactly one matched edge.

Why Bipartite Matching is Special:

1. Efficient Algorithms Exist For general graphs, maximum matching requires complex algorithms like Blossom (O(V³)). For bipartite graphs, simpler and faster algorithms suffice:

Hopcroft-Karp: O(E√V)
Hungarian Algorithm (weighted): O(V³)
Augmenting path method: O(VE)

2. Theoretical Tools Apply König's theorem, Hall's theorem, and other powerful results are specific to bipartite graphs.

3. Natural Problem Modeling Many real-world problems naturally model as bipartite matching: assignment problems, scheduling, resource allocation.

Matching Complexity: General vs. Bipartite
Problem	General Graph	Bipartite Graph
Maximum Matching	O(V²E) or O(V³) Blossom	O(E√V) Hopcroft-Karp
Perfect Matching Decision	O(V²E)	O(E√V) + Hall check
Weighted Max Matching	O(V³) or O(VE log V)	O(V³) Hungarian
Counting Perfect Matchings	#P-complete (very hard)	O(n³) or O(n^ω) with FKT

Augmenting Paths — The Key to Maximum Matching

The foundational concept for matching algorithms is the augmenting path. Understanding augmenting paths reveals both why a matching isn't maximum and how to improve it.

Definition: Augmenting Path

Given a matching M, an augmenting path is a path in the graph that:

Starts at an unmatched vertex
Ends at a different unmatched vertex
Alternates between edges NOT in M and edges IN M

The path has odd length: it contains one more non-matched edge than matched edges.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
Current Matching M = {(B, 2), (C, 3)}
 
    Left           Right
    
  A (free) ─────── 1 (free)    ← Unmatched vertices
           ╲
  B ════════════ 2              ═══ = Matched edge
           ╲     ║
  C ════════════ 3
           ╲     ║
  D (free) ─────── 4 (free)
 
Augmenting Path P: A → 2 → B → 1
 
    A (free) ──── 2 (matched to B)
                  │
    B ──────────── 1 (free)
 
Path breakdown:
  A → 2: NOT in M (unmatched edge)
  2 → B: IN M (matched edge)  
  B → 1: NOT in M (unmatched edge)
 
Path length: 3 edges (odd ✓)
Path starts at free vertex A, ends at free vertex 1 ✓
 
AUGMENT: Flip all edges along the path
  - Remove (B, 2) from M
  - Add (A, 2) and (B, 1) to M
 
New Matching M' = {(A, 2), (B, 1), (C, 3)}
  Size increased from 2 to 3!

The Augmenting Path Theorem (Berge's Theorem):

A matching M is maximum if and only if there is no augmenting path with respect to M.

This theorem is constructive: it tells us both how to check if we're done (no augmenting path exists) and how to improve if we're not (augment along the path).

Why Augmenting Works:

An augmenting path has k matched edges and k+1 unmatched edges (for some k ≥ 0). When we 'flip' the path:

The k matched edges become unmatched
The k+1 unmatched edges become matched
Net change: -k + (k+1) = +1 edge in matching

The endpoints that were free remain matched (to their new partners), and we gain one edge.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/**
 * Simple O(VE) algorithm for bipartite maximum matching.
 * Uses BFS to find augmenting paths, one at a time.
 */
function bipartiteMaxMatching(
  leftVertices: number[],
  rightVertices: number[],
  edges: Map<number, number[]>  // left vertex -> list of right neighbors
): Map<number, number> {
  // matchL[u] = right vertex matched to left vertex u (-1 if unmatched)
  // matchR[v] = left vertex matched to right vertex v (-1 if unmatched)
  const matchL = new Map<number, number>();
  const matchR = new Map<number, number>();
  
  // Initialize all as unmatched
  for (const u of leftVertices) matchL.set(u, -1);
  for (const v of rightVertices) matchR.set(v, -1);
  
  let matchingSize = 0;
  
  // Try to find augmenting path from each unmatched left vertex
  for (const startU of leftVertices) {
    if (matchL.get(startU) !== -1) continue; // Already matched
    
    // BFS for augmenting path
    const visited = new Set<number>();
    const parent = new Map<number, number>(); // right vertex -> left vertex we came from
    const queue: number[] = [startU];
    const leftParent = new Map<number, number>(); // left vertex -> right vertex we came from
    leftParent.set(startU, -1);
    
    let augmentingEndpoint = -1;
    
    bfsLoop: while (queue.length > 0) {
      const u = queue.shift()!;
      
      for (const v of edges.get(u) || []) {
        if (visited.has(v)) continue;
        visited.add(v);
        parent.set(v, u);
        
        const matchedTo = matchR.get(v)!;
        if (matchedTo === -1) {
          // Found augmenting path! v is unmatched on right
          augmentingEndpoint = v;
          break bfsLoop;
        } else {
          // v is matched; continue through its partner
          leftParent.set(matchedTo, v);
          queue.push(matchedTo);
        }
      }
    }
    
    if (augmentingEndpoint !== -1) {
      // Augment along the path
      let v = augmentingEndpoint;
      while (v !== -1) {
        const u = parent.get(v)!;
        const prevV = leftParent.get(u)!;
        
        matchL.set(u, v);
        matchR.set(v, u);
        
        v = prevV;
      }
      matchingSize++;
    }
  }
  
  // Return the matching as left -> right map
  const result = new Map<number, number>();
  for (const [u, v] of matchL) {
    if (v !== -1) result.set(u, v);
  }
  return result;
}

Complexity Analysis

The simple algorithm above runs in O(VE): we try O(V) augmenting paths, each requiring O(E) BFS. The Hopcroft-Karp algorithm improves this to O(E√V) by finding multiple augmenting paths simultaneously using layered BFS.

König's Theorem — The Matching-Cover Duality

One of the most beautiful results in graph theory is König's theorem, which establishes a surprising equality between maximum matching and minimum vertex cover in bipartite graphs. This duality doesn't hold for general graphs, making it a signature property of bipartite structure.

Definitions: Vertex Cover and Independent Set

Vertex Cover: A set S ⊆ V such that every edge has at least one endpoint in S. (S 'covers' all edges.)

Independent Set: A set S ⊆ V such that no two vertices in S are adjacent. (S has no edges within it.)

Note: S is an independent set ⟺ V \ S is a vertex cover.

König's Theorem (1931)

In any bipartite graph:

Maximum Matching Size = Minimum Vertex Cover Size

Equivalently: Maximum Matching Size = |V| - Maximum Independent Set Size

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
Bipartite Graph:
    Left       Right
    
    A ─────────── 1
    │╲           ╱│
    │ ╲         ╱ │
    B ──╲─────╱── 2
    │    ╲   ╱    │
    │     ╲ ╱     │
    C ──────X──── 3
           ╱╲
          ╱  ╲
    D ───╱────╲── 4
 
Maximum Matching (size 4):
    A ═══ 1
    B ═══ 2
    C ═══ 3
    D ═══ 4
 
Minimum Vertex Cover (size 4):
    Option 1: {A, B, C, D} (all left vertices)
    Option 2: {1, 2, 3, 4} (all right vertices)
    
    Any smaller set would miss some edge!
 
König's Theorem: |Maximum Matching| = |Minimum Vertex Cover| = 4 ✓
 
───────────────────────────────────────────────────────────
 
Contrast with non-bipartite graph (Triangle):
 
    A ─── B
     ╲   ╱
      ╲ ╱
       C
 
Maximum Matching: size 1  (e.g., {(A, B)})
Minimum Vertex Cover: size 2  (e.g., {A, B} to cover all 3 edges)
 
König's Theorem does NOT hold: 1 ≠ 2

Why König's Theorem Matters:

1. Algorithmic Implications Since minimum vertex cover is NP-hard on general graphs but maximum matching is polynomial, König's theorem gives us a polynomial algorithm for minimum vertex cover on bipartite graphs!

2. Problem Reduction If you can model a problem as bipartite vertex cover, you can solve it via matching.

3. LP Duality König's theorem is a special case of LP duality. The matching problem and vertex cover problem are LP duals, and for bipartite graphs, the integrality gap is zero.

Constructing the Minimum Vertex Cover:

Given a maximum matching M, we can construct the minimum vertex cover:

Run BFS from all unmatched left vertices
Follow unmatched edges left→right, matched edges right→left
Mark all reachable right vertices and unreachable left vertices
This set is the minimum vertex cover

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/**
 * Given a maximum matching, constructs the minimum vertex cover.
 * Based on König's theorem constructive proof.
 */
function minimumVertexCover(
  leftVertices: number[],
  rightVertices: number[],
  edges: Map<number, number[]>,
  matching: Map<number, number>  // left -> right
): Set<number> {
  // Build reverse matching
  const reverseMatch = new Map<number, number>();
  for (const [l, r] of matching) {
    reverseMatch.set(r, l);
  }
  
  // Find all unmatched left vertices
  const unmatchedLeft = leftVertices.filter(u => !matching.has(u));
  
  // BFS to find all vertices reachable via alternating paths
  // from unmatched left vertices
  const reachableLeft = new Set<number>(unmatchedLeft);
  const reachableRight = new Set<number>();
  
  const queue: Array<{ vertex: number; isLeft: boolean }> = 
    unmatchedLeft.map(u => ({ vertex: u, isLeft: true }));
  
  while (queue.length > 0) {
    const { vertex, isLeft } = queue.shift()!;
    
    if (isLeft) {
      // From left vertex, follow unmatched edges to right
      for (const r of edges.get(vertex) || []) {
        if (!reachableRight.has(r)) {
          // Only follow if this edge is NOT in matching
          if (matching.get(vertex) !== r) {
            reachableRight.add(r);
            queue.push({ vertex: r, isLeft: false });
          }
        }
      }
    } else {
      // From right vertex, follow matched edge back to left
      const matchedLeft = reverseMatch.get(vertex);
      if (matchedLeft !== undefined && !reachableLeft.has(matchedLeft)) {
        reachableLeft.add(matchedLeft);
        queue.push({ vertex: matchedLeft, isLeft: true });
      }
    }
  }
  
  // Minimum vertex cover = 
  //   (left vertices NOT reachable) ∪ (right vertices reachable)
  const cover = new Set<number>();
  
  for (const u of leftVertices) {
    if (!reachableLeft.has(u)) {
      cover.add(u);
    }
  }
  
  for (const v of reachableRight) {
    cover.add(v);
  }
  
  return cover;
}

Hall's Marriage Theorem — When Perfect Matching Exists

While maximum matching always exists (just find it!), sometimes we need to know if a perfect matching exists — one that matches every vertex. Hall's Marriage Theorem provides a beautiful characterization for bipartite graphs.

Hall's Marriage Theorem (1935)

A bipartite graph G = (U ∪ W, E) has a matching that saturates all of U (matches every vertex in U) if and only if:

For every subset S ⊆ U, |N(S)| ≥ |S|

where N(S) is the set of all neighbors of vertices in S.

This condition is called Hall's Condition or the Marriage Condition.

Intuitive Explanation:

Imagine U represents people looking for partners and W represents potential partners. Hall's condition says:

Any single person must have at least 1 option
Any pair of people must together have at least 2 options (combined)
Any k people must together have at least k options

If 3 people all want to match with only 2 potential partners, it's impossible for everyone to get a match. Hall's theorem says this is the only obstacle.

Why '≥' and not '>'?

Equal is fine: if 3 people together have exactly 3 options, those 3 options might be enough — as long as the constraint holds for all subsets.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
EXAMPLE 1: Hall's Condition SATISFIED
 
Candidates: {Alice, Bob, Carol}
Jobs:       {Engineer, Designer, Manager}
 
Edges (who can do what job):
  Alice → {Engineer, Designer}
  Bob   → {Designer, Manager}
  Carol → {Engineer, Manager}
 
Check Hall's Condition for all subsets of Candidates:
  {Alice}:         N = {Engineer, Designer}        |N| = 2 ≥ 1 ✓
  {Bob}:           N = {Designer, Manager}         |N| = 2 ≥ 1 ✓
  {Carol}:         N = {Engineer, Manager}         |N| = 2 ≥ 1 ✓
  {Alice, Bob}:    N = {Engineer, Designer, Mgr}   |N| = 3 ≥ 2 ✓
  {Alice, Carol}:  N = {Engineer, Designer, Mgr}   |N| = 3 ≥ 2 ✓
  {Bob, Carol}:    N = {Designer, Engineer, Mgr}   |N| = 3 ≥ 2 ✓
  {All three}:     N = {All three jobs}            |N| = 3 ≥ 3 ✓
 
Hall's Condition satisfied! Perfect matching exists.
  Alice → Designer, Bob → Manager, Carol → Engineer
 
───────────────────────────────────────────────────────────
 
EXAMPLE 2: Hall's Condition VIOLATED
 
Candidates: {Alice, Bob, Carol}
Jobs:       {Engineer, Designer, Manager}
 
Edges (restricted):
  Alice → {Engineer}
  Bob   → {Engineer}
  Carol → {Engineer, Manager}
 
Check Hall's Condition:
  {Alice}:         N = {Engineer}                  |N| = 1 ≥ 1 ✓
  {Bob}:           N = {Engineer}                  |N| = 1 ≥ 1 ✓
  {Alice, Bob}:    N = {Engineer}                  |N| = 1 ≥ 2 ✗ FAIL!
 
Hall's Condition violated! No perfect matching exists.
Alice and Bob both need Engineer, but there's only one!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/**
 * Checks if Hall's condition is satisfied for left vertices.
 * 
 * Note: Checking ALL subsets takes O(2^n) time!
 * In practice, we just try to find a matching and see if it saturates U.
 * This function is for educational purposes / small graphs.
 */
function checkHallsCondition(
  leftVertices: number[],
  edges: Map<number, number[]>
): { satisfied: boolean; violatingSubset?: number[] } {
  const n = leftVertices.length;
  
  // Check all 2^n - 1 non-empty subsets
  for (let mask = 1; mask < (1 << n); mask++) {
    const subset: number[] = [];
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) {
        subset.push(leftVertices[i]);
      }
    }
    
    // Compute neighborhood of subset
    const neighborhood = new Set<number>();
    for (const u of subset) {
      for (const v of edges.get(u) || []) {
        neighborhood.add(v);
      }
    }
    
    // Check Hall's condition
    if (neighborhood.size < subset.length) {
      return {
        satisfied: false,
        violatingSubset: subset,
      };
    }
  }
  
  return { satisfied: true };
}
 
/**
 * Practical approach: just find matching and check size.
 * Much faster than checking Hall's condition directly.
 */
function hasPerfectMatching(
  leftVertices: number[],
  rightVertices: number[],
  edges: Map<number, number[]>
): boolean {
  // Perfect matching requires |U| = |W|
  if (leftVertices.length !== rightVertices.length) {
    return false;
  }
  
  // Find maximum matching
  const matching = bipartiteMaxMatching(leftVertices, rightVertices, edges);
  
  // Check if all left vertices are matched
  return matching.size === leftVertices.length;
}
 
// Reference to earlier function
function bipartiteMaxMatching(
  leftVertices: number[],
  rightVertices: number[],
  edges: Map<number, number[]>
): Map<number, number> {
  // Implementation from Section 3
  // ...
  return new Map(); // placeholder
}

Practical Implication

Don't actually enumerate all 2^n subsets to check Hall's condition! Instead, find a maximum matching and check if it's perfect. If not perfect, the unmatched vertices reveal a violating subset. This is much more efficient.

Real-World Applications of Bipartite Matching

Bipartite matching appears in countless real-world scenarios. Understanding these applications helps you recognize matching problems in disguise and apply the efficient algorithms we've learned.

Classic Application: Job Assignment

•Workers ↔ Tasks: Each worker has skills; each task requires certain skills. Edges connect workers to compatible tasks. Maximum matching assigns tasks to workers optimally.
•Job Seekers ↔ Job Openings: Edges represent application/qualification. Maximum matching maximizes successful placements.
•Interns ↔ Teams: Each intern has preferences; teams have capacity. Bipartite matching with preferences leads to stable matching problems.

Scheduling Applications

•Courses ↔ Time Slots: Each course has availability constraints. Check bipartiteness of the 'conflict graph' to determine if 2-room scheduling works.
•Employees ↔ Shifts: Each employee has availability. Maximum matching assigns shifts without conflicts.
•Meetings ↔ Rooms: Meetings have time/resource requirements. Bipartite matching allocates rooms efficiently.
•Sports Scheduling: Teams ↔ Time slots, avoiding conflicts where a team plays twice simultaneously.

Network and System Applications

•Load Balancing: Requests ↔ Servers. Matching distributes load evenly and respects capacity.
•Network Switches: Input ports ↔ Output ports. Matching determines non-conflicting transmission schedules.
•Streaming Services: Users ↔ Content servers. CDN routing uses bipartite matching for efficient delivery.
•Microservices: Client requests ↔ Service instances. Matching balances across healthy instances.

Matching and Pairing Applications

•Kidney Exchange: Donors ↔ Recipients based on compatibility. Maximum matching saves the most lives.
•Dating Apps: Users ↔ Users (can be bipartite in traditional models). Matching maximizes mutual interest.
•Mentorship Programs: Mentors ↔ Mentees based on expertise/goals. Matching creates productive pairs.
•Roommate Assignment: Students ↔ Students based on compatibility scores.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/**
 * Real-world example: Scheduling courses into time slots.
 * Each course can only be offered in certain time slots.
 * Goal: Maximize courses offered.
 */
interface Course {
  id: string;
  name: string;
  availableSlots: string[];  // Time slots this course can use
}
 
interface TimeSlot {
  id: string;
  label: string;  // e.g., "Monday 9-10am"
}
 
function scheduleCourses(
  courses: Course[],
  timeSlots: TimeSlot[]
): Map<string, string> {  // course -> timeSlot
  // Build bipartite graph
  const leftVertices = courses.map(c => c.id);
  const rightVertices = timeSlots.map(t => t.id);
  
  const edges = new Map<string, string[]>();
  for (const course of courses) {
    edges.set(course.id, course.availableSlots);
  }
  
  // Find maximum matching
  const matching = bipartiteMaxMatchingGeneric(leftVertices, rightVertices, edges);
  
  // Report results
  const scheduled = matching.size;
  const unscheduled = courses.length - scheduled;
  console.log(`Scheduled ${scheduled} courses, ${unscheduled} unscheduled`);
  
  return matching;
}
 
// Example usage:
const courses: Course[] = [
  { id: "CS101", name: "Intro to CS", availableSlots: ["Mon9", "Wed9", "Fri9"] },
  { id: "CS201", name: "Data Structures", availableSlots: ["Mon9", "Tue10"] },
  { id: "CS301", name: "Algorithms", availableSlots: ["Tue10", "Thu10"] },
  { id: "CS401", name: "AI", availableSlots: ["Wed9", "Fri9"] },
];
 
const slots: TimeSlot[] = [
  { id: "Mon9", label: "Monday 9-10am" },
  { id: "Tue10", label: "Tuesday 10-11am" },
  { id: "Wed9", label: "Wednesday 9-10am" },
  { id: "Fri9", label: "Friday 9-10am" },
  { id: "Thu10", label: "Thursday 10-11am" },
];
 
// scheduleCourses(courses, slots);
// Output might be: CS101→Fri9, CS201→Mon9, CS301→Tue10, CS401→Wed9
 
function bipartiteMaxMatchingGeneric<T>(
  left: T[],
  right: T[],
  edges: Map<T, T[]>
): Map<T, T> {
  // Generic implementation...
  return new Map(); // placeholder
}

Weighted Bipartite Matching

Many real applications involve weighted edges (e.g., worker-task proficiency scores). The Hungarian algorithm solves max-weight bipartite matching in O(V³). For job assignment with varying skill levels, linear programming approaches also work well.

Beyond Matching — Other Bipartite Applications

While matching is the star application, bipartite structure enables efficient solutions to many other problems. Here's a survey of additional applications where recognizing bipartiteness is key.

Additional Bipartite Graph Applications
Problem	Bipartite Context	Why Bipartiteness Helps
Independent Set	Find largest set with no edges	= V - Min Vertex Cover, solvable via König
Vertex Cover	Cover all edges with fewest vertices	= Max Matching size (König's theorem)
Edge Coloring	Color edges, no vertex has same color twice	Always needs Δ or Δ+1 colors (König's edge coloring)
2-SAT Modeling	Certain constraint patterns	Bipartite implications enable efficient solving
Network Flow	Max flow in special networks	Bipartite matching reduces to max flow
Stable Matching	Find stable pairings	Gale-Shapley algorithm works on bipartite preference graphs
Graph Coloring	Color vertices with min colors	Always 2 colors (trivial for bipartite)
Dominating Set	Select vertices to cover all	Still NP-hard, but good approximations exist

Connection to Network Flow:

Bipartite matching can be reduced to maximum flow:

Add a source vertex s connected to all left vertices
Add a sink vertex t connected to all right vertices
Direct all edges: s → left → right → t
Set all capacities to 1
Maximum flow in this network = Maximum matching size

This reduction shows that bipartite matching is a special case of the broader network flow framework. It also provides an alternative algorithm: use any max-flow algorithm (Ford-Fulkerson, Edmonds-Karp, etc.) on the constructed network.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Original Bipartite Graph:
 
    A ─────── 1
    │         │
    B ─────── 2
    │
    C ─────── 3
 
Flow Network Construction:
 
         ┌──→ A ──→ 1 ──┐
         │    ↓         │
    s ───┼──→ B ──→ 2 ──┼──→ t
         │              │
         └──→ C ──→ 3 ──┘
 
All edges have capacity 1.
Max flow = 3 (s→A→1→t, s→B→2→t, s→C→3→t)
Max matching = 3 edges: (A,1), (B,2), (C,3)

Algorithm Selection

For pure bipartite matching, specialized algorithms (Hopcroft-Karp) are faster than generic flow algorithms. But when matching is part of a larger flow problem, or when you need other flow properties, the reduction is valuable.

Summary: Applications of Bipartite Graphs

We've explored the rich landscape of bipartite graph applications, with matching at the center. Let's consolidate the key insights:

Key Takeaways

•Matching is the core application — Maximum bipartite matching is solvable in O(E√V) with Hopcroft-Karp, enabling efficient assignment and scheduling.
•Augmenting paths drive matching algorithms — Berge's theorem: a matching is maximum iff no augmenting path exists. Finding and augmenting paths grows the matching.
•König's theorem links matching and covering — Max matching = Min vertex cover in bipartite graphs. This duality makes vertex cover polynomial-time solvable.
•Hall's theorem characterizes perfect matching — A bipartite graph has a perfect matching iff every subset S has at least |S| neighbors.
•Real-world applications are ubiquitous — Job assignment, course scheduling, load balancing, medical matching, and more all reduce to bipartite matching.
•Bipartite structure unlocks efficiency — Many NP-hard problems on general graphs become polynomial on bipartite graphs.

The Bigger Picture:

Bipartite graphs represent one of the most productive intersections of theory and practice in computer science. The elegant theorems (König, Hall, Berge) aren't just theoretical curiosities — they directly enable efficient algorithms that solve real problems.

When you encounter a problem involving two distinct types of entities with relationships between them, ask: Is this bipartite? If yes, you've unlocked:

O(E√V) matching algorithms
Polynomial-time vertex cover
Polynomial-time independent set
Guaranteed 2-colorability
Clean problem structure

This recognition skill separates engineers who struggle with NP-hard problems from those who solve them elegantly.

Module Complete

Congratulations! You've mastered bipartite graphs — from definition to detection to applications. You can now recognize bipartite structure, verify it efficiently with 2-coloring, and leverage the special algorithms that bipartiteness enables. This knowledge is directly applicable to interview problems and real-world system design.