最小頂点被覆問題
無向グラフ $G=(V,E)$ の頂点被覆とは、 $S\subseteq V$ という部分集合であり、 任意の辺 $(u,v)\in E$ に対して、 その端点の少なくとも一方が $S$ に属するものである。 最小頂点被覆問題とは、 最小の要素数を持つ頂点被覆を見つけることである。
この問題はQUBO式として定式化できる。 $n$頂点グラフ $G=(V,E)$ の頂点に $0,1,\ldots,n−1$ のラベルを付与し、 $n$ 個の二値変数 $x_0,x_1,\ldots, x_{n-1}$ を導入する。ここで $x_i=1$ となるのは、頂点 $i$ が選択されている（すなわち $i\in S$）場合に限る。
以下のペナルティ項を用いる。これは全ての辺がカバーされた場合にのみ0となる：
\[\begin{aligned} \text{制約} &= \sum_{(i,j)\in E} (1-x_i)(1-x_j) \end{aligned}\]辺 $(i,j)$ について、積 $(1-x_i)(1-x_j)$ が 1 となるのは、両端点が選択されていない場合（つまり辺が未カバーの場合）のみである。したがって、この和は未カバーの辺の数を数える。
目的関数は選択された頂点の数を最小化することである：
\[\begin{aligned} \text{目的関数} &= \sum_{i=0}^{n-1}x_i \end{aligned}\]最終的に、QUBO表現$f$は以下のように与えられる：
\[\begin{aligned} f &= \text{目的関数} + 2\times \text{制約関数} \end{aligned}\]ペナルティ係数2は、目的関数の最小化よりも制約条件の充足を優先させるために用いられる。
最小頂点被覆問題のためのQUBO++プログラム
以下のQUBO++プログラムは、$N=16$の頂点を持つグラフの最小頂点被覆問題を解く：
#include "qbpp.hpp"
#include "qbpp_exhaustive_solver.hpp"
#include "qbpp_graph.hpp"
int main() {
const size_t N = 16;
std::vector<std::pair<size_t, size_t>> edges = {
{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6},
{3, 7}, {3, 13}, {4, 6}, {4, 7}, {5, 8}, {6, 8},
{6, 14}, {7, 14}, {8, 9}, {9, 10}, {9, 12}, {10, 11},
{10, 12}, {11, 13}, {12, 14}, {13, 15}, {14, 15}};
auto x = qbpp::var("x", N);
auto objective = qbpp::sum(x);
auto constraint = qbpp::toExpr(0);
for (const auto& e : edges) {
constraint += (1 - x[e.first]) * (1 - x[e.second]);
}
auto f = objective + constraint * 2;
f.simplify_as_binary();
auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(f);
auto sol = solver.search();
std::cout << "objective = " << objective(sol) << std::endl;
std::cout << "constraint = " << constraint(sol) << std::endl;
qbpp::graph::GraphDrawer graph;
for (size_t i = 0; i < N; ++i) {
graph.add_node(qbpp::graph::Node(i).color(sol(x[i])));
}
for (const auto& e : edges) {
graph.add_edge(qbpp::graph::Edge(e.first, e.second));
}
graph.write("vertexcover.svg");
}
このプログラムでは、 objective, constraint、および f は上記の定式化に従って構築される。
最適解探索には網羅的ソルバーが適用される。 f を走査し最適解を検索する。
得られた解 sol は可視化され、 vertexcover.svg.
このプログラムは以下の出力を表示する：
objective = 9
constraint = 0
目的関数値9、制約値0の最適解が得られました。 選択された頂点を強調した結果画像は以下に示します：
