Pythonでグラフ内の最大クリークの最小サイズを求めるプログラム

問題概要

グラフが与えられたとき、そのグラフに含まれる最大クリークの最小サイズを求める問題を考えます。ここで「クリーク」とは、グラフの頂点部分集合のうち、任意の2つの頂点が必ず隣接している（つまり、すべての頂点ペア間に辺が存在する）ものを指します。

最大クリークを求める問題は多項式時間では解けないことが知られているため（NP困難問題）、小規模なグラフについてノード数とエッジ数が与えられた場合には、工夫したアルゴリズムで最大クリークのサイズを導き出す必要があります。

例えば、入力が nodes = 4、edges = 4 の場合、出力は 2 となります。このグラフでは、クリークの最大サイズは 2 です。

解決のアプローチ

この問題は、二分探索と補助関数を組み合わせることで効率的に解くことができます。補助関数 helper() は、x 個の頂点をできるだけ均等に y 個のグループへ分割したときの辺の総数を計算します。この値と与えられたエッジ数を比較しながら二分探索を行うことで、条件を満たす最小のサイズを絞り込んでいきます。

アルゴリズムの手順

• 関数 helper(x, y) を定義します。
  • ga := x mod y
  • gb := y - ga
  • sa := (x ÷ y) の商 + 1
  • sb := (x ÷ y) の商
  • ga * gb * sa * sb + ga * (ga - 1) * sa * sa / 2 + gb * (gb - 1) * sb * sb / 2 を返す
• i := 1、j := nodes + 1 で初期化する
• i + 1 < j の間、以下を繰り返す：
  • p := i + ⌊(j - i) / 2⌋
  • k := helper(nodes, p)
  • k < edges の場合は i := p、そうでなければ j := p
• j を返す

実装例

以下のPythonコードを見ると、処理の流れがより理解しやすくなります。

import math

def helper(x, y):
    ga = x % y
    gb = y - ga
    sa = x // y + 1
    sb = x // y
    return ga * gb * sa * sb + ga * (ga - 1) * sa * sa // 2 + gb * (gb - 1) * sb * sb // 2

def solve(nodes, edges):
    i = 1
    j = nodes + 1
    while i + 1 < j:
        p = i + (j - i) // 2
        k = helper(nodes, p)
        if k < edges:
            i = p
        else:
            j = p
    return j

print(solve(4, 4))

入力

4, 4

出力

2

まとめ

このプログラムでは、頂点を均等に分割した場合の辺数を計算する helper() 関数を基準に、二分探索で境界を狭めていくことで、最大クリークの最小サイズを効率よく求めています。全てのグラフ構造を列挙する必要がないため、ノード数やエッジ数が増えても比較的高速に答えを得られるのが大きな特徴です。