最大クリーク問題 (maximum clique problem)

概要

グラフ上の最大クリークを求める。

Bron-Kerbosch Algorithm はバックトラックでグラフ上の極大クリーク(maximal clique)を全て列挙する。

計算量

頂点数を \(N\) とする時、 \(O(3^{N/3})\)

特に疎グラフに関しては \(O(Nd 3^{d/3})\) (\(d\) は グラフの degeneracy)

実装

グラフ上の最大クリークを一つ返す実装例

def maximum_clique(N, G):
    def dfs(V, P, X):
        if not P and not X:
            # V is a maximal clique
            return V
        u = next(iter(X or P)) # a pivot vertex
        r = set()
        for v in P - G[u]:
            r0 = dfs(V | {v}, P & G[v], X & G[v])
            if len(r) < len(r0):
                r = r0
            P.remove(v)
            X.add(v)
        return r

    # sort vertices in a degeneracy ordering
    *I, = range(N)
    I.sort(key = lambda x: len(G[x]), reverse=1)

    ans = set()
    P = set(range(N))
    X = set()
    for v in I:
        res = dfs({v}, P & G[v], X & G[v])
        if len(ans) < len(res):
            ans = res
        P.remove(v)
        X.add(v)
    return ans

# example
G = [set() for i in range(6)]
G[0] |= {1, 2, 3, 4}
G[1] |= {0, 2, 5}
G[2] |= {0, 1, 3, 4}
G[3] |= {0, 2, 4}
G[4] |= {0, 2, 3}
G[5] |= {1}
print(maximum_clique(6, G))
# => "{0, 2, 3, 4}"

Verified

  • CodeChef: "CodeChef July Challenge 2018: Tom and Jerry": source (PyPy2, 2.72sec)

  • AOJ: "2306 - Rabbit Party": source (Python3, 0.35sec)

  • AOJ: "2948 - Great Strategy for Bring Up Grade": source (Python3, 6.65sec)

参考

戻る