頂点被覆問題

頂点被覆問題#

ここではJijZeptSolverとJijModelingを用いて、頂点被覆問題を解く方法を説明します。この問題は、Lucas, 2014, "Ising formulations of many NP problems" 4.3. Vertex Coverでも触れられています。

頂点被覆問題とは#

頂点被覆問題とは、無向グラフ \(G=(V, E)\) が与えられたとき、そのグラフの辺集合 \(E\) を被覆するような最小の集合 \(V' \subseteq V\) を求める問題です。ここで、頂点の集合 \(V'\) が辺集合 \(E\) を被覆するとは、各辺 \(e \in E\) について、\(e\) の端点の少なくとも片方が \(V'\) の要素になっていることを指します。

例題として、次のような無向グラフを考えましょう。

このグラフは頂点として \(A, B, C, D, E, F\) を持ち、これらの頂点を結ぶ辺が7本あります。

ここで、頂点の集合 \(V' := \{B, C, D\}\) を考えると、この集合は辺集合を被覆しています。なぜなら、

辺 \((A, B)\) については、\(B \in V'\)
辺 \((A, C)\) については、\(C \in V'\)
辺 \((B, C)\) については、\(B \in V'\)
辺 \((B, D)\) については、\(B \in V'\)
辺 \((C, E)\) については、\(C \in V'\)
辺 \((D, E)\) については、\(D \in V'\)
辺 \((D, F)\) については、\(D \in V'\)

となっているからです。

数理モデル#

まず、頂点\(v\)が色付けされたとき1、そうでないとき0となるようなバイナリ変数\(x_v\)を導入します。

制約: 各辺は少なくとも1つの色付けされた頂点を持つ#

各辺\((uv)\)において、頂点\(u\)または頂点\(v\)、あるいは両方の頂点を被覆する必要があります。

\[ \quad \sum_{(u,v) \in E} (1-x_u)(1-x_v) = 0. \]

目的関数: 頂点被覆の数を最小化する#

これは次のように解釈することができます。

\[ \quad \min \sum_v x_v. \]

JijModelingによる定式化#

次に、JijModelingを用いて上述の数式を実装してみましょう。最初に、数理モデルを記述するのに必要な変数を定義しましょう。 (グラフ分割問題を参照)

import jijmodeling as jm

problem = jm.Problem('Vertex Cover')

V = problem.Natural('V')
E = problem.Graph('E', dtype=V)
x = problem.BinaryVar('x', shape=(V,))

制約と目的関数#

制約と目的関数を、次のように実装しましょう。

problem += jm.sum(V, lambda v: x[v])
problem += problem.Constraint('color', jm.sum(E, lambda e: (1-x[e[0]])*(1-x[e[1]])) == 0)

Jupyter Notebook上で次のように入力することで、実装された数式を確認することができます。

problem

\[\begin{array}{rl} \text{Problem}\colon &\text{Vertex Cover}\\\displaystyle \min &\displaystyle \sum _{v=0}^{V-1}{{x}_{v}}\\&\\\text{s.t.}&\\&\begin{aligned} \text{color}&\quad \displaystyle \sum _{e\in E}{\left(1-{x}_{{e}_{0}}\right)\cdot \left(1-{x}_{{e}_{1}}\right)}=0\end{aligned} \\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[V;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}E&\in \mathop{\mathrm{Array}}\left[(-);V\times V\right]&\quad &1\text{-dimensional array of placeholders with elements in }V\times V\\V&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\end{array} \]

インスタンスの準備#

Networkxを用いてグラフを準備しましょう。

import networkx as nx

# set the number of vertices
inst_V = 12
# create a random graph
inst_G = nx.gnp_random_graph(inst_V, 0.4)
# get information of edges
inst_E = [list(edge) for edge in inst_G.edges]
instance_data = {'V': inst_V, 'E': inst_E}

このグラフを可視化すると、次のようになります。

import matplotlib.pyplot as plt

nx.draw_networkx(inst_G, with_labels=True)
plt.show()

../_images/afdbd681e7df24e169a7504581b7257aa071c7c561284a93bd7dd16bf3f45951.png

JijZeptSolverで解く#

jijzept_solverを用いて、この問題を解きましょう。

import jijzept_solver

instance = problem.eval(instance_data)
solution = jijzept_solver.solve(instance, solve_limit_sec=1.0)

解の可視化#

最後に、得られた解を可視化してみましょう。

import matplotlib.pyplot as plt
import numpy as np

# get the indices of x == 1
df = solution.decision_variables_df
x_indices = np.ravel(df[df["value"]==1]["subscripts"].to_list())
# set color list for visualization
cmap = plt.get_cmap("tab10")
# initialize vertex color list
node_colors = [cmap(0)] * instance_data["V"]
# set vertex color list
for i in x_indices:
    node_colors[i] = cmap(1)
# draw the graph
nx.draw_networkx(inst_G, node_color=node_colors, with_labels=True)
plt.show()

../_images/19544376b70e509b73c35ef52f603b1e8b17a99a5976be4582ef743854597640.png

上図からわかるように、制約の満たされている実行可能解の頂点被覆を示すことができました。

頂点被覆問題

目次

頂点被覆問題#