多重リスト彩色に対する保証付きアルゴリズム

修 士 論 文 の 和 文 要 旨

研究科・専攻

大学院 情報理工学研究科 情報・ネットワーク工学専攻

氏 名

蛭田 海斗

学籍番号 1731130

論 文 題 目

多重リスト彩色に対する保証付きアルゴリズム

要 旨

優先的なユーザを考慮した周波数割り当てに関して，多重リスト彩色を用いたモデルが

Wang, Liu (2005) によって提案されている．割り当てる際には，それぞれのユーザに割り当て

られる色の数をなるべく平等にすることが求められる．そのような問題について，Wang, Liu

(2005)，Qin et al. (2013)，Vishram et al. (2014) によっていくつかのヒューリスティックな分

散アルゴリズムが提案されているが，理論的な保証が得られているものはまだない．本研究で

は，最小値を最大化するような多重リスト彩色問題 (以下では最小値最大化多重リスト彩色と

呼ぶ

_{) について，P ≠ NPの仮定のもとで最適値の定数倍の切り下げ以上を保証することが不可}

能であること，完全グラフにおける最小値最大化多重リスト彩色は

Harvey et al. (2006) によ

って提案されたセミマッチング問題に帰着できるため，多項式時間厳密アルゴリズムが存在す

ること，完全グラフに近いグラフや完全

_{2 部グラフ，星グラフに絞ってもNP困難であること，}

そして，グラフの特殊な分割が与えられれば多項式時間で保証のある解が得られることを示し

た．

2 つのクリーク𝑞𝑖

, 𝑞

𝑗

について，

E)𝑞𝑖

, 𝑞

𝑗* を，片方の端点が𝑞𝑖

に，もう片方の端点が

𝑞

𝑗

に属して

いる辺の集合とする．グラフのクリーク分割

_{Qが互いに素な𝑖, 𝑗, 𝑘について次のような条件を満}

たすとき，そのクリーク分割は良いクリーク分割であると言う．

∀𝑞

𝑖

, 𝑞

𝑗

, 𝑞

𝑘

∈ Q, E)𝑞𝑖

, 𝑞

𝑗

*と E(𝑞𝑖

, 𝑞

𝑘

)は互いに素である

すなわち良いクリーク分割とは，クリーク分割に含まれていない辺がクリーク同士を”上手く”

繋げているときに言う．

本研究では，良いクリーク分割が与えられたとき，

₁

𝑂𝑃𝑇 2

6以上の解を保証する多項式時間アル

ゴリズムを提案した．ただし，

_{𝑂𝑃𝑇は最小値最大化多重リスト彩色の最適値である．また，良}

いクリーク分割が多項式時間で得られることを示した．さらに，良いクリーク分割を一般化し

た

_{𝑘-良いクリーク分割について，そのようなクリーク分割でも保証が得られることを示した．}

一方で，

_{𝑘-良いクリーク分割を構成するのが𝑘 ≥ 2のときNP困難であることも示した．}

多重リスト彩色に対する保証付きアルゴリズム

情報・ネットワーク工学専攻

1731130

蛭田 海斗

目次

1 導入 3 1.1 背景と目的 . . . 3 1.2 グラフ理論に関する用語の定義と導入. . . 3 1.3 計算理論に関する用語の定義と導入 . . . 4 1.4 扱う問題の定義 . . . 5 2 先行研究 6 2.1 完全グラフにおける最小値最大化多重リスト彩色問題とセミマッチング . . . 6 3 計算複雜性 7 3.1 完全2部グラフ . . . 7 3.2 星グラフ . . . 9 3.3 完全グラフから辺を取り除いたグラフ. . . 11 3.4 一般のグラフにおける近似不可能性 . . . 12 4 特殊なクリーク分割 13 4.1 保証付きアルゴリズム . . . 14 4.2 良いクリーク分割と理想グラフ . . . 19 4.3 良いクリーク分割を構成するアルゴリズム . . . 20 4.4 良いクリーク分割の一般化 . . . 21 5 まとめと今後の課題 23

1

導入

1.1

背景と目的

優先的なユーザを考慮しつつ，周波数帯を効率よく割り当てる研究に関するモデルとして，グラフ理論にお ける多重リスト彩色を用いたモデルが[1]によって提案されている．このモデルでは，ユーザ間で干渉する周 波数帯の関係は干渉グラフと呼ばれるものを用いて表される．干渉グラフとは，一般のユーザをグラフの頂点 として，同じ周波数帯を使うと干渉してしまうユーザ同士を辺で結んだようなグラフである．このようなグ ラフの上で，優先ユーザによって専有されていない周波数帯 (グラフ理論では色と呼ばれる)を，それぞれの ユーザに干渉することなく複数個割り当てるような問題を考える．このとき，それぞれのユーザに割り当てら れる周波数帯の数をなるべく平等にすることが求められる． そのような問題について，周波数帯を割り当てるという文脈でいくつかのヒューリスティックな分散アルゴ リズムが提案されているが，理論的な保証が得られているものはまだない．したがって本研究では，そのよう な問題について，理論的な難しさを明らかにすること，および，理論的な保証が得られる多項式時間アルゴリ ズムを提案することを目的とする．具体的には，最も割り当てられた色の数が少ないユーザの色数を最大化す るような問題(最小値最大化多重リスト彩色問題)について，定数近似が不可能であること，いくつかのグラ フ族に絞ってもNP困難であること，および，グラフの特殊な分割が与えられれば多項式時間で保証のある解 が得られるようなアルゴリズムが存在することを示す．

1.2

グラフ理論に関する用語の定義と導入

集合V, Eに対して，Eの各元がV の部分集合で，要素数が2であるとき，順序対G = (V, E)を単純無向 グラフと呼び，V を頂点集合，Eを辺集合と呼ぶ．また，Eの各元に，V の部分集合で要素数が1であるも の(自己ループ)を許し，同じ元(多重辺)を区別するようにしたものを多重グラフと呼ぶ．本研究では，特に 断りがない限り，有限な単純無向グラフについてのみ取り扱う．そのため，単純無向グラフを単にグラフと呼 ぶ．Gの頂点集合と辺集合を，それぞれG(V ), G(E)と書くこともある．また，V (G), E(G)の元を，それぞ れグラフGの頂点，グラフGの辺と呼ぶこともある． グラフG = (V, E)の頂点u, v ∈ V について，(u, v)∈ Eのとき，uとvは隣接している言い，u (および v)は(u, v)に接続していると言う．また，u, vを(u, v)の端点と言う．ある頂点v ∈ V と隣接している頂点 の集合，すなわち，_{{u | u ∈ V, (u, v) ∈ E}}を，vの隣接頂点などと呼び，N (v)と書く．隣接頂点の個数，す なわち，_|N(v)|を，uの次数と呼び，dG(v)と書く．Gが明らかなときは，単にd(v)と書くこともある．次 数と辺の数の関係として，握手補題と呼ばれる次の式が知られている． ∑ v∈V d(v) = 2|E|. 頂点部分集合U ⊆ V を頂点とし，両端点がUに属している全てのEの辺を辺集合とするようなグラフを， Uによって誘導されるGの誘導部分グラフと呼ぶ． 任意の2頂点間に辺があるようなグラフのことを完全グラフと呼び，頂点数がnであるような完全グラフ のことをKnと書く．完全グラフであるような誘導部分グラフのことを，そのグラフのクリークと呼ぶ． グラフG = (V, E) の頂点の分割V = A∪ B, A ∩ B = ∅が存在して，Aの頂点間およびB の頂点間 に1 つも辺がないとき，そのグラフを2 部グラフと呼ぶ．また，2部グラフのことをG = (A∪ B, E)等

と書くこともある．_{∀(u, v) ∈ A × B, (u, v) ∈ E} を満たすとき，その2部グラフを完全2部グラフと呼ぶ． |A| = m, |B| = nとしたとき，完全2部グラフのことをKm,nと書くこともある． グラフG = (V, E)の道とは，V の頂点の部分列v0, v2, . . . , vkで，全ての1≤ i ≤ kについて，(vi₋₁, vi)∈ E であり，かつ，1つの辺が1度しか現れないようなもののことを言う．v0= vkのとき，その道を閉路と言う． グラフの任意の頂点から任意の頂点への道が存在するとき，そのグラフは連結であるという．グラフの全ての 辺を1度ずつ通るような閉路のことをオイラー閉路と呼び，オイラー閉路が存在するグラフのことをオイラー グラフと呼ぶ．全ての頂点の次数が偶数であるような連結な多重グラフは，オイラーグラフであることが知ら れている． グラフGの頂点V (G)からある集合Cへの写像c : V (G)→ Cをグラフの彩色といい，集合Cを色集合， Cの元を色などと呼ぶこともある．あるグラフの彩色において，同じ色が割り当てられた頂点が互いに隣接し ていないとき，すなわち，_{∀(u, v) ∈ E, c(u) ̸= c(v)}を満たすとき，その彩色は真であると言う．本稿では，真 であるような彩色のことを単に彩色と呼ぶことにする．あるグラフGについて，要素数がkの集合Cで全て の頂点が彩色できるとき，Gはk彩色可能であると言い，Gがk彩色可能であるような最小のkのことをG の染色数と言い，χ(G)と書く． グラフGのマッチングとは，Gの辺部分集合M ⊆ E(G)で，M の辺が互いに端点を共有しないようなも ののことを言う．

1.3

計算理論に関する用語の定義と導入

yesかnoで答えることができる問題を判定問題と呼ぶ．その判定問題の答えの証拠が与えらたときに，そ れが問題の条件を満たすかどうかを，最悪でも入力のサイズの多項式で抑えられる時間で確認できるような判 定問題の集合をNPと呼び，その判定問題自体が最悪でも入力のサイズの多項式で抑えられるような時間で解 くことができるような判定問題の集合をPと呼ぶ． 判定問題Aを多項式時間で解くアルゴリズムがあれば，それをサブルーチンとして用いることで問題Bが 多項式時間で解けるときに，BはAに多項式時間還元可能であるという．判定問題Aについて，全てのNP 問題がAへ多項式還元可能であるとき，AはNP困難であると言い，さらに，AがNPであるときはAは NP完全であるという．P̸=NPの仮定のもとで，NP完全である問題には入力の多項式時間で解くことができ るアルゴリズムが存在しない．例えば，あるグラフの染色数を求める問題はNP困難であり，あるグラフがk 彩色可能かどうかという判定問題はNP完全である． 判定問題AがNPで，問題Bを任意のNP完全問題とするとき，BがAへ多項式時間還元可能ならば，A はNP完全であることが知られている．したがって，ある判定問題がNP完全であることを示すためには，別 のNP完全であることが知られている問題から多項式時間還元すれば十分である． 1.3.1 3-SAT ある問題がNP完全であることを示すために，既にNP完全であることが知られているような問題が必要で ある．そこで，この節では本研究で用いた3-SATについて紹介する．

充足可能性問題(satisfiability problem, SAT)とは，1つの命題論理式が与えられたとき，それに含まれる

変数の値を偽あるいは真に上手く定めることによって全体の値を真にできる(充足する)かという問題である．

充足可能性問題は，ある特殊な形状を持つような論理式に限定しても，NP完全であることが知られている．

節内のリテラル数(現れる変数，もしくは変数の否定の数)が高々3つのものである．以下は3-SATの例であ り，x1, x2を真，x3を偽とすることで，充足する． (x1∨ x2∨ ¬x3)∧ (¬x1∨ ¬x2∨ ¬x3)∧ (¬x1∨ x2∨ ¬x3). 3-SATに限定しても，充足可能性問題はNP完全であることが知られている．

1.4

扱う問題の定義

本研究では平等さとして，最小値の最大化を用いる．すなわち，本研究で扱う問題は， • グラフG， • 有り得る色の集合C • 各頂点ごとの色のリストLv ⊆ C (∀v ∈ V (G)) を入力として， • 割り当てられた色の数が最も少ない頂点の色の数を最大化し， • 辺で結ばれた頂点同士は同じ色にならず， • vに割り当てられたすべての色はLvに入っている ような色の割り当てを見つける問題である．本研究ではこのような問題を最小値最大化多重リスト彩色問題と 呼ぶ．xv,cを頂点vの色cを使うか否かに対応する01変数とすると，最小値最大化多重リスト彩色問題は01 整数計画問題として次のように定式化できる． maximize w subject to xv,c= 0, ∀c /∈ Lv, xu,c+ xv,c≤ 1, ∀(u, v) ∈ E, ∑ c∈C xv,c≥ w, ∀v ∈ V, xv,c∈ {0, 1}, ∀v ∈ V, ∀c ∈ C. 図1は，次のような入力の最小値最大化多重リスト彩色問題の例である． • グラフG = (V, E)， • V = {x, y, z, w}，

• E = {(x, y), (x, z), (y, z), (y, w), (z, w)}，

• C = {c1, c2, c3, c4, c5, c6}， • Lx={c1, c2, c3, c4, c5}， • Ly={c1, c3, c4,}， • Lz={c2, c6}， • Lw={c3, c5}． そして，図2はこの問題の解の例である．この場合，全ての頂点に2色ずつ割り当てることができるため，最 適値は2以上であり，かつ，全ての頂点に3色割り当てることはできないため，最適値は2である．したがっ て，図2の解は最適解である．

図1 最小値最大化多重リスト彩色問題の例． 図2 最小値最大化多重リスト彩色問題の最適解の例．

2

先行研究

モデルを提案した[1]を初めとして，[2]，[3]によって，ヒューリスティックな分散アルゴリズムが提案され ているが，今の所，理論的な保証が得られているアルゴリズムや，その計算複雜性についての文献は存在し ない． また，リスト彩色においてよく研究されている問題は，条件を満たす任意のリストにおいて彩色が存在する か(choosability等と呼ばれる)という判定問題であり，本研究で扱うような，入力で色のリストが固定され るような問題とはあまり関連がない．リスト彩色については[4]を参考にされたい． 均等に割り当てるという文脈では，[5]において，グラフのマッチングと似た概念であるセミマッチングを 用いて，割り当ての最小値の最大化を行う問題の厳密解が得られる多項式時間アルゴリズムが提案されてい る．後に述べるが，完全グラフにおける最小値最大化多重リスト彩色問題はセミマッチングの問題に帰着でき るため，多項式時間で解くことができる．

2.1

完全グラフにおける最小値最大化多重リスト彩色問題とセミマッチング

2部グラフG = (U∪ V, E)上でのセミマッチングとは，辺部分集合M ⊆ Eで，全てのu∈ Uについて， uはちょうど1つのM の辺と接続しているようなもののことを言う．つまり，通常のマッチングと違い，1 対多のマッチングである． ある2部グラフG = (U∪ V, E)上のセミマッチングをM とする．v∈ U ∪ V について，M によってでき るグラフH = (U∪ V, M)における頂点の次数dH(v)をvのMによる次数と言い，dM(v)と書く． 正の実数の集合_R+ _{から実数への関数f : R}+ _{→ R において，x, y ∈ R}+ _{について x < y ならば} f (x + 1)− f(x) > f(y + 1) − f(y)が成り立つとき，f は狭義凸関数であるという． セミマッチング問題とは，U の最小次数が1以上であるような2部グラフG = (U∪ V, E)と，狭義凸関数 f :R+→ Rが与えられたとき，M による頂点のコストをcostM(v) = f (dM(v))として，V の頂点のM に よるコストの総和∑_v∈VcostM(v)が最小となるようなセミマッチングを求める問題である．セミマッチング 問題の最適解は，O(|U||E|)時間で求める事ができる[5]． 完全グラフにおける最小値最大化多重リスト彩色問題では，ある色で割り当てられる頂点は，どの頂点のリ ストにも入っていないような色がない場合には，ちょうど1つである．したがって，色集合をU，頂点集合を V，v∈ V のリストに色u∈ Uが入っている場合に，その間に辺を引いたような2部グラフを構成し，狭義凸

関数f を_{∀i ∈ R}+_{, f (i) >|V |f(i + 1)を満たす関数とすれば，セミマッチング問題を解くことに帰着できる．}

図3は，セミマッチングを用いて完全グラフにおける最小値最大化多重リスト彩色問題を解く例である．左

る2部グラフである． 図3 セミマッチングとK3における最小値最大化多重リスト彩色問題．

3

計算複雜性

この節では，最小値最大化多重リスト彩色問題において，入力のグラフをあるグラフ族に絞った場合にも NP困難であること，および，近似困難性を示す．NP困難性を示す際には，任意のグラフ族に絞った場合で も，最小値最大化多重リスト彩色問題の最適値がある値k以上であるかという判定問題がNPに入っている ことは明らかであるため，あるNP完全性が知られている問題から帰着できることについて述べれば十分で ある．

3.1

完全

2

部グラフ

完全2部グラフにおける最小値最大化多重リスト彩色問題において，任意の自然数k≥ 1について最適値 がk以上であるかどうかという判定問題がNP完全であることを示す．まずk = 1の場合について示し，そ こから容易にk≥ 1に一般化できることを述べる．

帰着には，NP完全性が知られているNot-all-equal 3-SAT (NAE3-SAT)という判定問題を用いる． NAE3-SATは3-SATに似た問題で，各クローズに3つの変数(もしくはその否定) があるようなCNFの命題論理

式が充足可能かどうかを考える．しかし，NAE3-SATではクローズ内の全ての変数が真になってはいけない，

すなわち，各クローズについて，1つ以上の変数が真で，かつ，1つ以上の変数が偽になるような変数への割

り当てが存在するか？という判定問題がNAE3-SATである．NAE3-SATは3-SATとは違い，全てのクロー

ズ内に全ての変数が正リテラルで表れているときも，NP完全であることが知られている．したがって，今回 はそのような場合についてのみ考える． NAE3-SATの変数をX ={x1. . . xn}，変数の否定をY ={y1. . . yn}，クローズをZ ={z1, . . . zm}とす る．また，クローズzjに入っている変数をxj,1, xj,2, xj,3 ∈ zjと表す． 次のような頂点集合V = A∪ B上の完全2部グラフを考える． A = X, B = ZT ∪ ZF∪ Y, ZT ={z1,T, . . . zm,T}, ZF ={z1,F, . . . zm,F}.

つまり，片側の部には変数個の頂点が，もう片側の部には変数個の頂点と，クローズの2倍の個数の頂点があ るような完全2部グラフである． そのグラフ上で，次のような色のリストを考える． Lv={Tk, Fk}, (v = xk ∈ X), Lv={Tk, Fk}, (v = yk∈ Y ), Lv={Ti, Tj, Tk}, (v = zl,T ∈ ZT, xi, xj, xk∈ zl), Lv={Fi, Fj, Fk}, (v = zl,F ∈ ZF, xi, xj, xk ∈ zl). つまり，各変数(とその否定)には専用の真偽を表す色が割り当てられていて，クローズを表す2つの頂点集 合の頂点について，1つ目の集合の各頂点には，そのクローズ内にある変数の真の色3つ，2つ目の集合の各 頂点には，そのクローズ内にある頂点の真偽に対応する変数の偽の色3つをそれぞれのリストに割り当てる． 図4はNAE3-SATの問題である (v∨ w ∨ x) ∧ (v ∨ x ∨ z) ∧ (w ∨ y ∨ z). を帰着した例である．ただし，辺は省略している． 図4 NAE3-SATからの帰着の例． このようなグラフと色のリストで，NAE3-SATの充足可能性が，最小値最大化多重リスト彩色の最適値が 1以上かどうかと同値であることを示す． 補題 1. NAE3-SATの充足可能性と，前述のグラフと色のリストにおける最小値最大化多重リスト彩色問題 の最適値が1以上かどうかは同値である． 証明. 全ての頂点に1色以上を割り当てることを考える．そのとき，X, Y 間について注目すると，変数xiと その否定yiに対応する頂点は隣接していて，さらに同じ色Ti, Fiのみがリストにある．したがって，xiとyi

に1色ずつ割り当てるしかない(つまり，xiとyiのうち，どちらか一方にはTiが，もう一方にはFiが割り 当てられる)．以上から，X とY にはそのような割り当てが行われると仮定して，ZT, ZF に1色以上割り当 てることができるかについて考えれば良い． NAE3-SATが充足できることは，各クローズに真と偽が必ず1つ以上含む割り当てがあることと同値であ る．変数iの真偽を前述のようにその頂点にTi, Fiのどちらが割り当てられているかに対応させる．ここで， クローズzlについて，そのクローズの変数をu, v, wとすると，Tu, Tv, Tw, Fu, Fv, Fwがリストに含まれて いる頂点はxu, xv, xw, yu, yv, yw, zl,T, zl,F だけであり，さらにその中でzl,T およびzl,F と隣接しているのは xu, xv, xwだけであることに注意する．すると，NAE3-SATが充足するとき，xu, xv, xwに割り当てられた色 の中に，Tu, Tv, Twのうち1つと，Fu, Fv, Fwのうち1つが必ず存在する．その色をzl,T およびzl,F に割り 当てることができるので，全ての頂点に1色以上を割り当てることができる． 逆に，NAE3-SATが充足できないとき，どのようにXとY に真偽に対応する色を割り当てたとしても， 必ずあるクローズzlで，その変数u, v, wにTu, Tv, Twが割り当てられている，もしくはFu, Fv, Fwが割り 当てられているようなものが存在する．そのような場合には，Lzl,T ={Ti, Tj, Tk}, Lzl,F ={Fi, Fj, Fk}であ るから，そのどちらかには1色も割り当てることができない．したがって，最適値は0である． したがって，完全2部グラフにおける最小値最大化多重リスト彩色問題の最適値が1以上かどうかという判 定問題はNP完全である．k≥ 1以上かどうかに一般化するためには，単にそれぞれの頂点の色のリストに専 用の色をk− 1個ずつ割り当てれば良い．したがって，次の定理が成り立つ． 定理1. 任意の自然数k≥ 1について，完全2部グラフにおける最小値最大化多重リスト彩色問題の最適値が k以上かどうかという判定問題はNP完全である．

3.2

星グラフ

片側の部の頂点数が1であるような完全2部グラフを星グラフと呼ぶ．この節では，星グラフにおける最小 値最大化多重リスト彩色問題において，最適値がc以上であるかという判定問題がNP完全となるようなcが 存在することを示す．星グラフは完全2部グラフであるが，前節の完全グラフのNP完全性の帰着は，星グラ フでは使うことができないことに注意する．逆に，本節で述べる帰着は，両方の部の頂点数が2以上であるよ うな完全2部グラフでは使うことができない． 帰着には，NP完全性が知られている集合横断問題を用いる．集合横断問題とは，集合U，Uの部分集合族 S⊆ 2U_{，自然数k≥ 1が与えられたとき，次の条件を満たすU の部分集合H ⊆ Uがあるかどうかを判定す} る問題である． • |H| = k， • ∀U′ _{∈ S, U}′_{∩ H ̸= ∅．} 言い換えれば，任意のSの要素U′に対して，U′の要素のうち少なくとも1つはH に含まれているように， Hを選ぶような問題である． 集合横断問題は，_|U|が偶数で，かつk = |U|₂ でもNP完全であることが知られている． 集合横断問題の入力であるU とSに対して，次のような頂点集合V = A∪ B上の星グラフと色のリスト

を考える．ただし，U の要素数は偶数であるとする． V = A∪ B, A ={x}, B = S, Lx= U, Ls={u | u ∈ s} ∪ {cs,1, cs,2, . . . , c_s,|U| 2 −1} (s ∈ B) ． つまり，中心の頂点xのリストにはU の要素が，それ以外の頂点のリストには，その頂点に対応する集合に 含まれている要素および，その頂点専用の|U|_{2 − 1}色が含まれている．図5は，次の集合横断問題を帰着した 例である．ただし，各頂点に専用の色は全てXで描かれているが，実際には全て異なる． U = 1, 2, 3, 4, S ={{1, 2}, {2, 3, 4}, {2, 4}, {1, 4}, {3}}. 図5 集合横断問題からの帰着の例． このおようなグラフと色のリストで，k = |U|₂ である集合横断問題の真偽と，最小値最大化多重リスト彩色 の最適値が |U|₂ 以上かどうかが同値であることを示す． 定理 2. k = |U|₂ である集合横断問題の真偽と，前述のグラフにおける最小値最大化多重リスト彩色の最適値 が|U|₂ 以上かどうかが同値である 証明. 集合横断問題が真であるとき，その解であるU の部分集合の要素を最小値最大化多重リスト彩色問題 のグラフのBの頂点に割り当てることによって，全てのBの頂点に1色ずつ割り当てることができる．そし

て，残りの|U|₂ 色をAの頂点に割り当てることができる．したがって，最小値最大化多重リスト彩色の最適 値は |U|₂ 以上である．逆に，集合横断問題が偽であるとき，どのような解においても |U|₂ 色ではBの全ての 頂点に1色ずつ割り当てることはできない．したがって，Bの全ての頂点に1色ずつ割り当てるために，|U| 2 色より多くの色が必要になるが，そのとき，Aの頂点には|U|₂ より少ない色しか割り当てることができない． したがって，最適値は |U|₂ 未満である．

3.3

完全グラフから辺を取り除いたグラフ

完全グラフにおける最小値最大化多重リスト彩色問題はセミマッチングのアルゴリズムによって多項式時間 で最適解を求めることができる．この節では，完全グラフから辺を取り除いたグラフにおける計算複雜性につ いて述べる． n頂点の完全グラフの頂点を_{v1, . . . , vn}とする．このとき，次の辺を取り除いたグラフを，準完全グラフ と呼ぶことにする． • (v3i+1, v3i+3) (i = 0, 1, . . . ,⌊(n − 1)/3⌋ − 1)． 前節と同様に，準完全グラフにおける最小値最大化多重リスト彩色問題において，任意の自然数k≥ 1につ いて最適値がk以上であるかどうかという判定問題がNP完全であることを示す．まずk = 1の場合につい て示し，そこから容易にk≥ 1に一般化できることを述べるというのも同様である． 帰着には，3-SATを用いる．任意の3-SATは，全ての変数について，正リテラル2つと負リテラル1つで 構成できることが知られている．したがって，今回はそのような場合についてのみ考える． 変数をx0, x1, . . . , xn−1としたとき，次のような3n頂点の準完全グラフと色のリストを構成し，3-SATの 充足可能性と最小値最大化多重リスト彩色問題の最適解が1以上かどうかが同値となることを示す．まず頂点

については，i = 0, 1, . . . , n− 1について，v3i+1, v3i+3が変数xiに，v3i+2がその否定xiに対応する．

色のリストは次のような手順で構成する． 1. k = 0, 1, . . . , n− 1について，頂点v3k+1, v3k+2, v3k+3には，色Tkをリストに割り当てる． 2. クローズcに対して，そのクローズに含まれている変数(もしくは変数の否定)に対応する頂点で，ま だどのクローズに対応する色もリストに入っていないような頂点をそれぞれ1つずつ選ぶ．その頂点に は，cが3つのリテラルで構成されているならば，対応する2色Cc,0, Cc,1をリストに割り当て，2つ のリテラルで構成されているならば，対応する色1色Cc,0をリストに割り当てる． 3. 手順2で割り当てられなかった頂点には，その頂点のリストにのみ固有の1色を割り当てる． 図6は，全ての変数について，正リテラル2つと負リテラル1つで構成されているような，3-SATの問題で ある (x0∨ x1∨ x2)∧ (x0∨ x1∨ x2)∧ (x0∨ x1∨ x2) を帰着した例である．ただし，破線で描かれた辺は完全グラフとの対比をわかりやすくするために描かれてい るが，実際には存在しない． 補題2. 3-SATの充足可能性と，前述のグラフと色のリストにおける最小値最大化多重リスト彩色問題の最適 値が1以上かどうかは同値である． 証明. 各変数kとその否定に対応する頂点v3k+1, v3k+2, v3k+3について，Tkが割り当てられている頂点が真，

図6 3-SATからの帰着の例． 割り当てられていない頂点が偽に対応する．3-SATが充足可能であるとき，全てのクローズにおいて，その クローズの変数(もしくはその否定)が1つ以上真になるような真偽の割り当てが存在する．したがって，そ の真偽を前述のように色の割り当てに対応させると，手順2でリストに色が割り当てられた全ての頂点viに ついて，同じクローズに属している変数をvj, vkとすると，vi, vj, vkのうちのどれか1つには真に対応する 色が割り当てられている．したがって，残った2つの頂点に，クローズに対応する2つの色を割り当てれば， 最適値は1以上となる．逆に，3-SATが充足不能であるとき，vi, vj, vk に全てT の色が割り当てられていな いようなクローズが存在する．そのとき，vi, vj, vkはクリークであるから，クローズに対応する2色ではその 3頂点に1色ずつ割り当てることはできない．したがって，最適値は0である したがって，準完全グラフにおける最小値最大化多重リスト彩色問題の最適値が1以上かどうかという判定 問題はNP完全である．k≥ 1以上かどうかに一般化するためには，単にそれぞれの頂点の色のリストに専用 の色をk− 1個ずつ割り当てれば良い．したがって，次の定理が成り立つ． 定理3. 任意の自然数k≥ 1について，準完全グラフにおける最小値最大化多重リスト彩色問題の最適値がk 以上かどうかという判定問題はNP完全である．

3.4

一般のグラフにおける近似不可能性

この節では一般グラフでの近似不可能性について示す．互いに素な言語L1, L2について，あるアルゴリズ ムがL1とL2の間で区別できるとは，そのアルゴリズムが，入力xがx∈ L1のときにYes，入力がx∈ L2 のときにはNoと答え，xがL1, L2のどちらにも入っていないときには，適当に(正しくないかもしれないよ うに)答えるようなアルゴリズムであるときに言う．近似不可能性の証明のために，次の定理から得られる系 を用いる． 定理 4. [6][7]任意の定数g > 1について，ある定数cが存在して，グラフH が与えられたときに，Hは c 彩色可能である，もしくはHの染色数がgcより大きい，という2つの間で区別できる多項式時間アルゴリズ ムはP̸= NPの仮定のもとで存在しない．

これはすなわち，任意の定数gについてc彩色可能グラフをgc彩色するのはNP困難であることを意味し ている．したがって，次の系が得られる． 系 1. [6][7]任意の定数g > 1について，あるgによって決まる定数cが存在して，c彩色可能な全てのグラ フをgc彩色できるような多項式時間アルゴリズムはP̸= NPの仮定のもとで存在しない． ここから，つぎの定理を得る． 定理 5. 一般のグラフにおいて，任意の定数g > 1について，最小値最大化リスト彩色問題の最適値をOPT としたとき，目的関数が_{⌊OPTg ⌋}以上となる解を出力するような多項式時間アルゴリズムは，P̸= NPの仮定 のもとで存在しない． 証明. 任意の定数g > 1について，定理4を満たすような定数cと，入力であるc彩色可能なグラフGを考 える．そのとき，次のような最小値最大化多重リスト彩色問題の入力を構成する． • グラフG， • ∀v ∈ G(V )について，vの色のリストLv ={1, 2, . . . , gc}． このとき，Gはc彩色可能であるから，明らかに最小値最大化多重リスト彩色問題の最適値はg以上である． 最小値最大化多重リスト彩色問題に_{⌊OPTg ⌋}を満たす解を出力する多項式時間アルゴリズムが存在したと仮 定する．そのとき，そのアルゴリズムは目的関数値が1以上の解を出力する，すなわち，全ての頂点にgc色 のうちの1色が割り当てられている．したがって，これはc彩色可能なグラフをgc以下の色で彩色したに等 しい．よって前述の系に矛盾するため，P̸= NPの仮定のもとで所望のアルゴリズムは存在しない．

4

特殊なクリーク分割

グラフの頂点集合が，そのグラフの複数のクリークの頂点で分割されているときに，それらのクリークの集 合のことグラフのクリーク分割と言う．先行研究により，完全グラフにおける最小値最大化多重リスト彩色は 多項式時間で厳密解を求めることができる．したがって，この節では，特殊なクリーク分割が得られている場 合について考える．そのために，いくつかの定義を行う． グラフGのクリーク分割Qの元qの頂点vについて，N+_{(v) :={x | (v, x) ∈ E(G), x /∈ V (q)}とする．} qi, qj∈ Qとし，qi̸= qjとする．G(E)のうち，片方の端点がqiに，もう片方の端点がqjに属しているよ うな辺の集合を，qiとqjを結ぶ辺といい，E(qi, qj)と書く． 2つの辺集合E1, E2について，E1に属する全ての辺が，E2に属する全ての辺と端点を共有しないとき， E1とE2は互いに素であるという． グラフのクリーク分割が互いに素なi, j, kについて次のような条件を満たすとき，そのクリーク分割は良い クリーク分割であると言う． ∀qi, qj, qk∈ Q, E(qi, qj)とE(qi, qk)は互いに素である. すなわち良いクリーク分割とは，クリーク分割に含まれていない辺がクリーク同士を“上手く”繋げていると きに言う．図7は，良いクリーク分割をもつようなグラフである． ここで，準完全グラフと良いクリーク分割の関係について述べる．

図7 良いクリーク分割の例． 補題3. 準完全グラフには良いクリーク分割が存在する． 証明. 準完全グラフGの頂点をV ={v1, . . . , vn}とし，nは3の倍数とする．このとき，次のように頂点を 分割する． V1={vk ∈ V | kを3で割った余りが1}, V2= V1\ V1. ここで，準完全グラフの定義から，全ての頂点間には， (v3i+1, v3i+3) (i = 0, 1, . . . ,⌊(n − 1)/3⌋ − 1) で表される辺を除いて，必ず辺が存在する．除かれている辺は，片方の端点がV1，もう片方の端点がV2に 属している．したがって，V1の頂点間，およびV2の頂点間は必ず辺で結ばれている．つまり，V1,V2で誘導 される部分グラフq1, q2はそれぞれGのクリークである．全ての頂点を2つのクリークで分割できたので， q1, q2は良いクリーク分割の定義を満たす． これは線形時間で求めることができる．したがって，前節の準完全グラフのNP完全性から，以下の系が得 られる． 系2. 良いクリーク分割が与えられていた場合でも，最小値最大化多重リスト彩色問題はNP完全である．

4.1

保証付きアルゴリズム

この節では，グラフGの良いクリーク分割が入力として与えられているとき，最小値最大化多重リスト彩 色問題には多項式時間で⌊OPT 2 ⌋ 以上の解を出力するアルゴリズムについて述べる．このアルゴリズムのアイ デアは，まず各クリークごとに，完全グラフに対するアルゴリズムを適用し，その解を元に割り当てを行うと いうものである．まず最初に，その割り当てに用いる補題について述べる． 補題4. 任意の2部グラフG = (V, E)には，次のような部分グラフH = (V, E′)が存在する． ∀(v ∈ V ), ⌊ dG(v) 2 ⌋ ≤ dH(v)≤ ⌈ dG(v) 2 ⌉ .

Algorithm 1良いクリーク分割に対するアルゴリズム for all qi∈ Q do qiに厳密アルゴリズムを適用し，厳密解を求める． end for for all qi∈ Q do for all qj∈ Q do GB = (V (qi)∪ V (qj), E(qi, qj))とする． GBについて，半マッチングEhalfを求める．

for all e = (u, v)∈ E(qi, qj) do

u, vの両方に割り当てられている色を_Cˆ_{u,vとする．}

if e∈ Ehalf then

ˆ

Cu,vのうち，qi側に半分の切り下げ，qj側に切り上げをした個数を割り当てる．

else if e∈ ˆE\ Ehalf then

ˆ Cu,vのうち，qj側に半分の切り下げ，qi側に切り上げをした個数を割り当てる． end if end for end for end for 最終的な色の割り当てを出力する． 証明. E′ =∅とする．任意の2部グラフGにおいて，握手補題から，次数が奇数の頂点は偶数個存在する． したがって，それらを適当に辺で結ぶことによって，全ての頂点の次数が偶数のグラフが得られる(このとき 辺が重複する可能性があるが，その場合は2本の辺があるとする)．このとき加えた辺をE′′とする．全ての 頂点の次数が偶数であることから，それぞれの連結成分において，全ての辺をちょうど1つずつ通るようなオ イラー閉路が存在する．そのオイラー閉路の辺を1つ飛ばしでE′に加える．そしてその後，E′′をE′から除 く．このとき，各頂点に対して，そのように取り除かれる辺は高々1つであることに注意すると，このように してできたE′からなる部分グラフHにおいて，全ての頂点v∈ V について { dG(v)+1 2 − 1 ≤ dH(v)≤ dG(v)+1 2 (dG(v)は奇数), dH(v) = dG(v) 2 (dG(v)は偶数). が成り立つ．したがって補題の式は成り立つ． このように次数が半分(奇数次数の頂点なら半分の切り下げと切り上げの間)になるような部分グラフの辺 集合をグラフの半マッチングと呼ぶことにする． アルゴリズム1は，グラフの良いクリーク分割が与えられているとき，クリークごとの最適解を求めた後 に，2つのクリーク間でどちらのクリークでも使われている色を，半マッチングに従って上手く割り振るアル ゴリズムである．図8から図14は，アルゴリズム1の開始から，最初に行われる2つのクリーク間で割り当 てが終わるまでの動作例である． 定理6. 最小値最大化多重リスト彩色問題の最適値をOPTとすると，アルゴリズム1は多項式時間で⌊OPT 2 ⌋ 以上の解を出力する．

図8 問題の入力と良いクリーク分割． 図9 クリークごとの最適解と，注目する2つのクリークqi, qj． 証明. アルゴリズム1の計算量は，m =|E|として，クリークごとの最適値を求めるのにO(n· nm)，全体の 2部グラフを作るのにO(n2m)，半マッチング(オイラー閉路) を求めるのにO(m)かかることを考えると， O(n· nm + n2m + m) = O(n2m)である．以下では，アルゴリズム1の出力が最適値の半分の切り下げ以上 であることを示す． アルゴリズム1の出力である色の割り当てにおいて，各頂点に割り当てられる色の個数の最小値ALGとす る．良いクリーク分割を構成する各クリークで，厳密解を求める．その厳密解を上手く組み合わせることを考 える．定義から,∀qi, qj, qk ∈ Q, E(qi, qj)とE(qi, qk)は互いに素である．クリークの組(qi, qj)について考え

図10 qi, qj間で辺が結ばれている部分．

図11 qi, qj間の2部グラフ．

図13 半マッチングによる色の割り当て． 図14 qi, qj間における割り当てが終了した時点での解の状態． る．u∈ V (qi)について，良いクリーク分割の定義から，N+(u)を頂点集合とするGの誘導部分グラフは完 全グラフである．したがって，N+_{(u)の頂点に割り当てられた色は互いに素である．u∈ V (q} j)のときも同 様である．このため，全てのクリークの組それぞれに対して，個別に被っている部分を上手く分配できれば 良い． ２つのクリークの頂点とその間の辺からなる２部グラフGB= (V (qi)∪ V (qj), E(qi, qj))について，その上 での半マッチングを考える．補題4から，任意の2部グラフにおいて，半マッチングは必ず存在する．それに 従って分配を行うと， ⌊ min q∈Q qにおける最適値 2 ⌋ ≤ min u∈V ( Nu+ ∑ v∈N+_(u) ⌊ ˆ Cu,v 2 ⌋ ) ≤ ALG

となる．ただし，Nuは，u∈ V に割り当てられていて，N+(u)のどの頂点とも被っていない色の数 である． 全てのクリークについて，そのクリーク内での最適値は，全体の最適値以上である．なぜなら，そのクリー ク以外の頂点が増えたとしても，クリーク内の頂点に割り当てることができる色の数は増えないからである． したがって，ALGは最低でも ⌊ OPT 2 ⌋ ≤ ⌊ min q∈Q qにおける最適値 2 ⌋ ≤ ALG となる．

4.2

良いクリーク分割と理想グラフ

グラフGのクリーク数をω(G)，染色数をω(G) = χ(G)とする．グラフGの任意の誘導部分グラフIに おいて，ω(I) = χ(I)のとき，グラフGは理想グラフであると言う．理想グラフでは，染色数やクリーク数を 多項式時間で求められることが知られている[8]．この節では，良いクリーク分割が存在するグラフが理想グ ラフであることを示す．証明には次の定理を用いる． 定理 7. （強理想グラフ定理[9]）Knをn頂点の完全グラフとする．n頂点のグラフG = (V (G), E(G))が 理想グラフであるための必要十分条件は，GとGの補グラフH = (V, E(Kn)\E(G))が頂点数5以上の奇閉 路を誘導部分グラフとして含まないことである． したがって，あるグラフGが理想グラフであることを示すためには，そのグラフとその補グラフが頂点数5 以上の奇閉路を誘導部分グラフとして含まないことを示せば十分である． 定理8. 良いクリーク分割が存在するグラフは理想グラフである． 証明. グラフGを，良いクリーク分割が存在するグラフとする．GとGの補グラフH が頂点数5以上の奇 閉路を含まないことを示す． Gに長さ5以上の奇閉路が存在したと仮定する．この奇閉路は各クリークの辺を高々1つまでしか含まな い(クリークであるため，2つ以上含んだ場合に誘導部分グラフが閉路ではなくなってしまう)．また同様の理 由で，同じクリーク間を結ぶ辺を高々1つまでしか含まない．以上から，奇閉路には，クリーク間を結ぶ辺が 2つ連続することになる．しかし，これは良いクリーク分割の定義と矛盾する． Hに長さn≥ 5の奇閉路が存在したと仮定する．このとき，その奇閉路の補グラフがGの誘導部分グラフ として含まれる．その補グラフをSとすると，Sはn−1 2 頂点のクリークと，クリークではない連結な n+1 2 頂 点にわけることができる．次の補題から，Sは良いクリーク分割をすることができないため，Gの良いクリー ク分割が存在することと矛盾する． 補題5. 奇閉路の補グラフは良いクリーク分割をすることができない． 証明. n頂点の奇閉路の補グラフSのクリーク分割を考える．n = 5のときは補グラフも5頂点の奇閉路であ る．5頂点の奇閉路は，頂点数3のクリークを持たないから，クリーク分割には必ず1頂点のクリークが含ま れる．その頂点vの隣接頂点同士が隣接していないときは，良いクリーク分割の定義に矛盾する．そのため， v隣接頂点同士は隣接しているが，これは頂点数3のクリークとなるので，矛盾する．したがって，n≥ 7と する．クリーク分割に含まれる最大のクリークKのサイズは_⌊n/2⌋である．Sのクリーク分割が良いクリー ク分割であることを仮定して矛盾を導く．Sの頂点の次数はn− 3 (完全グラフKnから閉路の辺2本引く)

Algorithm 2良いクリーク分割を構成するアルゴリズム．

if Gが2つ以下のクリークで分割できるthen

その分割を良いクリーク分割として出力する． end if

for (a, b)∈ E(G) do

S← {(a, b)}．

E∗← ∅． while S̸= ∅ do

(c, d)← Sから適当に１つ選ぶ．

K← N(c) ∪ N(d)

for e∈ {(u, v) | (u, v) ∈ E(G), (u, v) /∈ E∗, (u, v) /∈ S, u ∈ K, v /∈ K} do S← S ∪ {e}.

end for

E∗← E∗∪ {(u, v) | (u, v) ∈ E(G), u ∈ K, v /∈ K}． end while if グラフ(V (G), E(G)\ E∗)が，いくつかのクリークで構成されているthen それらのクリークを良いクリーク分割として出力する． end if end for 良いクリーク分割はできないと出力する． であるから，必ず各頂点からn− 3 − ⌊n/2⌋ + 1 = ⌈n/2⌉ − 2本はほかのクリークと接続している辺が出てい る．良いクリーク分割であることを仮定すると，これらの辺の端点は同じクリークに属する必要があるから， 少なくともK以外に_{⌈n/2⌉ − 2}以上のサイズのクリークがもう一つ存在するが，Kが最大クリークであるた め，Kのサイズも_{⌈n/2⌉ − 2}以上である．ここで，Kのサイズが_{⌈n/2⌉ − 2}であるとすると，Kが最大であ ることに矛盾するため，Kのサイズは_{⌈n/2⌉ − 1 = ⌊n/2⌋}である．したがって，それらのクリークに含まれ ない頂点は2頂点だけなので，それらが2頂点のクリークであるとすると，少なくとも各頂点からn− 4本の 辺がそれぞれ1つのクリークの頂点と接続しているが，n = 7のときは頂点数が最大以上のクリークができて しまうため矛盾．n≥ 9のときはn− 4 ≥ ⌊n/2⌋のため，矛盾． これらの結果から，良いクリーク分割を持つグラフは理想グラフの部分族であり，染色数が多項式時間で求 まる一方で，最小値最大化多重リスト彩色はNP困難であることがわかる．

4.3

良いクリーク分割を構成するアルゴリズム

この節では，良いクリーク分割を構成する多項式時間アルゴリズムについて述べる．良いクリーク分割の定 義から，異なるクリークのペアにおいて，クリーク間の辺は端点を共有しない．したがって，あるクリーク間 の辺(u, v)の両端点の隣接頂点の合併N (u)∪ N(v)は，その辺が結ぶ2つのクリークの頂点集合の合併とな る．それを用いたアルゴリズムがアルゴリズム2である． 補題 6. Gを連結グラフとする．アルゴリズム2は多項式時間で，Gの良いクリーク分割が存在すれば必ず

それを出力する．

証明. まずアルゴリズム2の計算量について示す．あるグラフが2つのクリークで分割できるかどうかを判定

するには，そのグラフの補グラフが2部グラフかどうかを判定すれば良い．これは頂点数に関する線形時間で

行うことができる．また，Sに1度挿入された辺はE∗にも加えられることから，whileループは高々_|E(G)|

回である．さらに，whileループ内のforループは高々_|E(G)|回である．したがって，アルゴリズム2の計

算量はO(|V (G)|) + O(|E(G)|3) = O(|E(G)|3)である． 次に，Gの良いクリーク分割が存在すれば，アルゴリズム2は必ずそのうちの1つであるQを出力するこ とを示す．Gが2つ以下のクリークで分割できるとき，アルゴリズム2は明らかに良いクリーク分割を出力 する．したがって，Gの任意の良いクリーク分割は3つ以上のクリークで構成されていると仮定する．また， 一般性を失わず，(a, b)∈ E(G)をクリーク間の辺であるとする．このとき，良いクリーク分割が出力される ことを示す． Sの初期値は_{{(a, b)}}であるから，取り出される辺は(a, b)である．良いクリーク分割の定義より，Kは辺 (a, b)が結んでいる2つのクリークqa, qb ∈ Qの頂点集合の合併である．また，E∗およびSに加えられる辺 は，qaもしくはqbとそれ以外のクリークを結ぶような全ての辺である．同様に，Sから取り出される辺(c, d) がクリーク間の辺であるとき，Kは辺(c, d)が結んでいる2つのクリークの頂点集合の合併であり，E∗およ びSに加えられる辺の候補は，(c, d)が結んでいる2つのクリークとそれ以外のクリークを結ぶような全ての 辺である．グラフが連結であり，任意の良いクリーク分割が3つ以上のクリークで構成されていることから， 任意のクリークのペアqi, qjについて，そのどちらか一方はqi, qjのどちらでもないクリークとの間に辺が存 在する．したがって，任意のクリーク間の辺がSに含まれるから，E∗にも任意のクリーク間の辺が含まれる． 以上から，Gの良いクリーク分割が存在するならば，グラフH = (V (G), E(G)\ E∗)にはクリーク間の辺が 存在しない．したがって，V (H) =∪_q∈QV (q), E(H) =∪_q∈QE(q)となり，Qが出力される． したがって，次が成り立つ． 定理9. 良いクリーク分割ができるかどうかは多項式時間で判定することができる．また，同時に良いクリー ク分割を構成することができる．

4.4

良いクリーク分割の一般化

この節では，良いクリーク分割の一般化について述べる．グラフGのクリーク分割Qが良いクリーク分割 であることの定義は，互いに素なi, j, kについて次のような条件を満たすことであった． ∀qi, qj, qk∈ Q, E(qi, qj)とE(qi, qk)は互いに素である. これは，任意の頂点について，N+_{(v)の頂点を含んでいるクリークの数は高々1つという条件に言い換える} ことができる．すなわち，良いクリーク分割であるための条件は，次のように書ける． ∀qi∈ Q, ∀v ∈ V (qi),|{q ∈ Q | ∃u ∈ N+(v), u∈ q}| ≤ 1. これを一般化することを考える．グラフのクリーク分割が次の条件を満たすとき，そのクリーク分割はk-良い クリーク分割であるという． ∀qi∈ Q, ∀v ∈ V (qi),|{q ∈ Q | ∃u ∈ N+(v), u∈ q}| ≤ k.

1-良いクリーク分割は良いクリーク分割である． アルゴリズム1は，k-良いクリーク分割でも全く同じように動作する．その際，出力される解は，最適値を OPTとしたとき，⌊OPT 2k ⌋ 以上である．何故なら，ある頂点について，クリーク間での割り当てが行われるの は高々k回だからである．したがって，例えば2-良いクリーク分割を求めることができれば，⌊OPT 4 ⌋ 以上の 解を多項式時間で求めることができる． しかしながら，k-良いクリーク分割が存在するかどうかの判定はNP完全である．以下では，NP完全性が [10]によって知られている，グラフが3彩色可能かどうかの判定問題 (3彩色問題と呼ぶ)から2-良いクリー ク分割が存在するかどうかの判定問題への多項式時間帰着が存在することを示す． 3彩色問題の入力のグラフをGとする．また，Knをn =|V (G)|頂点の完全グラフとする．Gから次のよ うなグラフH = (V, E)を構成する． V = V (G)∪ {x, y, z}, E = (E(Kn)\E(G)) ∪ F, F ={(u, v) | u ∈ {x, y, z}, v ∈ V }. すなわち，グラフH は，Gの補グラフに，その補グラフの頂点全てに隣接する3つの頂点x, y, zを加えたも のである．x, y, zは色に対応する．図15から図20は，GからH を作る例と，Gにおける3彩色とHにお ける2-良いクリーク分割の対応の図である． 図15 彩色の入力であるグラフG． 図16 Gの3彩色． 図17 Gの補グラフ(破線は元のグラフの辺)． 図18 Gの補グラフ(破線無し)． 定理10. Gが3彩色可能であることと，Hに2-良いクリーク分割が存在するかどうかは同値である． 証明. ある頂点がxと同じクリークに属したとき，その頂点はxで塗られたことと対応する．また，x, y, zが それぞれ隣接していないことから，Hのクリーク分割には必ず3つ以上のクリークが含まれている．さらに， x, y, zのどれも含まれていないクリークに属する頂点vが存在するとき，その頂点はx, y, zと隣接している

図19 Gの補グラフにx, y, zを加えたグラフH． 図20 Hにおける2-良いクリーク分割． から，_{|{q ∈ Q | ∃u ∈ N}+_{(v), u∈ q}| ≥ 3となり，2-良いクリーク分割は存在しない．したがって，2-良いク} リーク分割が存在するとき，全ての頂点はx, y, zのうちのどれかと同じクリークに属する．それらのクリーク を，qx, qy, qzとする．以上を踏まえて，Gが3彩色可能であることと，H に2-良いクリーク分割が存在する かどうかが同値であることを示す． Gが3彩色可能であるとき，Gの頂点は互いに異なる3つの独立集合X, Y, Zに分割される．このとき，G の補グラフでは，X, Y, Z頂点からなる誘導部分グラフはそれぞれ完全グラフとなっている．さらに，Xの頂 点とx，Y の頂点とy，Zの頂点とzは隣接しているから，X∪ {x}, Y ∪ {y}, Z ∪ {z}からなる誘導部分グラ フはそれぞれ完全グラフとなる．したがって，それらをクリーク分割とすれば，それは2-良いクリーク分割で ある． 逆に，Gが3彩色不能であるとき，Gの頂点を順番に1頂点ずつ彩色していくことを考える．そのとき，ど のように彩色しても，3色全てと隣接してしまうような，まだ塗られていない頂点が存在する．同様に，x, y, z を除いたH の頂点を，順番に1頂点ずつ，x, y, zのどの頂点と同じクリークに属するか選んでいくことを考 える．このとき，どのような選び方をしても，qx, qy, qzのそれぞれに属する3頂点a, b, cと隣接していないよ うな，まだ選ばれていない頂点vが存在する (Gで辺がある部分は，H では辺が無いことに注意する)．その とき，vはa, b, cのどれとも隣接していないことから，qx, qy, qzのどれにも属することはできない，したがっ て，2-良いクリーク分割は存在しない．

5

まとめと今後の課題

本研究では平等さを伴った多重リスト彩色問題について，最小値最大化問題として定式化し，その問題につ いて，まず困難性について明らかにした．具体的には，完全2部グラフ，星グラフ，および準完全グラフに 絞った場合でさえも，厳密解を求めることはNP困難であることを示した．さらに，一般グラフにおいては最 適値を定数で割ったものの切り下げ以上の解を保証することもNP困難であることを示した．次に，良いク リーク分割が与えられた場合に，多項式時間で最適値の半分の切り下げ以上の解を保証するアルゴリズムを提 案した．また，準完全グラフは良いクリーク分割が存在するグラフであることを，および，良いクリーク分割 が存在するグラフが理想グラフであることも示した．さらに，良いクリーク分割の一般化であるk-良いクリー ク分割について，k = 1のときのみ，そのような分割が存在するかを多項式時間で判定できることを示した． 今後の課題としては，アルゴリズムの適用範囲を広げることや，その他のグラフについての計算複雜性を示す ことが挙げられる．特に，周波数帯の割り当てに応用しようとした場合には，単位円グラフ等におけるアルゴ リズムを考えることが重要である．

参考文献

[1] Wei Wang and Xin Liu. List-coloring Based Channel Allocation for Open-Spectrum Wireless Net-works. IEEE 62nd Vehicular Technology Conference, pp. 690–694, 2005.

[2] Yurong Qin, Hongmei Hu, Dongli Huang, and Hao Lin. Improved list coloring algorithm in cognitive radio based on time cost and demand satisfaction. Radioelectronics and Communications Systems, Vol. 56, No. 11, pp. 528–533, 2013.

[3] Mishra Vishram, Lau Chiew Tong, and Chan Syin. List multi-coloring based fair channel allocation policy for self coexistence in cognitive radio networks with QoS provisioning. IEEE Region 10

Symposium, pp. 99–104, 2014.

[4] J. Ravi Sankar, Felix Augustin, G. Mokesh Rayalu, and M. Maria Sagaya Nathan. A Survey: List Coloring Problem. International Journal of Control Theory and Applications, pp. 245–249, 2016. [5] Nicholas J.A. Harvey, Richard E. Ladner, L´aszl´o Lov´asz, and Tami Tamir. Semi-matchings for

bipartite graphs and load balancing. Journal of Algorithms, Vol. 59, No. 1, pp. 53–78, 2006. [6] Sanjeev Khanna, Nathan Linial, and Shmuel Safra. On the Hardness of Approximating the

Chro-matic Number. The 2nd Israel Symposium on Theory and Computing Systems, 1993.

[7] Carsten Lund and Mihalis Yannakakis. On the hardness of approximating minimization problems.

Journal of the ACM, Vol. 41, No. 5, pp. 960–981, 1994.

[8] Martin Gr¨otschel, L´aszl´o Lov´asz, and Alexander Schrijver. Geometric Algorithms and Combinatorial

Optimization. Springer, 1988.

[9] Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas. The strong perfect graph theorem. Annals of Mathematics, Vol. 164, pp. 51–229, 2006.

[10] Richard M. Karp. Reducibility Among Combinatorial Problems. Complexity of Computer