3 彩色可能頂点削除問題
無向グラフ $G=(V,E)$ が与えられたとき、3 彩色可能頂点削除問題は、できるだけ少ないノードを削除して、残りのグラフを 3 色で彩色できるようにする問題です。 グラフがもともと 3 色で彩色できれば、削除するノードは 0 個です。 削除するノードの最小数は、グラフが 3 色の彩色からどれだけ離れているかを表します。
グラフ彩色問題の 16 ノードのグラフは、3 色では彩色できません。 このページでは、まずこのグラフで削除するノードの最小数を求めます。 次に、アメリカ本土の 48 州の地図で、何州を除けば残りの州を 3 色で塗り分けられるかを求めます。
動画では、アメリカ本土の 48 州で除く州の最小数を求め、除く 2 州の全 24 組と、その理由を説明します。動画のプログラムと章ごとの説明は動画：アメリカ 48 州を 3 色で塗り分けるのページにあります。
定式化
$V=\lbrace 0,1,\ldots ,n−1\rbrace$ とし、3 つの色を $0, 1, 2$ とします。 $n\times 3$ のバイナリ変数行列 $X=(x_{i,j})$ を導入し、$x_{i,j}=1$ はノード $i$ を色 $j$ で塗ることを表します。 行がすべて 0 のノードは色を塗らないノードで、これが削除するノードです。
色は高々 1 つ
各ノードは、1 つの色で塗るか、塗らないかのどちらかです。 そのため、各行の 1 は高々 1 個でなければなりません。 行 $i$ の 1 の個数を $s_i=\sum_{j=0}^{2}x_{i,j}$ とすると、これは範囲制約 $0\leq s_i\leq 1$ です。 範囲の幅が 1 なので、QUBO++ はこれを補助変数のない次のペナルティにします（比較制約の場合 2）：
\[\begin{aligned} \text{atmostone} &= \sum_{i=0}^{n-1}\Bigl(0\leq\sum_{j=0}^{2}x_{i,j}\leq 1\Bigr)\\ &= \sum_{i=0}^{n-1}s_i(s_i-1) \end{aligned}\]$s_i(s_i-1)$ は、$s_i=0, 1$ のとき 0、$s_i=2$ のとき 2、$s_i=3$ のとき 6 です。
この制約は qbpp.cons() で宣言することもできますが、ここではペナルティ式のまま使います。 qbpp.cons() が役立つのは、ペナルティ式にすると補助変数が要る制約です（非線形関数とネイティブ制約の「ペナルティ式との比較」）。 この制約は補助変数が要らず、$s_i$ が 3 変数の和なので、展開しても $s_i(s_i-1)=2(x_{i,0}x_{i,1}+x_{i,0}x_{i,2}+x_{i,1}x_{i,2})$ という 2 次の項 3 つの小さな式です。 qbpp.cons() で小さな制約を $n$ 個作るより、展開して 1 つの QUBO 式にまとめたほうが、GPU での並列計算に向いています。
隣接ノードは異なる色
辺の両端のノードを、同じ色で塗ってはいけません：
\[\text{different} = \sum_{(u,v)\in E}\sum_{j=0}^{2}x_{u,j}x_{v,j}\]これはグラフ彩色問題と同じ式です。 塗らないノードの行はすべて 0 なので、そのノードにつながる辺の項はすべて 0 になります。
塗るノードの数
これらの制約を守って、色を塗るノードの数を最大にします。 各行の 1 は高々 1 個なので、塗るノードの数は 1 の個数です：
\[\text{colored} = \sum_{i=0}^{n-1}\sum_{j=0}^{2}x_{i,j}\]削除するノードの数は $n-\text{colored}$ なので、塗るノードの数を最大にすることは、削除するノードの数を最小にすることです。
QUBO 目的関数
colored を最大にするので、符号を反転して、次の QUBO 式を最小化します：
\[f = -\text{colored} + 2\,(\text{atmostone} + \text{different})\]制約を優先するため、ペナルティを 2 倍しています。 制約を破っている解で、1 が 2 個以上ある行か、同じ色で隣り合う 2 ノードの一方の行の 1 を 1 つ 0 にすると、colored は 1 減りますが、ペナルティは 2 以上減ります。 そのため、制約を破った解が $f$ の最小になることはなく、$f$ の最小値は塗るノードの最大数の符号を反転した値になります。 重みは 1 より大きければ十分です。
この定式化は、各ノードを色ごとに 3 つに分けた新しいグラフでの最大独立集合問題と同じ形です。 新しいグラフでは、同じノードの 3 つを互いに結び、元のグラフの辺 $(u,v)$ ごとに $u$ と $v$ の同じ色どうしを結びます。 塗るノードを最大にすることは、新しいグラフの独立集合を最大にすることです。
QUBO++ プログラム
グラフ彩色問題と同じ 16 ノードのグラフで、削除するノードの最小数を求めます：
import pyqbpp as qbpp
n = 16
edges = [
(0, 1), (0, 2), (0, 4), (1, 3), (1, 4), (1, 7), (2, 5),
(2, 6), (3, 7), (3, 13), (3, 15), (4, 6), (4, 7), (4, 14),
(5, 8), (6, 8), (6, 14), (7, 14), (7, 15), (8, 9), (8, 12),
(9, 10), (9, 11), (9, 12), (10, 11),(10, 12),(10, 13),(10, 14),
(10, 15),(11, 13),(12, 14),(13, 15),(14, 15)]
m = 3
x = qbpp.var("x", shape=(n, m))
atmostone = qbpp.sum(qbpp.constrain(qbpp.vector_sum(x), between=(0, 1)))
different = 0
for u, v in edges:
different += qbpp.sum(x[u] * x[v])
colored = qbpp.sum(x)
f = -colored + 2 * (atmostone + different)
f.simplify_as_binary()
solver = qbpp.EasySolver(f)
sol = solver.search(time_limit=1.0)
print(f"colored = {sol(colored)}")
print(f"atmostone = {sol(atmostone)}")
print(f"different = {sol(different)}")
node_color = qbpp.onehot_to_int(sol(x))
print("deleted nodes:", [i for i in range(n) if node_color[i] == -1])
qbpp.vector_sum(x) は各行の和の配列です。 qbpp.constrain(qbpp.vector_sum(x), between=(0, 1)) は各行の範囲制約の配列で、qbpp.sum() で足すと atmostone になります。 different はグラフ彩色問題と同じです。 qbpp.sum(x) は x のすべての要素の和で、colored になります。 最小値は分からないので、目標エネルギーは指定せず、Easy Solver で 1 秒探索します。
qbpp.onehot_to_int() は、行がワンホットでないとき $-1$ を返すので、削除したノードの値は $-1$ になります。 その番号を出力します。
このプログラムの出力は次のとおりです：
colored = 15
atmostone = 0
different = 0
deleted nodes: [7]
16 ノードのうち 15 ノードを 3 色で塗れます。 つまり、ノードを 1 つ削除すれば、残りは 3 色で彩色できます。 総当たりで調べると、1 つの削除で 3 色の彩色ができるのは、ノード 7・14・15 のどれかを削除したときだけです。 どれを削除する解が得られるかは、実行ごとに変わります。 次の図は、ノード 7 を削除した解で、削除したノードを白、残したノードを 3 色で描いています。
アメリカ本土 48 州
動画：地図の塗り分けでは、アメリカ本土の 48 州が 4 色で塗り分けられ、3 色では塗り分けられないことを確かめました。 ここでは、何州を除けば残りの州を 3 色で塗り分けられるかを求めます。 州をノードとし、境界線を共有する 2 州を辺で結んだ、48 ノード・105 辺のグラフです（点で接するだけの組は辺にしません）。
州の名前と辺の一覧は、JSON ファイル usa48.json に入っています（動画：地図の塗り分けと同じファイルです）。 辺は州の番号の組で、州の番号は names の位置です（たとえば [1, 25] はアリゾナとネバダ）。 usa48.json を、実行するディレクトリに置いて実行します。 式は 16 ノードのグラフと同じです。 ABS3 Solver で 10 秒探索し、best_energy_sols=0 にして、最良と同じエネルギーの解をすべて保持します。 保持した解ごとに、削除した州の名前の組を作り、組ごとに解の数を数えます。
import json
import pyqbpp as qbpp
data = json.load(open("usa48.json"))
names, edges = data["names"], data["edges"]
n, m = len(names), 3
x = qbpp.var("x", shape=(n, m))
atmostone = qbpp.sum(qbpp.constrain(qbpp.vector_sum(x), between=(0, 1)))
different = 0
for u, v in edges:
different += qbpp.sum(x[u] * x[v])
colored = qbpp.sum(x)
f = -colored + 2 * (atmostone + different)
f.simplify_as_binary()
solver = qbpp.ABS3Solver(f)
sol = solver.search(time_limit=10, best_energy_sols=0)
print(f"colored = {sol(colored)}")
sets = {}
for s in sol.sols:
node_color = qbpp.onehot_to_int(s(x))
key = tuple(names[i] for i in range(n) if node_color[i] == -1)
sets[key] = sets.get(key, 0) + 1
print(f"solutions = {len(sol.sols)}, deletion sets = {len(sets)}")
for key in sorted(sets):
print(f"{' + '.join(key)}: {sets[key]}")
このプログラムの出力は次のとおりです：
colored = 46
solutions = 1728, deletion sets = 24
Arizona + Kentucky: 48
Arizona + Ohio: 48
Arizona + Virginia: 24
Arizona + West Virginia: 72
California + Kentucky: 48
California + Ohio: 48
California + Virginia: 24
California + West Virginia: 72
Idaho + Kentucky: 96
Idaho + Ohio: 96
Idaho + Virginia: 48
Idaho + West Virginia: 144
Kentucky + Nevada: 96
Kentucky + Oregon: 96
Kentucky + Utah: 48
Nevada + Ohio: 96
Nevada + Virginia: 48
Nevada + West Virginia: 144
Ohio + Oregon: 96
Ohio + Utah: 48
Oregon + Virginia: 48
Oregon + West Virginia: 144
Utah + Virginia: 24
Utah + West Virginia: 72
塗れる州の最大数は 46、つまり削除する州の最小数は 2 で、削除する 2 州の組は 24 組あります。 残りの 46 州の塗り方は組ごとに複数あり（色の入れ替えだけでも 6 通り）、保持された解は全部で 1728 個です。 この出力は GPU を使ったときのものです。 GPU を使わないと 10 秒で保持できる解は少なくなります（20 コアの CPU で 135 個）が、この例では 24 組はすべて得られました。
Easy Solver でも最小の 2 州はすぐに見つかります。 ただし Easy Solver は最良解の近くを重点的に探すので、離れたところにある同じエネルギーの解はあまり集まりません（10 秒で 13 個の解、10 組）。 最良と同じエネルギーの解を広く集めるには、ABS3 Solver が向いています。
次の地図は、アリゾナとウェストバージニアを削除した解です。 削除した 2 州を斜線で示し、残りの 46 州を 3 色で塗っています。
なぜ 2 州で、なぜ 24 組か
真ん中の州を、隣の州が奇数個の輪のように囲んでいると、その部分は 3 色では塗れません。 輪を 3 色で塗るとき、奇数個の輪では 3 色すべてを使うので、輪のすべての州と隣り合う真ん中の州には 4 色目が要ります。 輪の州か真ん中の州のどれか 1 つを削除すれば、この形はなくなります。
48 州には、この形が 3 つあります。
- ネバダを、カリフォルニア・オレゴン・アイダホ・ユタ・アリゾナの 5 州が囲む
- ウェストバージニアを、オハイオ・ペンシルベニア・メリーランド・バージニア・ケンタッキーの 5 州が囲む
- ケンタッキーを、イリノイ・インディアナ・オハイオ・ウェストバージニア・バージニア・テネシー・ミズーリの 7 州が囲む
西のネバダの形と東の 2 つの形は州を共有しないので、少なくとも 2 州は削除しなければなりません。 西では、ネバダと、それを囲む 5 州（図の黄色）のどれか 1 州を削除します。 東では、2 つの形の両方に入っているケンタッキー・ウェストバージニア・オハイオ・バージニア（図の青）のどれか 1 州を削除すれば、両方の形がなくなります。 西の 6 州から 1 州、東の 4 州から 1 州を選ぶので $6\times 4=24$ 組で、出力の 24 組はちょうどこの組み合わせです。