Cặp ghép II: Thuật toán Hopcroft-Karp -- Matching II: Hopcroft-Karp algorithm

Bài này chúng ta tìm hiểu thuật toán Hopcroft-Karp [1] tìm cặp ghép cực đại trong đồ thị hai phía. Mình khuyến khích bạn đọc xem lại các khái niệm đã nhắc đến trong bài trước; chúng ta không nhắc lại các khái niệm đó ở đây. Các bạn phải nắm rõ hai khái niệm quan trọng nhất, đường tăng (augmenting path) và hiệu đối xứng (symmetric difference), để tiếp tục đọc bài này. Trong bài này, ta sẽ sử dụng Observation 1 của bài trước nên mình sẽ copy nguyên bản ra đây.

Observation 1: Gọi $M_1, M_2$ là hai cặp ghép của đồ thị $G(V,E)$. Đồ thị con $H(V, M_1\oplus M_2)$ sẽ bao gồm: (1) các đỉnh cô lập (isolated vertices), i.e, các đỉnh không kề với cạnh nào cả, (2) các đường pha và (3) các chu trình pha.

 

Ý tưởng trung tâm của thuật toán Hopcroft-Karp là mỗi lần tìm đường tăng bằng duyệt đồ thị, thay vì tìm một đường tăng, ta tìm một tập các đường tăng rời nhau (vertex-disjoint), kí hiệu là $\mathcal{P}$. Tập đường tăng rời nhau này có tính chất:

  1. Tối đại (maximal): mọi đường tăng khác đều có chung ít nhất một đỉnh với $\mathcal{P}$.
  2. Ngắn nhất: mỗi đường tăng trong $\mathcal{P}$ là một đường tăng có chiều dài ngắn nhất so với tất cả các đường tăng của cặp ghép hiện tại $M$.

Ta gọi $\mathcal{P}$ là một tập đường tăng ngắn nhất rời nhau tối đại (maximally vertex-disjoint shortest augmenting paths), ta gọi tắt là tập đường tăng tối đại. Chú ý $\mathcal{P}$ là tối đại chứ không phải cực đại (maximum). Không dễ để tìm được một tập đường tăng cực đại nhưng tìm tập đường tăng tối đại có thể tìm được trong thời gian $O(m + n)$ mà ta sắp mô tả dưới đây.

Hopcroft-Karp($G(A\cup B, E)$):
    $M \leftarrow \emptyset$
    while there is an augmenting path of $M$
        $\mathcal{P} \leftarrow \{P_1,P_2,\ldots, P_k\}$ a set of maximally short. disj. aug. path
        $M \leftarrow M \oplus P_1 \oplus P_2 \ldots \oplus P_k$
    return $M$

 

Như đã nói ở trên, ta có thể tìm được một tập đường tăng tối đại trong thời gian $O(m+n)$. Tạm thời bỏ qua chi tiết làm sao ta có thể tìm được tập như vậy, ta tập trung vào câu hỏi: thuật toán Hopcroft-Karp cần bao nhiêu lần tăng (bao nhiêu lần lặp trong vòng lặp while).

Số lần lặp

Ta sẽ chứng minh:

Theorem 1: Số lần lặp trong vòng lặp while của thuật toán Hopcroft-Karp là $O(\sqrt{n})$ lần.

 

Bản thân mình cảm thấy con số $O(\sqrt{n})$ rất khó hiểu. Trong phân tích thuật toán, rất ít khi chúng ta gặp con số kiểu này, mà chủ yếu là kiểu đa thức như $O(n), O(n^2), \ldots $ hoăc là logarithm như $O(\log n)$. Để hiểu lịch sử của con số này có lẽ phải truy ngược lại thuật toán blocking-flow áp dụng trong luồng cực đại của Dinitz [3] (mối quan hệ giữa luồng cực đại và cặp ghép trên đồ thị hai phía đã được giải thích ở đây), mà chúng ta không có đủ thời gian để nói đến ở đây. Thay vào đó, mình mô tả một chút ý tưởng ở mức cao trước khi đi vào chứng minh chi tiết.

Gọi $M^*$ là một cặp ghép cực đại. Trong vòng lặp đầu tiên, tập các đường tăng tối đại cũng chính là một cặp ghép tối đại. Cặp ghép này có kích thước ít nhất một nửa kích thước của cặp ghép cực đại $M^*$ (xem bài tập 5 của post trước). Sau vòng lặp thứ hai, ta có thể chứng minh rằng cặp ghép tìm được có kích thước ít nhất $2/3 \cdot |M^*|$ (mình khuyến khích bạn đọc nên thử). Tổng quát hóa lên, sau $\sqrt{n}$ vòng lặp, cặp ghép hiện tại có kích thước ít nhất $\frac{\sqrt{n}}{\sqrt{n} + 1} |M^*|$ (chứng minh tỉ mỉ sẽ được trình bày dưới đây). Như vậy, sau $\sqrt{n}$ lần lặp, ta có:

$|M^*| - |M| \leq \frac{1}{\sqrt{n} + 1} |M^*| \leq \frac{1}{\sqrt{n} + 1} n/2 \leq \sqrt{n} $

Do đó, chỉ cần thêm $\sqrt{n} $ lần tăng nữa (vì mỗi lần tăng kích thước của $M$ tăng lên ít nhất 1 đơn vị) thì ta thu được một cặp ghép cực đại. Như vậy, tổng số lần lặp cần thiết là $2\sqrt{n}$. Sau đây ta sẽ trình bày cách chứng minh hình thức và tổng quát hơn.

Lemma 1: Gọi $M$ là một cặp ghép và $M^*$ là một cặp ghép cực đại. Nếu $|M^*| = |M| + k$ thì đường tăng ngắn nhất của $M$ có chiều dài không quá $\frac{n}{k}-1$.

 
Chứng minh: Theo Observation 1, $M^* \oplus M $ có đúng $k$ đường tăng (của cặp ghép $M$). Các đường này thỏa mãn không có hai đường nào có chung đỉnh. Do đó, đường ngắn nhất có không quá $n/k$ đỉnh, hay nói cách khác, không quá $\frac{n}{k}-1$ cạnh.


Một phiên bản khác mạnh hơn Lemma 1 sẽ được coi như bài tập cho bạn đọc (bài tập 1). Một cách phát biểu khác của Lemma 1 là:

Corollary 1: Nếu đường tăng ngắn nhất có $k$ cạnh thì $|M| \geq |M^*| - \frac{n}{k+1}$.

 
Ý nghĩa của Corollary 1 đó là nếu đường tăng ngắn nhất có chiều dài ít nhất $\sqrt{n}$ thì:

$|M| \geq |M^*| -\sqrt{n} \qquad (1)$

Do đó, chỉ cần tăng thêm $\sqrt{n}$ lần nữa là cặp ghép $M$ sẽ cực đại. Vậy khi nào thì đường tăng ngắn nhất có chiều dài ít nhất $\sqrt{n}$? Nếu ta chứng minh được, sau mỗi lần lặp của thuật toán Hopcroft-Karp, chiều dài đường tăng ngắn nhất tăng lên 1, do đó, sau $\sqrt{n}$ lần tăng thì chiều dài đường tăng ngắn nhất sẽ là $\sqrt{n}$. Như vậy tổng số vòng lặp của thuật toán Hopcroft-Karp chính là $2\sqrt{n}$ như trong phát biểu của Theorem 1.

Lemma 2: Gọi $M$ là một cặp ghép, và $P$ là một đường tăng ngắn nhất của $M$. Gọi $P'$ là một đường tăng của cặp ghép $M\oplus P$. Ta có:

$|P'| \geq |P| + 2|P\cap P'| \qquad (2)$

 
Chứng minh: Nếu $P\cap P' = \emptyset$ thì dễ thấy $(2)$ đúng vì lúc đó $P'$ cũng là đường tăng của $M$ và $P$ ngắn nhất.

Gọi $N = (M \oplus P) \oplus P'$. $N$ là một cặp ghép và $|N| = |M|+2$. Theo Observation 1, $N \oplus M$ sẽ bao gồm 2 đường tăng (của $M$) mà ta gọi là $P_1,P_2$. Do $P$ ngắn nhất, $|P_1|, |P_2| \geq |P|$.

Do $N \oplus M = P\oplus P'$, ta có $|P \oplus P'| = |P_1| + |P_2|$. Theo định nghĩa của hiệu đối xứng (symmetric difference), $|P \oplus P'| = |P| + |P'| - 2 |P\cap P'|$. Từ đó ta suy ra dpcm.


Chứng minh Theorem 1: Như đã thảo luận ở trên, ta chỉ cần chứng minh sau mỗi lần lặp của thuật toán Hopcroft-Karp chiều dài đường tăng ngắn nhất tăng lên 1.

Do $\mathcal{P}$ là tối đại, bất kì đường tăng nào, giả sử $Q$, của cặp ghép $M\oplus P_1 \oplus \ldots \oplus P_k$ cũng phải chứa một cạnh nào đó của $\mathcal{P}$. Chú ý, $|P_1| = |P_2| = \ldots = |P_k|$. Không mất tính tổng quát, ta giả sử $Q \cap P_k \not= \emptyset$. Theo Lemma 2, $Q \geq |P_k| + 2$. Do đó $Q$ > $P_k$ (dpcm).


Tìm bộ đường tăng tối đại trong thời gian $O(n+m)$

Trong phần này ta sẽ tìm hiểu cách tìm một bộ đường tăng tối đại trong thời gian $O(n+m)$. Kết hợp với Theorem 1, ta có:

Theorem 2: Thuật toán Hopcroft-Karp có thời gian $O(m\sqrt{n})$.

 

Một điều đáng chú ý trong giải thuật BipartiteMaximumMatching của bài trước là trong vòng lặp repeat-until, ta không chỉ tìm một đường tăng sau mỗi lần lặp mà một tập đường tăng tối đại (maximal set of augmenting paths), và tập này tìm được bằng thuật toán DFS. Tuy nhiên, trong thuật toán Hopcroft-Karp, ta phải tìm tập đường tăng tối đại ngắn nhất.

Để tìm tập đường tăng này, đầu tiên ta sẽ thực hiện định hướng cạnh đồ thị như bài trước: các cạnh không thuộc cặp ghép được định hướng từ $A$ sang $B$ và các cạnh thuộc cặp ghép được định hướng từ $B$ sang $A$. Tiếp theo, ta thêm một đỉnh ảo $s$, nối đỉnh này với tất cả các cạnh chưa ghép của $A$ bằng các cạnh có hướng. Từ $s$, ta thực hiện BFS để tìm độ dài của đường tăng ngắn nhất. Giả sử đường này có độ dài $k$. Khi thực hiện BFS, ta sẽ gán nhãn mỗi đỉnh $v \in A\cup B$ bằng một số $L[v] = d(s,v)$ chính là độ dài đường đi ngắn nhất từ $s$ tới $v$. Ta có nhận xét:

Observation 2: Các điểm cuối của các đường tăng nằm trong bộ đường tăng tối đại ngắn nhất đều có nhãn $k+1$.

 

Sau khi thực hiện BFS, theo Observation 2, ta chỉ giữ lại các đỉnh có nhãn không quá $k+1$. Lúc này ta có thể thực hiện BFS như trong giải thuật BipartiteMaximumMatching của bài trước để tìm bộ đường tăng tối đại ngắn nhất. Chú ý, khi thực hiện DFS, ta chỉ thăm từ đỉnh có nhãn $i$ tới đỉnh có nhãn $i+1$ mà thôi. Chi tiết giả mã như sau:

Hopcroft-Karp($G(A \cup B, E)$):
    $M \leftarrow \emptyset$
    repeat
        $L[1,\ldots, n] \leftarrow$ FindBFSLevel $(G, M)$
        $k \leftarrow +\infty$             $\ll k$ is the length of the shortest aug. path$\gg$
        for each unmatched $v \in B$
            $k \leftarrow \min(k, L[v])$
        mark every vertex of $G$ unvisited
        for each $u \in A$
            if $u$ is univisited and unmatched
                Augmenting $(G, u, L, M, k)$
    until no augmenting path exists
    return $M$

 

FindBFSLevel($G(A \cup B, E), M$):
    $Q \leftarrow \emptyset$             $\ll Q$ is a queue $\gg$
    mark every vertex of $G$ unvisited
    for each unmatched vertex $u \in A$
        $L[u] \leftarrow 1$
        Enqueue$(Q,u)$             $\ll $ put $u$ to queue $Q \gg$
        mark $u$ visiting.
    while $Q \not= \emptyset$
        $u \leftarrow$ Dequeue$(Q)$
        mark $u$ visited
        if $u \in A$
            for each unvisited $v\in N[u]$
                Enqueue$(Q,v)$
                $L[v] \leftarrow L[u]+1$
                mark $v$ visiting
        else             $\ll u \in B\gg$
            if $M[u]$ is unvisited
                Enqueue$(Q,M[u])$
                mark $M[u]$ visiting
                $L[M[u]] \leftarrow L[u]+1$
    return $L[1,\ldots, n]$

 

Augmenting($G(A \cup B, E), u, L, M, k$):
    mark $u$ visited
    for each $v \in N[u]$             $\ll v \in B \gg$
        if $v$ is unmatched             $\ll$ found an augmenting path $\gg$
            $M[v] \leftarrow u$             $\ll$ augmenting $\gg$
            return True
        if $v$ is unvisited and $L[v] = L[u] + 1$
            mark $v$ visited
            if $M[v]$ unvisited and $L[v]$ < $k$ and Augmenting($G, M[v],L, M,k$)
                $M[v] \leftarrow u$
                return True
    return False

 

Code C:
to-do

Remark: Mặc dù thuật toán Hopcroft-Karp được đề xuất cách đây hơn 40 năm, cho đến tận 2013 Madry [4] mới tìm ra thuật toán thực sự nhanh hơn Hopcroft-Karp khi đồ thị đầu vào đủ thưa. Tuy nhiên, thuật toán của Madry phức tạp hơn thuật toán Hopcroft-Karp rất nhiều.

Tham khảo

[1] J. E. Hopcroft and R. M. Karp. An $n^{5/2}$ algorithm for maximal matchings in bipartite graphs. SIAM Journal on Computing (1973): 225-231.
[2] U. Zwick. Maximum matching in bipartite and non-bipartite graphs. Tel Aviv University, 2009.
[3] E. A. Dinic. Algorithm for Solution of a Problem of Maximum Flow in a Network with Power Estimation. Soviet Math Doklady (1970): 1277-1280.
[4] A. Madry. Navigating central path with electrical flows: From flows to matchings, and back. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2013.

Bài tập

Bài tập 1: Chứng minh rằng Lemma 1 vẫn đúng nếu ta thay $\frac{n}{k}-1$ bằng $\frac{|2M^*|}{k}-1$.

Facebook Comments

Tags: , , , ,

Reply

Your email address will not be published. Required fields are marked *