続: 最大クリーク問題 - 高温処理済みコースケ

なんかいろいろやってこんな形に落ち着いた。

簡単にいうとまず適当にソートして、有向グラフに変換してDPする。
dp[j][c]はj以下の頂点を使用したjを含むサイズcのクリークの文字列表現の配列。
後続の頂点iからはこのクリークの頂点にすべて辺があれば、サイズc+1のクリークなのでdp[i][c+1]に追加する。
このクリークの頂点にすべて辺があればの部分は、rubyなので配列を&した、他の言語だとbitsetみたいなライブラリで行うほうがよいと思う。

belongs_max_cliqueは前回のソースを引き継いでいるので現在は適当ではないかもしれないけど、ある頂点vに隣接する誘導グラフから、最大クリークサイズをだす場合はbelongs_max_clique(G[v]) + 1とすればよいようになっている。

#!/usr/bin/env ruby

V, m = gets.split.map(&:to_i) # read Graph Infomation
G = {} 

# Initialize Graph
V.times {|v| G[v] = []}
m.times do 
  from, to = gets.split.map(&:to_i).sort
  G[from] << to
  G[to] << from
end


def belongs_max_clique(node = V.times.to_a, limit =  V)
  subgraph = {}
  node.sort!
  node.each_index{|i| subgraph[i] = [] }
  node.each_with_index do |u, i|
    i.times do |j|
      w = node[j]
      subgraph[i] << j if G[u].include?(w)
    end
  end
  
  dp = Array.new(node.size + 1){ Array.new(limit + 1){ [] } }
  node.each_index{|i| dp[i][1] << i.to_s }
  max_clique_size = (1 ... limit).find do |c|
    found_clique = false
    node.each_index do |i|
      subgraph[i].each do |j|
        dp[j][c].each do |clq|
          clique = clq.split.map(&:to_i)
          shared = clique & subgraph[i]
          if shared == clique
            clique << i
            dp[i][c + 1] << clique.join(' ')
            dp[node.size][c + 1] << clique.join(' ')
            found_clique = true
          end
        end
      end
    end
    !found_clique
  end
  max_clique_size || limit
end

puts belongs_max_clique

前回指摘をもらったグラフだとDPした結果は以下のようになる

[[], ["0"], [], [], [], [], [], [], []], 
[[], ["1"], ["0 1"], [], [], [], [], [], []], 
[[], ["2"], ["0 2", "1 2"], ["0 1 2"], [], [], [], [], []], 
[[], ["3"], ["0 3", "1 3", "2 3"], ["0 1 3", "0 2 3", "1 2 3"], ["0 1 2 3"], [], [], [], []], 
[[], ["4"], ["0 4"], [], [], [], [], [], []], 
[[], ["5"], ["0 5", "4 5"], ["0 4 5"], [], [], [], [], []], 
[[], ["6"], ["0 6", "5 6"], ["0 5 6"], [], [], [], [], []], 
[[], ["7"], ["0 7", "4 7", "6 7"], ["0 4 7", "0 6 7"], [], [], [], [], []],

入力はこんな感じ

dp[node.size][c]は別になくてもよいけど、サイズcのクリーク( c >= 2)の全列挙用につくっている。

こんな感じになる。

[],
["0 1", "0 2", "1 2", "0 3", "1 3", "2 3", "0 4", "0 5", "4 5", "0 6", "5 6", "0 7", "4 7", "6 7"],
["0 1 2", "0 1 3", "0 2 3", "1 2 3", "0 4 5", "0 5 6", "0 4 7", "0 6 7"], 
["0 1 2 3"]

追記: コメントに計算量のことを書いて質問をいただきました。現在のコードがc^2 * v * eかと言われれば、ご指摘の通りたぶん違うんじゃないかとおもってきました。ただ自分的にはc^2 * v * eにまでおそらく落とせると思っているのでそこまで計算量を落としたアルゴリズムを作りたいと思っています。

メモ: cのループをnodeのループの中に入れて、サイズcのクリークの全列挙をやめると計算量は落ちるな。でもやはりサイズcのクリーク数に依存しそうだから、サイズcのクリークの個数に対して、cかc^2になりそうかな。計算量は落ち着かないけど、これならできそう。