[演算法] A Progressive Network-Flow-Based Heuristic for Finding Minimum Cost Clique Partition

 minimum clique partition (MCP) 探討的是如何將一個無向圖 (undirected graph) 分成最少數量的 clique。若是無向圖上的邊具有權重的話，並且最少數量的 clique partition 有好幾組的話，則此問題要找的是所有 clique 上的所有邊的權重總和要是最小的那一組。因為這是個 NP-hard 的問題，因此若非一定要找出最佳解 (optimum solution)，一般將採用 heuristic 的方式找出一組次佳解 (optimal solution)。這邊要介紹的是基於 progressive network-flow 的方法找出一組解

關於 clique 的定義與介紹可以參考這篇文章，這邊就不多贅述。基於 clique 的是個完整圖 (complete graph)，一般是用來表達一個集合中的某個子集合具有非常強烈的交互作用，比方說具有極高的相似度 (如果把一個人都用一個點來表示，點之間的邊表示兩個人彼此認識，則此時 clique 代表那群人彼此都互相認識，那代表他們有非常強烈的共通性)、連通性強烈 (像是用一個無向圖來表示所有城市中的道路連通關係，屬於同一個 clique 所有城市彼此間都有道路連接)，因此 minimum clique partition 想知道的是這個無向圖中至少有幾個關係非常緊密的群組。而如果我們用一個權重來表示任兩點間關係的緊密度，並且數字越小表示關係越緊密的話，我們當然希望最後分成數個群組後，每個群組間的關係都要非常的緊密，這樣的結果才有參考價值。

所有這類的問題，如果要想一個最簡單的 heuristic，那絕對是先用 greedy，方法如下：
1. 從無向圖 G 中找出一組權重最小的 maximal clique C
2. 把 C 從 G 中移除，回到步驟 1，直到 G 中再也沒有任何的點

舉個例子，以下圖為例：

這是一個具有 9 個點的無向圖，其中黑色 / 黃色 / 綠色的邊的權重分別是 1 / 2 / 3。

依照這個 greedy 的方法，最一開始會先抓出 (1, 2, 4, 5) 這 4 個點組成的 clique (當然有很多種可能的結果，但不管哪一種可能都是 4 個點的 clique，並且權重也都一樣)，這個 clique 的權重是 11；下一個會挑的 clique 可能就輪到 (7, 8, 9) 權重為 5，最後則分別是 (3) 以及 (6)，權重都 0，因此這組 partition 的結果是拆成 4 組 clique：(1, 2, 4, 5), (7, 8, 9), (3), (6)，總權重為 16。

通常 greedy 類型的 heuristic優點就在於簡單、快速，但缺點很明顯的就是很難保證結果會有多好，而且從這個例子可以發現就算是挑 maximal clique 也都有很多種可能的結果，因此結果的變異性非常大。因此這邊要介紹另一種 heuristic，他的收斂性與變異性都比 greedy based 的好。

整體演算法的概念如下：

1.  首先從 G 中先挑出一組 maximal independent set (MIS)，因為 MIS 中的任兩個點都不可能屬於同一個 clique，因此我們可以很放心的為 MIS 中的每個點都變成一個 clique，並且把這組 MIS 從 G 中移除。
2.  再從 G 中挑出一組 MIS，依照上一步同樣的概念，我們可以確保他們必然屬於不同的 clique，但這時候因為在上一步我們已經有創好幾個 clique 了，所以我們優先檢查這些點是否可以被併入先前已經存在的 clique，同時確保合併成更大的 clique 後，所有 clique 的權重增加的量是最少的。之後再將這組 MIS 從 G 中移除。
3. 重覆步驟 2 直到 G 沒有任何的點為止。

我們用相同的圖來解釋這個新的 heuristic 吧：

首先第一步我們可以找出來的 MIS 是 (1, 6, 8)，則我們讓 1, 6, 8 分別變成 3 個 clique (Iteration 1)。接下來假設找出來的 MIS 是 2, 3, 9，經過比對後我們可以發現 3 可以跟 (1) 組成更大的 clique 變成 (1, 3)，同理 9 可以跟 (6) 或 (8) 組，這邊假設最後選了 (8) 變成 (8, 9)。可以注意到 2 沒辦法跟 (1), (6) 或 (8) 組成 clique，所以我們讓 2 變成新的 clique (Iteration 2)。接下來重覆同樣的步驟，結果分別列在 Iteration 3 跟 4，最後我們得到了這樣的 clique partition 結果：(1, 3, 7), (4, 6), (8, 9), (2, 5) 總計分成 4 個 clique，權重為 9。

這個方法的特點在於因為每次都是找 MIS，因此我們可以確保他們必然要落在不同的 clique，從而降低 greedy 的方法中的不確定性，因此可以得到比較好、也比較穩定的結果。

另一方面，每次找出一組新的 MIS 後，因為他們必然要歸屬不同的 clique，並且現存的所有 clique 也絕對不可能彼此合併成更大的 clique，因此如果我們把 MIS 中的每個點跟現有的 clique 都變成一個點、兩個點之間建一條邊來表示相對應的 MIS 中的點跟 clique 可以合併成更大的 clique，則這個新建的 graph 必然會是一個 bipartite graph。因此這個階段如果要讓 MIS 中最多的點可以跟現存的 clique 合併的話，相當於在 bipartite graph 找一組 maximum matching。

進一步擴充這個概念的話，如果我們讓邊上附加上一個權重，用以代表合併後會讓結果增加多少權重，則這個問題會進一步的變成要找一組 min-cost max bipartite matching。這個問題可以利用匈牙利演算法 (Hungarian method) 或者是轉成 min cost max s-t flow problem 來解。

以上就是這個 heuristic 的概念，以下列出兩篇有用到這個概念的 paper：
[1] Track assignment: A Desirable Intermediate Step Between Global Routing And Detailed Routing
[2] Progressive Network-Flow Based Power-Aware Broadcast Addressing for Pin-Constrained Digital Microfluidic Biochips