最大クリーク問題

http://poj.org/problem?id=3692

を解いていて、「最大クリーク問題」という問題について知った。

　与えられたグラフの部分グラフのうち完全グラフとなるものをクリーク（clique）と呼ぶ。節点数が最大となるクリークを求める問題を「最大クリーク問題」という。この問題はNP完全らしい。

　完全グラフの補グラフは、null graph（枝集合が空集合であるグラフ）であるので、あるグラフの最大クリークを求めることと、その補グラフの最大独立集合を求めることは同値である。

　二部グラフにおいては最小点カバーと最大マッチングが一致すること、および、一般のグラフにおいて最小点カバーと最大独立集合の和が節点数と一致することから、対象の補グラフが二部グラフである場合には最大クリークを簡単に求めることができる。

　”クリーク”という言葉は、社会学から生まれたらしい。ソーシャルグラフの中からお互いが全員知り合いであるような最大集合の大きさを求めたいというのが研究のはじまり。まさに、PKUの問題もこれと同様の問題。実際のソーシャルグラフの補グラフは必ずしも二部グラフになるとは限らないため、さまざまな近似アルゴリズムが研究されているらしい。

　PKUの問題の解答例を載せておきます。

view plainprint?

1. int n;  
2. bool edge[400][400];  
3. bool used[400];  
4. int pr[400];  
5.   
6. bool match(int s) {  
7.     used[s] = true;  
8.     REP(i, n) {  
9.         if (!edge[s][i]) continue;  
10.         if (pr[i] == -1 || (!used[pr[i]] && match(pr[i]))) {  
11.             pr[s] = i;  
12.             pr[i] = s;  
13.             return true;  
14.         }  
15.     }  
16.   
17.     return false;  
18. }  
19.   
20. int main() {  
21.     int b, g, m;  
22.   
23.     int t = 0;  
24.     while (cin >> b >> g >> m) {  
25.         if (!b && !g && !m) break;  
26.   
27.         int x, y;  
28.         n = b + g;  
29.         REP(i, n) REP(j, n) edge[i][j] = 1;  
30.         REP(i, b) REP(j, b) edge[i][j] = 0;  
31.         REP(i, g) REP(j, g) edge[i+b][j+b] = 0;  
32.   
33.         REP(i, m) {  
34.             cin >> x >> y;  
35.             --x, --y;  
36.             edge[x][y+b] = edge[y+b][x] = 0;  
37.         }  
38.   
39.         int ret = n;  
40.         memset(pr, -1, sizeof(pr));  
41.         REP(i, n) {  
42.             if (pr[i] == -1) {  
43.                 memset(used, 0, sizeof(used));  
44.                 if (match(i)) --ret;  
45.             }  
46.         }  
47.   
48.         printf("Case %d: %d\n", ++t, ret);  
49.     }  
50.   
51.     return 0;  
52. }  

int n;
bool edge[400][400];
bool used[400];
int pr[400];

bool match(int s) {
    used[s] = true;
    REP(i, n) {
        if (!edge[s][i]) continue;
        if (pr[i] == -1 || (!used[pr[i]] && match(pr[i]))) {
            pr[s] = i;
            pr[i] = s;
            return true;
        }
    }

    return false;
}

int main() {
    int b, g, m;

    int t = 0;
    while (cin >> b >> g >> m) {
        if (!b && !g && !m) break;

        int x, y;
        n = b + g;
        REP(i, n) REP(j, n) edge[i][j] = 1;
        REP(i, b) REP(j, b) edge[i][j] = 0;
        REP(i, g) REP(j, g) edge[i+b][j+b] = 0;

        REP(i, m) {
            cin >> x >> y;
            --x, --y;
            edge[x][y+b] = edge[y+b][x] = 0;
        }

        int ret = n;
        memset(pr, -1, sizeof(pr));
        REP(i, n) {
            if (pr[i] == -1) {
                memset(used, 0, sizeof(used));
                if (match(i)) --ret;
            }
        }

        printf("Case %d: %d\n", ++t, ret);
    }

    return 0;
}

参考：
1. simezi_tanの日記
2. Clique problem - wikipedia