最大クリーク問題（最大安定集合問題）とその周辺
最大クリーク問題と最大安定集合問題
最大安定集合問題(maximum stable set problem)は，以下のように定義される問題である．
点数 $n$ の無向グラフ $G=(V,E)$ が与えられたとき，点の部分集合 $S (\subseteq V)$ は， すべての $S$ 内の点の間に枝がないとき安定集合（stable set）とよばれる． 最大安定集合問題とは，集合に含まれる要素数（位数）$|S|$ が最大になる安定集合 $S$ を求める問題である.
この問題のグラフの補グラフ（枝の有無を反転させたグラフ）を考えると， 以下に定義される最大クリーク問題（maximum clique problem）になる．
無向グラフ $G=(V,E)$ が与えられたとき，点の部分集合 $C (\subseteq V)$は， $C$ によって導かれた誘導部分グラフが完全グラフ（complete graph）になるときクリーク（clique）とよばれる （完全グラフとは，すべての点の間に枝があるグラフである）． 最大クリーク問題とは，位数 $|C|$ が最大になるクリーク $C$ を求める問題である．
これらの2つの問題は（お互いに簡単な変換によって帰着されるという意味で）同値である．
点 $i$ が安定集合 $S$ に含まれるとき $1$，それ以外のとき $0$ の $0$-$1$ 変数を用いると， 最大安定集合問題は，以下のように定式化できる．
$$ \begin{array}{l l l} maximize & \sum_{i \in V} x_i & \\ s.t. & x_i +x_j \leq 1 & \forall (i,j) \in E \\ & x_i \in \{0,1\} & \forall i \in V \end{array} $$G = nx.fast_gnp_random_graph(100, 0.5)
count = 0
for i in nx.find_cliques(G):
count += 1
count
count = 0
for i in nx.find_cliques(G):
print(i)
count += 1
if count >= 10:
break
n = 100
random.seed(1)
pos = {i: (random.random(), random.random()) for i in range(n)}
G = nx.random_geometric_graph(n, 0.3, pos=pos, seed=1)
from networkx.algorithms import approximation
S = approximation.max_clique(G)
print(len(S))
nx.draw(G, pos=pos, node_size=100)
nx.draw(
G,
pos=pos,
nodelist=list(S),
edgelist=[(i, j) for i in S for j in S if i < j],
node_color="red",
edge_color="blue",
)
Gbar = nx.complement(G)
nodes, edges = Gbar.nodes(), Gbar.edges()
adj = gts.adjacent(nodes, edges)
sol = construct(nodes, adj)
max_iter = 10000
tabulen = len(nodes) / 10
bestsol, bestcard = tabu_search(nodes, adj, sol, max_iter, tabulen, report=None)
nx.draw(G, pos=pos, node_size=100)
nx.draw(
G,
pos=pos,
nodelist=list(S),
edgelist=[(i, j) for i in S for j in S if i < j],
node_color="red",
edge_color="blue",
)
print(len(bestsol))
sol = construct(nodes, adj)
max_iter = 10000
tabulen = len(nodes) / 10
bestsol, bestcard = ts_intens_divers(nodes, adj, sol, max_iter, tabulen, report=False)
nx.draw(G, pos=pos, node_size=100)
nx.draw(
G,
pos=pos,
nodelist=list(S),
edgelist=[(i, j) for i in S for j in S if i < j],
node_color="red",
edge_color="blue",
)
print(len(bestsol))
sol = construct(nodes, adj)
max_iterations = 10000
tabulength = len(nodes) / 10
sol, rmn, card = hybrid(nodes, adj, max_iterations, tabulength, False)
nx.draw(G, pos=pos, node_size=100)
nx.draw(
G,
pos=pos,
nodelist=list(S),
edgelist=[(i, j) for i in S for j in S if i < j],
node_color="red",
edge_color="blue",
)
print(len(sol))
model = Model()
x = {}
nodes = {}
for i, c in enumerate(nx.find_cliques(G)):
x[i] = model.addVar(vtype="B", name=f"x[{i}]")
nodes[i] = c
cliques = {} # 点iを含んでいるクリークの集合
for i in range(n):
cliques[i] = []
for c in nodes:
for i in nodes[c]:
cliques[i].append(c)
for i in range(n):
model.addConstr(quicksum(x[c] for c in cliques[i]) >= 1)
model.setObjective(quicksum(x[c] for c in x), GRB.MINIMIZE)
model.optimize()
lhs = np.zeros(n)
for c in x:
if x[c].X > 0.001:
for i in nodes[c]:
lhs[i] += 1
edges = []
for c in x:
if x[c].X > 0.001:
# print(nodes[c])
for i in nodes[c]:
for j in nodes[c]:
if i != j:
edges.append((i, j))
plt.figure()
nx.draw(G, pos=pos, with_labels=False, node_size=10, edge_color="blue")
nx.draw_networkx_edges(G, pos=pos, edgelist=edges, edge_color="orange", width=2)
plt.show()
