Maximum Matching: Find Maximum Bipartite Matching Using Augmenting Paths

Question

## Problem

Given a bipartite graph where left nodes are workers and right nodes are tasks, and each edge means a worker can perform that task, find the maximum number of tasks that can be assigned (one task per worker, one worker per task).

```python
def max_matching(n: int, m: int, edges: list[tuple[int,int]]) -> int:
    # n: number of workers (0..n-1)
    # m: number of tasks (0..m-1)
    # edges: list of (worker, task) indicating compatibility
    # returns: size of maximum matching
    pass

def find_matching(n: int, m: int, edges: list[tuple[int,int]]) -> dict[int,int]:
    # returns: dict mapping worker -> assigned task (only matched workers)
    pass
```

**Example:**
```
edges = [(0,0),(0,1),(1,1),(2,2)]
max_matching(3, 3, edges) -> 3
find_matching(3, 3, edges) -> {0: 0, 1: 1, 2: 2}
```

## Follow-ups

1. Walk through the augmenting path algorithm. What is its time complexity?
2. How does Hopcroft-Karp improve on the naive augmenting path approach?
3. How would you model task scheduling with deadlines as a maximum matching problem?
4. When might a minimum vertex cover be more useful than maximum matching?

Maximum Matching: Find Maximum Bipartite Matching Using Augmenting Paths

Question Details

Full Details

Topics

More from Waymo