Bipartite Matching

Bipartite Matching คือการหา maximum matching ใน bipartite graph

Kuhn’s Algorithm (Hungarian Algorithm for Matching)

Simple augmenting path algorithm ที่หา maximum matching ใน $O(VE)$

Implementation

class BipartiteMatching {
    int n, m;  // n = left size, m = right size
    vector<vector<int>> adj;  // adjacency list for left side
    vector<int> match;  // match[right_node] = left_node (or -1)
    vector<bool> used;
    
    bool dfs(int v) {
        for (int to : adj[v]) {
            if (!used[to]) {
                used[to] = true;
                
                if (match[to] == -1 || dfs(match[to])) {
                    match[to] = v;
                    return true;
                }
            }
        }
        return false;
    }
    
public:
    BipartiteMatching(int n, int m) : n(n), m(m), adj(n), match(m, -1), used(m) {}
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }
    
    int maxMatching() {
        int result = 0;
        
        for (int v = 0; v < n; v++) {
            fill(used.begin(), used.end(), false);
            if (dfs(v)) {
                result++;
            }
        }
        
        return result;
    }
    
    // Get the matching pairs (left, right)
    vector<pair<int, int>> getMatching() {
        vector<pair<int, int>> result;
        for (int i = 0; i < m; i++) {
            if (match[i] != -1) {
                result.push_back({match[i], i});
            }
        }
        return result;
    }
};

Hopcroft-Karp Algorithm

Faster algorithm ที่หา maximum matching ใน $O(E \sqrt{V})$

Implementation

class HopcroftKarp {
    int n, m;
    vector<vector<int>> adj;
    vector<int> matchL, matchR;  // matchL[left] = right, matchR[right] = left
    vector<int> dist;
    
    bool bfs() {
        queue<int> q;
        
        for (int u = 0; u < n; u++) {
            if (matchL[u] == -1) {
                dist[u] = 0;
                q.push(u);
            } else {
                dist[u] = INT_MAX;
            }
        }
        
        bool found = false;
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            
            for (int v : adj[u]) {
                int next = matchR[v];
                
                if (next == -1) {
                    found = true;
                } else if (dist[next] == INT_MAX) {
                    dist[next] = dist[u] + 1;
                    q.push(next);
                }
            }
        }
        
        return found;
    }
    
    bool dfs(int u) {
        for (int v : adj[u]) {
            int next = matchR[v];
            
            if (next == -1 || (dist[next] == dist[u] + 1 && dfs(next))) {
                matchL[u] = v;
                matchR[v] = u;
                return true;
            }
        }
        
        dist[u] = INT_MAX;
        return false;
    }
    
public:
    HopcroftKarp(int n, int m) : n(n), m(m), adj(n), matchL(n, -1), matchR(m, -1), dist(n) {}
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }
    
    int maxMatching() {
        int result = 0;
        
        while (bfs()) {
            for (int u = 0; u < n; u++) {
                if (matchL[u] == -1 && dfs(u)) {
                    result++;
                }
            }
        }
        
        return result;
    }
    
    vector<pair<int, int>> getMatching() {
        vector<pair<int, int>> result;
        for (int u = 0; u < n; u++) {
            if (matchL[u] != -1) {
                result.push_back({u, matchL[u]});
            }
        }
        return result;
    }
};

ทฤษฎีที่เกี่ยวข้อง

Konig’s Theorem

ใน bipartite graph:

$\text{Maximum Matching} = \text{Minimum Vertex Cover}$

Hall’s Theorem

Bipartite graph $G = (L \cup R, E)$ มี matching ที่ saturates $L$ ทั้งหมด ก็ต่อเมื่อ:

$|N(S)| \geq |S| \text{ สำหรับทุก } S \subseteq L$

โดยที่ $N(S)$ คือ neighbors ของ $S$

หา Minimum Vertex Cover

vector<int> minVertexCover() {
    // Run max matching first
    maxMatching();
    
    // BFS from unmatched left vertices
    vector<bool> visitedL(n, false), visitedR(m, false);
    queue<int> q;
    
    for (int u = 0; u < n; u++) {
        if (matchL[u] == -1) {
            q.push(u);
            visitedL[u] = true;
        }
    }
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int v : adj[u]) {
            if (!visitedR[v]) {
                visitedR[v] = true;
                
                if (matchR[v] != -1 && !visitedL[matchR[v]]) {
                    visitedL[matchR[v]] = true;
                    q.push(matchR[v]);
                }
            }
        }
    }
    
    // Vertex cover: unvisited left + visited right
    vector<int> cover;
    for (int u = 0; u < n; u++) {
        if (!visitedL[u]) cover.push_back(u);  // left side
    }
    for (int v = 0; v < m; v++) {
        if (visitedR[v]) cover.push_back(n + v);  // right side
    }
    
    return cover;
}

ประยุกต์ใช้งาน

1. Job Assignment

แต่ละคนทำได้ 1 งาน, แต่ละงานต้องการ 1 คน

int maxJobs(int workers, int jobs, vector<pair<int,int>>& canDo) {
    BipartiteMatching bm(workers, jobs);
    for (auto& [w, j] : canDo) {
        bm.addEdge(w, j);
    }
    return bm.maxMatching();
}

2. Domino Covering

นับจำนวน dominoes ที่วางได้บน grid (cells เป็น bipartite โดย checkerboard pattern)

3. Independent Set in Bipartite Graph

$\text{Maximum Independent Set} = V - \text{Minimum Vertex Cover}$

4. Edge Cover

$\text{Minimum Edge Cover} = V - \text{Maximum Matching}$ (ถ้าไม่มี isolated vertices)

Complexity Comparison

Algorithm	Time	Space
Kuhn	$O(VE)$	$O(V + E)$
Hopcroft-Karp	$O(E \sqrt{V})$	$O(V + E)$
Max Flow (Dinic)	$O(E \sqrt{V})$	$O(V + E)$

Tips

1. Kuhn’s algorithm ง่ายต่อการ implement และเร็วพอสำหรับกรณีส่วนใหญ่
2. Hopcroft-Karp เร็วกว่าสำหรับ large sparse graphs
3. Max Flow ยืดหยุ่นกว่า - ใช้ได้กับ weighted matching (ใช้ MCMF)
4. Vertex ordering ใน Kuhn อาจมีผลต่อ performance