最小支配集合問題
無向グラフ $G=(V,E)$ の支配集合とは、頂点集合 $V$ の部分集合 $S\subseteq V$ で、任意の頂点 $u\in V$ が $S$ に属するか、$S$ の頂点に隣接するものである。
$u\in V$ の隣接頂点集合を $N(u)={v\in V\mid (u,v)\in E}$ と定義し、 $u$ の閉近傍を $N[u]={u}\cup N(u)$ と定義する。 このとき、$S$ が支配集合であるのは、次の条件が成立するときとだけである：
\[\begin{aligned} V = \bigcup_{u\in V} N[u]. \end{aligned}\]最小支配集合問題とは、最小の要素数を持つ支配集合を見つけることを目的とする。 $0,1,\ldots,n−1$ でラベル付けされた $n$ ノードのグラフ $G=(V,E)$ 上で、$n$ 個の二値変数 $x_0, x_1, \ldots, x_{n-1}$ を導入する。ここで $x_i=1$ となるのは、ノード $i$ が支配集合 $S$ に含まれる場合に限る。
二つの定式化を示す：
- HUBO表現：式には高次項が含まれる可能性がある。
- QUBO表現：式は二次式であるが、補助変数が用いられる。
最小支配集合問題のHUBO形式化
各ノード $i\in V$ について、以下の条件が全てのノード $i$ に満たされる必要がある：
- $j\in N[i]$ のいずれかにおいて $x_j=1$ （すなわち、ノード $i$ が支配されている）。 したがって、制約を次のように定義する：
ノード $i$ に対する項の次数 $∣N[i]∣$ であるため、この制約は二次式ではない可能性がある。
目的は選択されるノードの数を最小化することである：
\[\begin{aligned} \text{制約条件} = \sum_{i=0}^{n-1} x_i \end{aligned}\]最終的に、関数 $f$ は次のように表される：
\[\begin{aligned} f &= \text{目的関数} + (n+1)\times \text{制約条件} \end{aligned}\]ペナルティ係数 $n+1$ は、目的関数の最小化よりも支配集合制約の充足を優先させる安全な選択である。
HUBO定式化のためのQUBO++プログラム
以下のQUBO++プログラムは、$N=16$ノードのグラフに対する解を求める：
#include "qbpp.hpp"
#include "qbpp_easy_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}};
std::vector<std::vector<size_t>> adj(N);
for (const auto& e : edges) {
adj[e.first].push_back(e.second);
adj[e.second].push_back(e.first);
}
auto x = qbpp::var("x", N);
auto objective = qbpp::sum(x);
auto constraint = qbpp::toExpr(0);
for (size_t i = 0; i < N; ++i) {
auto t = (1 - x[i]);
for (size_t j : adj[i]) {
t *= (1 - x[j]);
}
constraint += t;
}
auto f = objective + (N + 1) * constraint;
f.simplify_as_binary();
auto solver = qbpp::easy_solver::EasySolver(f);
solver.time_limit(1.0);
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("dominatingset.svg");
}
このプログラムはまず隣接リストを構築する adj を構築する edgesから隣接リストを構築する。各隣接リストは adj[i] 頂点の隣接頂点を格納します iの隣接頂点を格納します。
次に constraint, objectiveを構築し、 f HUBO形式に従って
イージーソルバーを適用し f を解くためにイージーソルバーを適用する solを得る。
の値は objective と constraint solの値が出力され、結果のグラフは dominatingset.svgに保存され、選択された頂点が強調表示される。
このプログラムは以下の出力を生成します:
objective = 5
constraint = 0
画像ファイルには以下の画像が保存されます:
QUBO定式化とQUBO++プログラム
ノード $i$ は、$N[i]\cap S$ が空でない場合に支配される。 二値変数 $x_i$ を用いると、この条件は次の不等式に等価である:
\[\begin{aligned} \sum_{j\in N[i]}x_j &\geq 1 \end{aligned}\]QUBO++表記では、支配集合制約をペナルティ式の和として表現できる:
\[\begin{aligned} \text{制約} &= \sum_{i=0}^{n-1} \bigl(\sum_{j\in N[i]}x_j \geq 1\bigr) \end{aligned}\]目的関数とfは、QUBO形式と同様の方法で定義できる。
上記の制約は、以下の通りQUBO++プログラムとして記述できる:
auto constraint = qbpp::toExpr(0);
for (size_t i = 0; i < N; ++i) {
auto t = qbpp::toExpr(x[i]);
for (size_t j : adj[i]) {
t += x[j];
}
constraint += 1 <= t <= +qbpp::inf;
}
このコードでは、 t は式
を格納し、範囲演算子は以下のペナルティ式を生成します：
\[1\leq \sum_{j\in N[i]}x_j \leq +\infty,\]この式は、不等式が満たされる場合にのみ最小値0を取る。
を最小化することで fを最小化することで、プログラムは最小支配集合を見つける。