多重彩色問題とチャネル割当問題の 近似解法 宮本裕一郎

多重彩色問題とチャネル割当問題の
近似解法
宮本 裕一郎
c 2006, 宮本 裕一郎.
Copyright °
i
論文要旨
本論文は多重彩色問題およびチャネル割当問題の近似解法について記したものである．多重
彩色問題およびチャネル割当問題はいずれも頂点彩色問題を特殊な場合として含む問題であ
る．本研究の主な成果をモデルの観点から述べる．多重彩色問題に関しては，入力グラフを限
定した場合にのみ，近似解法が知られていた．本研究では，入力グラフとしてより広いグラフ
クラスを扱い，近似解法を提案した．チャネル割当問題に関しては自明でない近似解法は知ら
れていなかった．本研究では，実務において現実的と思われる仮定を入力グラフに与えた場合
の（自明でない）近似解法を提案した．本研究の主な成果を解法の観点から述べる．本研究で
はパーフェクトグラフに着目し，パーフェクトとは限らないグラフを入力とした多重彩色問題
に対する効率的な解法を提案した．この解法は，格子状グラフを入力グラフとした場合には多
項式時間近似解法であり，良い近似率を達成する．チャネル割当問題に対しては，パーフェク
トグラフを入力とした場合の近似解法を提案し，それを基に，より広いグラフクラスの近似解
法を提案した．「パーフェクトグラフを，パーフェクトとは限らないグラフの近似解法に利用
する」という手法は，本研究の大きな特徴といえる．本研究では，問題の入力グラフとして，
格子状グラフおよび単位円グラフを扱っている．これらのグラフは，現実のチャネル割当問題
において多く現れるグラフであり，有名なベンチマーク問題である Philadelphia 問題例の入
力グラフを含む．
多重彩色問題に関する成果を以下に簡単にまとめる．本研究で提案した解法は，入力グラ
フが三角格子グラフの場合，その近似率がほぼ 4/3 の多項式時間近似解法となる．この近似
率は，得られる彩色の上界の見積もりに関し定数項を除けば，既存の最良の近似率と同じで
ある．三角格子グラフの多重彩色問題に対して，近似率が 4/3 より小さい多項式時間近似解
法があるならば P=NP となることが，既存の結果からわかっている．本研究で提案した多
項式時間近似解法は，入力グラフが三角格子点上の単位円グラフの場合には，近似率がほぼ
j
k j √
k
2 −3
/ 3+ 4d
となり，入力グラフが四角格子点上の単位円グラフの場合には，そ
2
j√ k
の近似率がほぼ 1 + bdc/ 23 d となる，ここで d は単位円の直径である．また，入力グラフ
1+
√2 d
3
が三角格子グラフの k 乗グラフの場合には，その近似率がほぼ (2k + 1)/(k + 1) となり，入
力グラフが四角格子グラフの k 乗グラフの場合には，その近似率がほぼ 1 + k/
¥ k+3 ¦
2
のとな
る．本研究で提案した解法は，入力グラフが三角格子グラフの 2 乗グラフの場合，既存の解法
の近似率 7/3 より勝っている．各グラフに対する近似率は，各グラフがパーフェクトである条
件を整理した定理により導かれる．その定理により，各グラフの最大重み安定集合問題の近似
ii
論文要旨
解法，各グラフの有理彩色数の見積もり，各グラフの非パーフェクト率の見積もりなども得ら
れた．一方，対角格子グラフの多重彩色問題が NP-困難であることも示した．
最小スパンチャネル割当問題に関する成果を以下に簡単にまとめる．入力グラフの枝の重み
が全て同じチャネル割当問題を解く多項式時間近似解法を提案した．その解法は，入力グラフ
がパーフェクトグラフグラフまたは単位円グラフの場合には O(log n)-近似解法になる，ここ
で n は入力グラフの頂点数である．また，この解法を基に，一般のグラフに対する O(n)-近似
解法も提案した．これらの解法の基となるアイディアは，枝の重みが全て同じとは限らない問
題クラスに対しても適用可能である．その例として Philadelphia の問題例を含む問題クラス
を定義し，その近似解法も示した．また，入力グラフが単位円グラフで，枝の重みに現実的な
仮定が与えられた場合の近似解法を提案した．
iii
目次
i
論文要旨
第1章
はじめに
1
1.1
背景と目的 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
本論文の構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.3
従来研究と本論文の関連 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.4
最小スパンチャネル割当問題および格子状グラフについて . . . . . . . . . .
5
第2章
10
基本的な用語と記号
2.1
グラフの基本用語
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
2.2
彩色問題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.3
パーフェクトグラフ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.4
単位円グラフ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
2.5
格子状グラフ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
2.6
近似解法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
2.7
調和数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
格子状グラフの多重彩色問題
16
3.1
格子グラフと多重彩色問題の定義 . . . . . . . . . . . . . . . . . . . . . . .
17
3.2
パーフェクトグラフと非パーフェクトグラフの整理 . . . . . . . . . . . . . .
18
3.3
有理彩色と非パーフェクト率
. . . . . . . . . . . . . . . . . . . . . . . . .
33
3.4
最大重み安定集合問題の多項式時間近似解法 . . . . . . . . . . . . . . . . .
36
3.5
多重彩色問題の多項式時間近似解法 . . . . . . . . . . . . . . . . . . . . . .
37
3.6
各種格子状グラフの多重彩色問題の計算困難性 . . . . . . . . . . . . . . . .
41
3.7
パーフェクトグラフを利用した解法の枠組み . . . . . . . . . . . . . . . . .
45
3.8
まとめと考察 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
チャネル割当問題
50
4.1
チャネル割当問題の定義 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
4.2
枝の重みが全て同じ場合のチャネル割当問題の近似解法 . . . . . . . . . . .
51
4.3
Philadelphia 問題例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
第3章
第4章
iv
目次
4.4
単位円グラフのチャネル割当の近似解法 . . . . . . . . . . . . . . . . . . . .
62
4.5
まとめと考察 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
67
まとめと考察
69
第5章
謝辞
71
参考文献
72
1
第1章
はじめに
1.1 背景と目的
本論文の目的は多重彩色問題とチャネル割当問題の多項式時間近似解法を論じることであ
る．特に強 NP-困難であることが知られている多重彩色問題とチャネル割当問題それぞれに
対して，多項式時間近似解法を構築できる条件を整理し，実務において現実的と思われる仮定
の下で多項式時間近似解法を提案する．
通信機に周波数を割り当てる問題として周波数割当問題がある．周波数割当問題は 1960 年
代には既に知られていたが，1990 年代に入り移動体通信網が発達するに従って，その社会的重
要性は増してきている．この周波数割当問題を離散的にモデル化した問題としてチャネル割当
問題が知られている．最小スパンチャネル割当問題は，チャネル割当問題の中でも特に多重彩
色問題をその特殊な場合として含む最小スパンチャネル割当問題は計算困難な問題として知ら
れている．本研究は，この多重彩色問題と最小スパンチャネル割当問題を対象としている．最
小スパンチャネル割当問題に対しては，1970 年代に Philadelphia 問題例が紹介されて以来，
組合せ最適化問題として多くの研究がなされてきた．最小スパンチャネル割当問題の問題例と
して現場から生じたものが数多く知られており，それら問題例の入力グラフには特徴がある．
その特徴を良く表しているのが三角格子グラフや単位円グラフである．最小スパンチャネル割
当問題の理論的難しさを残しつつ単純化した問題として「三角格子グラフの多重彩色問題」や
「単位円グラフの彩色問題」がある．三角格子グラフの多重彩色問題および単位円グラフの彩
色問題は最小スパンチャネル割当問題の単純化であるが，それでもなお NP-困難であり，多項
式時間近似解法の構築に焦点を当てた研究が多い．
三角格子グラフの多重彩色問題に対しては多項式時間 (4/3)-近似解法が提案されている．し
かし三角格子グラフは，現実に現れる問題のモデルとしては単純すぎ，実務には適さない場面
も多い．もう少し複雑なグラフの多重彩色問題に対する多項式時間近似解法を構築できるだろ
うか，という興味が本研究の動機の 1 つである．単位円グラフの頂点彩色問題に対しては多項
式時間 3-近似解法が提案されている．しかし，現在知られている 3-近似解法においてその近
似率を 3 より小さくできないことを示す問題例（タイトな問題例）は見つかっていない．さら
に，簡単な計算実験により実際の近似精度は 3 よりかなり良いことが確認できる．以上より
2
第 1 章 はじめに
「近似率が 3 よりも小さい多項式時間近似解法があるのでないか」と予想されている．単位円
グラフの頂点彩色問題の，より良い近似解法を提案する事も本研究の動機の 1 つである．
以上の動機を踏まえ，3 章では三角格子点上の単位円グラフの多重彩色問題を扱っている．
三角格子点上の単位円グラフは三角格子グラフを特殊な場合として含む．そして Philadelphia
問題例の入力として現れるグラフも特殊な場合として含む．本研究で扱っているグラフは，従
来研究で扱っているグラフを拡張し，より現実の問題に近づけたものと位置づけられる．三角
格子点上の単位円グラフは単位円グラフの特殊な場合である．しかし，任意の単位円グラフが
与えられたとき，十分細かな三角格子と適切な大きさの単位円を用意すれば，与えられた単位
円グラフを三角格子点上の単位円グラフとして表すことができる．よって，三角格子点上の単
位円グラフの多重彩色問題の多項式時間近似解法は，単位円グラフの頂点彩色問題の多項式時
間近似解法の構築に示唆を与えると思われる．
本研究の目的は，従来研究で提案されている解法よりも適用範囲の広い解法を提案すること
である．得られた結果として，三角格子グラフの k 乗グラフ，四角格子点上の単位円グラフ，
四角格子グラフの k 乗グラフにおける多重彩色問題の多項式時間解法がある．四角格子は従
来研究では扱われていなかったものである．そのため，例えば四角格子点上の単位円グラフの
多重彩色問題が計算困難な問題であることは自明ではなく，本研究ではこの問題が NP-困難で
あることも示す．また，本研究で提案する手法の適用範囲の広さを示すため，上記のグラフに
おける有理多重彩色問題，非パーフェクト率，最大重み安定集合問題なども扱う．
4 章では最小スパンチャネル割当問題を扱う．3 章で提案する多重彩色問題の多項式時間近
似解法を構築する際の枠組みは最小スパンチャネル割当問題の多項式時間近似解法の構築にも
用いることができる．すなわち 4 章では，パーフェクトグラフ，単位円グラフ，Philadelphia
問題例の入力グラフなどを取り上げ，最小スパンチャネル割当問題の多項式時間近似解法を提
案する．最小スパンチャネル割当問題の多項式時間近似解法の既存研究はなく，本研究の意義
は大きいと思われる．
1.2 本論文の構成
本論文の構成は以下の通りである．以下本章では本論文の内容に関連する従来研究を紹介
し，その中での本論文の位置づけを述べる．2 章では本論文で使う用語と記号について説明す
る．3 章では多重彩色問題の近似解法に関する研究成果を述べる．4 章では最小スパンチャネ
ル割当問題の近似解法に関する研究成果を述べる．5 章では本論文の成果をまとめ今後の課題
について述べる．
1.3 従来研究と本論文の関連
彩色問題の研究は，1850 年代の「平面に描かれた地図は必ず 4 色で塗り分けられるか」と
いう問いかけから始まったと言われている．この問いかけは 4 色予想とよばれた．多重彩色問
題がいつから研究されているのか定かではないが，彩色問題の最も素直な拡張の 1 つであるた
1.3 従来研究と本論文の関連
3
め，古くから研究されていたであろうと想像される．実際，多重彩色問題は擬多項式時間で彩
色問題に帰着できるため，計算量を気にしなければ両者の研究に差異はない．
計算量，特に計算困難性，が意識され盛んに研究され始めたのは 1970 年頃のことである．
1971 年に Cook は，充足可能性問題が NP-完全であることを証明した [17]．それ以降，組合
せ最適化問題を「多項式時間で解けるもの」か「NP-完全（あるいは困難）」かに二分して議
論することが多い．1972 年に Karp は「グラフが k 彩色可能か否か判定する問題は NP-完全
である」と示した [38]．この結果は頂点彩色問題が NP-困難であることを意味している．さ
らに 1976 年には Garey, Johnson, Stockmeyer が「平面グラフが 3 彩色可能か否か判定する
問題は NP-完全である」と示した [25]．この結果は，グラフに制限を加えてもなお彩色問題
は NP-困難であることを意味する．本論文の 3 章で「対角格子グラフの多重彩色問題は NP困難である」と示しているが，そこではこの結果を利用している．なお 4 色予想が 4 色定理と
して肯定的に証明されたのは 1977 年である [7, 8]．1970 年代には多くの組合せ最適化問題が
NP-困難であると証明された．1979 年には代表的な NP-完全問題が Garey, Johnson によっ
てまとめられている [24]．1980 年代，1990 年代には NP-困難問題の近似解法が多数提案さ
れた．これら近似解法のうち本研究に関連するものは後で詳しく述べる．NP-困難問題に多項
式時間解法があるか否か，俗にいう P=NP 問題，は 2005 年現在でも解決されていない．し
かし P=NP ではないと信じている研究者が多いと言われている．1992 年には Arora, Lund,
Motowani, Sudan が彩色問題に関して，P=NP でない限り，任意の ² に対して O(n² )-近似解
法が存在しないことを示した [9]．ここで n はグラフの頂点数である．これにより一般のグラ
フの彩色問題は近似困難であると理論的に確認されたと言える．1998 年に Karger, Motwani,
Sudan が提案した彩色問題の近似解法は半正定値計画緩和を用いた画期的なものであるが，そ
の近似率は k-彩色グラフに対して O(min{∆1−2/k log1/2 ∆ log n, n1−3/(k+1) log1/2 n}) であ
る [37]，ここで n, ∆ はそれぞれグラフの頂点数と最大次数である．一般のグラフの彩色問題
は NP-困難であり近似困難なので「どのようなグラフならば効率的に彩色できるか」という問
いかけに関し，多くの研究がなされている．
彩色数に関して美しい特徴付けが存在するグラフのクラスとしてパーフェクトグラフが研
究され始めたのは 1960 年代のことである．当時は計算困難性の明確な指標はまだなかった
が，一般のグラフの彩色数を求める問題は解きづらいということは認識されていた．1963 年
に Berge は「全ての誘導部分グラフにおいて彩色数とクリーク数が一致するグラフ」をパー
フェクトグラフとして定義し，パーフェクトグラフに関するいくつかの予想を立てた．予想の
1 つは 1972 年に Lovász [42] によって肯定的に示された「パーフェクトグラフの補グラフは
パーフェクトグラフである」という弱パーフェクト定理である．この定理は本論文の 3 章で直
接あるいは間接的に用いられている．1981 年に Grötschel, Lovász, Schrijver はパーフェクト
グラフを多項式時間で最適彩色可能であると示した [31]．その証明では最適彩色する解法が提
案されており，その解法を使えばパーフェクトグラフ上の多重彩色問題も多項式時間で解くこ
とができる [59]．この結果は 3 章で用いられている．Grötschel, Lovász, Schrijver はその解
法の中で楕円体法を用いているが，近年開発された，半正定値計画問題を解く内点法を用いれ
ばより効率的である．なお 2005 年現在，パーフェクトグラフを多項式時間で彩色する組合せ
4
第 1 章 はじめに
的解法はまだ提案されていない．これは当該分野の未解決問題の 1 つである．パーフェクトグ
ラフとそのアルゴリズムに関しては Golumbic の著書 [29] などを参照されたい．
彩色問題には様々な拡張があり，Jensen, Toft [36] の著作や Kubale の著作 [41] で多数
紹介されている．多重彩色問題は彩色問題の拡張の 1 つであるが，別の拡張として最小スパ
ンチャネル割当問題がある．最小スパンチャネル割当問題は 1973 年に Anderson によって
Philadelphia 問題例として紹介されている [6]．最小スパンチャネル割当問題は様々なチャネ
ル割当問題 (channel assignment problem) のうちの 1 つである．チャネル割当問題は周波数
割当問題 (frequency assignment problem) ともよばれるが，本論文ではチャネル割当問題と
呼ぶことにする．チャネル割当問題の歴史，問題の種類，解法については ZIB (Zuse Institute
Berlin) の研究グループによる報告書 [1, 40] に詳しく記されている．最小スパンチャネル割当
問題の定義は 4 章で述べるが，簡単に説明すると「電波の干渉制約と，各基地局で必要とされ
るチャネル数が条件として与えられたとき，使うチャネルの範囲（スパン）を最小にするよう
に各基地局にチャネルを割り当てる問題」である．最小スパンチャネル割当問題のベンチマー
ク問題の 1 つである Philadelphia 問題例は 1970 年代初頭から知られていたにもかかわらず，
その最適解が得られたのは 1990 年代終盤である．問題の困難性のため計算機および解法の進
歩を待たなければならなかったのであろう．特に，1990 年代の半ばになって携帯電話が普及
し始め，実用における問題の重要性が増したことも大きな理由になっていると思われる．チャ
ネル割当問題のポータルサイトである FAP WEB*1 で紹介されている文献の数は 1970 年代
は 10 本，1980 年代は 18 本，1990 年から 1995 年までは 54 本，1996 年から 2000 年までは
133 本，2001 年から 2005 年までは 71 本であり，1990 年代の後半に特に多いことがわかる．
Philadelphia の問題例は 9 問あり発見的に下界を見つける方法 [23, 61] と発見的に上界を見
つける方法 [62, 60, 5, 35, 11, 12, 44] によってその全ての最適解が分かっている．実務におい
ては最良解を得ることが重要であるため，チャネル割当問題の研究のほとんどは発見的解法の
研究である．本論文の主題は近似解法であり，発見的方法に関して詳しく紹介はしない．
本論文ではチャネル割当問題のうち最小スパンチャネル割当問題のみを扱うので，以下では
最小スパンチャネル割当問題をチャネル割当問題と略すことにする．チャネル割当問題の典型
的な単純化として「単位円グラフの彩色」と「三角格子グラフ（およびその拡張グラフ）の多
重彩色」がある．以下，これらの問題の従来研究について述べる．Philadelphia 問題例では電
波の干渉制約は頂点間の距離に依存しており，単位円グラフで表されている．そしてチャネル
割当問題は彩色問題を特殊な場合として含む．これが単位円グラフの彩色問題の研究の動機に
なったと思われる．1995 年に Marathe, Breu, Hunt, Ravi, Rosenkrantz は単位円グラフの
彩色問題が NP-困難であることを示し，3-近似解法を示した [43]．それとは独立に示された 3近似解法もある [30, 32, 18]．簡単な数値計算実験により，これらの解法によって実際に得ら
れる解は最適値の 3 倍よりかなり小さいことが確認できる．最適値の 3 倍の値が出力される
問題例（タイトな問題例）は見つかっておらず近似解法の近似見積もりが十分でないと予想さ
れている．しかし，より良い近似率を持つ解法は 2005 年現在見つかっていない．単位円グラ
*1
http://fap.zib.de/
1.4 最小スパンチャネル割当問題および格子状グラフについて
5
フの彩色問題のより良い近似解法を見つけることが本論文の動機の 1 つとなっている．
単位円グラフに関する彩色問題以外の研究も紹介する．1983 年に Hochbaum は幾何詰め込
み問題の PTAS を示した [32]．その論文に現れる単位四角グラフは L1 ノルム上の単位円グ
ラフと見なせる．1990 年に Clark, Colbourn, Johnson [16] が単位円グラフの最大クリーク
は多項式時間で見つかるが，最大安定集合問題は NP-困難であることを示している．1998 年
に Breu, Kirkpatrick [13] は「与えられたグラフが単位円グラフか否か判定する問題は NP完全である」ということを示した．その結果は「単位円グラフの頂点の座標を決める解法は，
単位円グラフか否かの判定法として，そのまま使えること」を意味している．2000 年には
Matsui [45] が単位円グラフの最大安定集合問題の PTAS (Polynomial Time Approximation
Scheme) を示した．2004 年には Nieberg, Hurink, Kern [55] が単位円グラフの最大重み安定
集合問題の PTAS を提案した．Nieberg, Hurink, Kern の方法は，「グラフの頂点の座標を必
要としない」という意味で頑健なものになっている．
Philadelphia 問題例の頂点の座標（基地局の位置）は三角格子点に限られている．これが三
角格子グラフの多重彩色問題の研究の動機になったと思われる．Philadelphia 問題例の電波
干渉を表すグラフは三角格子点上の単位円グラフであり，三角格子点上の単位円グラフの特
殊な場合として三角格子グラフがある．そしてチャネル割当問題の枝の重みを 1 に限定した
特殊な場合が多重彩色問題である．2000 年に McDiarmid, Reed [47] は三角格子グラフの多
重彩色問題が NP-困難であることを示し (4/3)-近似解法を提案した．2001 年に Narayanan,
Shende [54] は別な (4/3)-近似解法を提案している．1998 年に Feder, Shende [20] は三角格
子グラフの 2 乗グラフの多重彩色問題の (7/3)-近似解法を提案した．
本論文の 3 章で提案している解法の特徴の 1 つとして「問題を複数の層状部分問題に分け，
個別に解き，得られた複数の解を統合する」ことが挙げられる．これは幾何学的な問題に対す
る分割統治法の一種と捉えることができる．平面に埋め込まれたグラフ上で定義された組合
せ最適化問題において，グラフを層状の部分グラフに分けるという手法は 1980 年代にすでに
見られる．1983 年に Hochbaum [32] は幾何的詰め込み問題を複数の小矩形の部分問題に分
けて解き，得られた解を統合して元の問題の近似解を得る方法を提案している．これは後に
Hochbaum によって shifting strategy と名付けられている [33]．1994 年には Baker が平面
グラフの組合せ最適化問題において，外側からドーナツ状にグラフを分割し部分問題を解いて
近似解を出す方法を提案している [10]．2000 年に Matsui が提案した単位円グラフの最大安
定集合問題の PTAS [45] では，問題を帯状の部分問題に分解し，得られた解を統合している．
なお，4 章で提案している解法の多くも分割統治法の一種と捉えることができるが，その分割
法は既存の研究や 3 章の方法と異なるものとなっている．
1.4 最小スパンチャネル割当問題および格子状グラフについて
本節では，最小スパンチャネル割当問題が生じた背景を詳しく述べる．また，最小スパン
チャネル割当問題の問題例に多く現れる格子状グラフについても述べる．本節の内容の多く
は，Aardal らによる包括的な概説論文 [1]，及び移動通信に関するハンドブック [58] に依って
6
第 1 章 はじめに
いる．
無線通信に使われる周波数帯域は各国政府や ITU (International Telecommunication
Union) によって定められている．無線通信で用いられる周波数帯域と主な用途を表 1.1 に記
す．無線通信を使う者はその定められた範囲の中でさらに許可された周波数帯を使う．ある無
表 1.1. 無線通信で用いられる周波数帯域と主な用途 [58]
周波数帯域
主な利用周波数
主な用途
MF 帯（300kHz∼3MHz）
航空無線航行，漁業無線，海上保安など
HF 帯（3MHz∼30MHz）
船舶及び航空機の通信，市民ラジオなど
VHF 帯
小型船舶用無線など
40MHz 帯
（30MHz∼300MHz） 60MHz 帯
UHF 帯
（300MHz∼3GHz）
SHF 帯
（3∼30GHz）
EHF 帯
（30∼300GHz）
防災行政無線，電車・バス事業用無線など
150MHz 帯
警察・消防用無線，国際沿岸無線電話など
250MHz 帯
コードレス電話，沿岸船舶無線電話など
400MHz 帯
警察・消防用無線，タクシー無線など
800MHz 帯
携帯・自動車電話，地域防災行政無線など
1.4∼1.6GHz 帯
ディジタル移動通信，GPS，静止衛星通信など
1.9∼2.2GHz 帯
PHS，ディジタルコードレス電話など
2.5GHz 帯
アマチュア無線，構内無線，警察用無線など
5GHz 帯
ETC，無線 LAN など
19∼20GHz 帯
無線 LAN など
60GHz 帯
特定小電力無線局ミリ波レーダー
帯など
など
線通信事業者が使うことを許された周波数帯域が [fmin , fmax ] であるとすると，その周波数帯
域はさらに幅 ∆ の周波数帯（いわゆるチャネル）に分割されて無線通信に使われる．このた
めチャネルは通常 1 から N に番号付けされて識別される，ここで N = (fmax − fmin )/∆ で
ある．使えるチャネルは F = {1, . . . , N } で表される．無線事業者が使える周波数帯域が複数
ある場合は，使えるチャネルは，連続する整数からなる有限集合をいくつか併せたものとして
表される．例えば使えるチャネルは F = {1, . . . , N1 , N2 + 1, . . . , N3 } という集合で表される
が，このような場合，複数の周波数帯域が互いに影響しないように N1 << N2 となっている
ことが多い．
無線電波通信における電波の干渉は，通信の受信側で雑音を生じる．通信の品質を保つため
には受信側の雑音，すなわち受信時の電波の干渉が十分小さい必要がある．雑音（電波の干
渉）は，第三者から発せられた電波が比較的近い周波数である場合に生じる．一般に干渉の強
さは，周波数が離れると，急速に小さくなる．しかし，干渉の強さは，周波数の離れ具合だけ
でなく，発信源の電波出力の強さ，地形などの環境，天候などにより変化する．そのため受信
側の干渉の強さをあらかじめ正確に知ることは難しい．よって多くの状況では，地形や天候な
1.4 最小スパンチャネル割当問題および格子状グラフについて
7
どの要素を無視し，アンテナは全方向に同じ強度で電波を出力するとモデル化することが多
い．以下では，同じ周波数で発せられる 2 つの電波 f, f 0 の干渉について簡単に記す．受信機
が f を受信したい場合，f 0 が干渉する強さは
P
dγ
に比例する，ここで P は f 0 が送信されると
きの電波の強さ，d は f 0 の送信機と受信機の距離である．γ は 2 から 4 の値をとる係数であ
る．この係数 γ の値は f 0 の周波数に依存する．一般に周波数の大きい電波ほど減衰しやすい
ので，周波数の大きい電波ほど干渉の強さが減る速さが速い（すなわち γ が大きい）
．f 0 と f 0
のチャネルが n(≥ 1) 離れている場合，− log2 n に比例して干渉の強さは減少する．以上は 1
対の電波が起こす干渉に関する性質であり，複数の電波が存在する場合には，干渉の強さの変
化はより複雑になる．しかし多くの研究では，電波対ごとの干渉が許容範囲にあるか否か議論
していることが多い．これは，電波対ごとの干渉を許容範囲に収めることが，実際の通信にお
ける雑音軽減の良い近似になっていることによる．なお，複数電波の干渉を考慮に入れた研究
もある [21]．
以上の考察を基に，平面に配置された複数のアンテナの電波干渉をグラフで表現する．グラ
フの頂点をアンテナとし，電波干渉の強さがある閾値以上の頂点対（アンテナ対）を枝とする
グラフを，電波干渉を表すグラフとする．このグラフは，近似的に，平面に埋め込まれた円グ
ラフ (disk graph) となる．特に，アンテナの電波出力の強さがほぼ同じ場合には単位円グラ
フ (unit disk graph) となる．
無線移動通信では，1 つの基地局がカバーする範囲をセル (cell) と呼ぶ．故にセルラー通信
網と呼ばれることも多い．通常，1 つの基地局がカバーできる平面領域は円で近似できる．複
数のアンテナを規則的に並べて平面をカバーする場合には，平面を正多角形で分割してセルを
構成することが多い．これを正則セル構成と呼ぶ．平面を分割できる正多角形分割のうち，最
も円に近いのは正六角形であるため，無線移動通信では正六角形のセルが用いられることが多
い．すなわち，基地局は正六角形の中心に置かれる．結果として基地局は三角格子点状に配置
されることになる．特に都市平野部では規則正しく三角格子点上に基地局が配置されている
（海，川，山間部などはこの限りではない）．なお，携帯電話の基地局などの配置は規則正しい
ものであるが，軍事目的の無線移動通信ではこの限りではない．
以上をふまえて，1973 年に Philadelphia 問題例がモデル化された [6]．これは当時の自動車
電話の基地局のチャネル割当問題をモデル化したものである．以下 Philadelphia 問題例につ
いて解説する．Philadelphia 問題例は，図 1.1 のような 21 個のセルを持ち，基地局は各セルの
中心に配置されている（結果として基地局は三角格子点上に配置されていることになる）．一
つの基地局が一度に通信をできる数，すなわち割り当てられなければならないチャネル数，が
与えられている．割り当てられなければならないチャネル数は基地局によって異なる．図 1.1
に，各セル（基地局）に割り当てられるべきチャネル数の一例を示す．Philadelphia 問題例は
全部で 9 個の問題例からなる．どの問題例においてもセルの数は 21 と定まっているが，各セ
ルに割り当てられるべきチャネル数が問題例により異なっている．携帯電話などの使用者が通
信を行おうとしたとき，割り当てるべきチャネル数が足りないという理由で通信が成り立たな
い確率を呼損率という．携帯電話などの通信事業者は呼損率が定められた値以下でなければな
らないと法律で定められている．よって通信の需要が多い場所をカバーする基地局にはたくさ
8
第 1 章 はじめに
32 100 32
60
32
70 208 308 112 52
32
60
124 60 144 228 112 32
40
52
32
図 1.1. 21 個のセルと各セル（基地局）に割り当てるべきチャネル数
んのチャネルを割り当てなければならない．以上の理由により，基地局に割り当てなければな
らないチャネル数は，基地局によって異なるのが通常である．Philadelphia 問題例における詳
しい数値は 4.3 節を参照されたい．同じ基地局に割り当てられるチャネルは，電波干渉を防ぐ
ため，大きく離れていなければならない．Philadelphia 問題例ではその値は 5 とされている．
チャネル数や電波発信源が離れれば，電波の干渉は小さくなる．Philadelphia 問題例では，
チャネルを離す数ごとに，チャネルを割り当ててよい距離を定めた．これを再利用距離 (reuse
distance) という．例えば，2 離れたチャネル対は
√
3 以上離れたセル対に割り当ててよい，と
いったものである．Philadelphia 問題例ではセル間の距離を「セルの中心間のユークリッド距
離」で定義し，隣接するセル間の距離を単位距離（距離 1）としている．Philadelphia 問題例
√
の再利用距離の一例として「0 離れたチャネル対は 2 3 以上離れたセル対に割り当ててよい，
1 離れたチャネル対は
√
3 以上離れたセル対に割り当ててよい，2 離れたチャネル対は 1 以上
離れたセル対に割り当ててよい，3 離れたチャネル対は 1 以上離れたセル対に割り当ててよ
い，4 離れたチャネル対は 1 以上離れたセル対に割り当ててよい，5 以上離れたチャネル対は
同一セルに割り当ててよい」がある．Philadelphia 問題例以外にも，再利用距離を用いてモデ
ル化されている問題例があるが，その数値は Philadelphia 問題例と大差ないものになってい
ることが多い．Philadelphia 問題例の目的関数は 2 種類ある．すなわち各入力に対し 2 つの
問題がある．1 つは最小スパン目的関数であり，使われるチャネルの最大値と最小値の差の最
小化である．もう 1 つは最小干渉目的関数であり，この場合は使えるチャネル集合が制約条件
になっており，目的は再利用距離の制約を破るチャネル対の数の最小化である．Philadelphia
問題例は 1970 年代のものであるが，2005 年現在でも携帯電話の基地局はほぼ三角格子点状に
並んでおり，それぞれの基地局が通信を担当する範囲はほぼ正六角形になっている．
ここまでは，基地局が発する電波に関してのみ論じてきたが，携帯電話に代表される多くの
無線電波通信では，基地局から移動端末への通信（下り通信）と移動端末から基地局への通信
（登り通信）が同時に行われる．一般に，同時に行われる通信では，特にチャネルを大きく離
す必要がある．そのため，下り通信でチャネル c が割り当てられた場合に登り通信では c + N
を割り当てる方式が一般的である，ここで N は十分大きな値である．登り通信と下り通信に
1.4 最小スパンチャネル割当問題および格子状グラフについて
9
おける，このような割当方法には現場での運用のしやすさも関係していると思われる．このよ
うな運用状況を考慮して，最小スパン割当問題を含む，多くのチャネル割当問題では下り通信
のみを考えて入力データを作ることが多い．例えば，最小スパンチャネル割当問題の解で用い
られるチャネル数が 100 ならば，現場では 200 チャネル使って双方向通信することになる．
本論文 4 章で取り扱う最小スパンチャネル割当問題は，以上の状況をふまえて，チャネル割
当問題を離散最適化問題としてモデル化したものである．最小スパンチャネル割当問題の詳細
な定式化は 4.1 節を参照されたい．また，上記で述べた理由から，最小スパンチャネル割当問
題の入力グラフとしては（単位）円グラフおよびその特殊な場合である格子状グラフが多く研
究されている．単位円グラフの定義に関しては 2.4 節を，格子状グラフに関しては 3.1 節を参
照されたい．
10
第2章
基本的な用語と記号
本章ではグラフ理論および近似解法における基本的な用語と記号を説明する．組合せ最適化
問題とその近似解法で使う用語は文献によって異なることも多い．記号に関しても同様であ
る．以下では本論文で採用する用語と記号を説明する．重要な用語に関しては対応する英語も
記す．
2.1 グラフの基本用語
本論文ではグラフ (graph) のうち，自己閉路 (loop) と並行枝（多重枝）(parallel edges) を
含まないグラフ，すなわち単純グラフ (simple graph) だけを扱う．よって単純グラフをグラ
フと略す．グラフ G の頂点集合を V [G] で，枝集合を E[G] で表す．グラフ G = (V, E) が
与えられたとき，頂点部分集合 H ⊆ V により誘導される点誘導部分グラフ (vertex induced
subgraph) を G[H] で表す．本論文では誘導部分グラフのうち点誘導部分グラフだけを扱う．
よって点誘導部分グラフを誘導部分グラフと略す．
グラフ G = (V, E) の誘導部分グラフ G[H] が完全グラフであるとき，H ⊆ V を G のク
リーク (clique) という．クリークの要素数（頂点数）をクリークの大きさ (clique size) とい
う．グラフ G のクリークのうちその大きさが最も大きいものを G の最大クリーク (maximum
clique) という．グラフ G の最大クリークの大きさを G のクリーク数 (clique number) とい
う．本論文では G のクリーク数を ω(G) で表す．
グラフ G = (V, E) の誘導部分グラフ G[H] に枝がないとき，H ⊆ V を G の安定集合
(stable set) あるいは独立集合 (independent set) という．本論文では安定集合と呼ぶことに
する．安定集合の要素数（頂点数）を安定集合の大きさという．グラフ G の安定集合のうち
その大きさが最も大きいものを G の最大安定集合 (maximum stable set) という．グラフ G
の最大安定集合の大きさを G の安定数 (stable number) という．本論文では G の安定数を
α(G) で表す．
2.2 彩色問題
11
2.2 彩色問題
グラフ G = (V, E) が与えられたとき，隣接する頂点同士は異なる値となっている自然数の
割当 c : V → N を G の頂点彩色 (vertex coloring) という．割り当てられた自然数を「色」
と呼ぶこともある．k 色以下しか使わない頂点彩色を k-彩色 (k-coloring) という．グラフ
G = (V, E) の頂点彩色 c のうち，使われている色数 |{c(v) | v ∈ V }| が最小の頂点彩色を見
つける問題を G の頂点彩色問題 (vertex coloring problem) という．頂点彩色問題は
minimize
subject to
max c(v)
v∈V
c(u) 6= c(v), ∀{u, v} ∈ E,
c(v) ∈ N, ∀v ∈ V
と定式化することができる．彩色問題には他にも様々な変種が存在するが，本論文では彩色問
題のうち頂点彩色問題だけを扱うので，頂点彩色問題を彩色問題と略す．彩色問題の最適値を
彩色数 (coloring number) あるいは染色数 (chromatic number) という．本論文では彩色数と
呼ぶことにする．グラフ G の彩色数を χ(G) で表す．
平面グラフの彩色数は 4 以下であることが知られている．いわゆる 4 色定理である．4 色
定理は 1977 年に Appel, Haken [7, 8] によって証明された．1997 年に Robertson, Sanders,
Seymour, Thomas [57] はその証明を少し簡略化した．これらの証明から，平面グラフを 4 色
で彩色する方法が直ちに得られる．その方法は単純なものではないが計算量は O(|V |2 ) であ
る [56]．平面グラフの彩色に関しては Nishizeki, Chiba による著作 [56] に詳しい．
2.3 パーフェクトグラフ
任意の誘導部分グラフのクリーク数と彩色数が一致する，すなわち ∀V 0 ⊆ V, ω(G[V 0 ]) =
χ(G[V 0 ]) を満たすグラフをパーフェクトグラフ (perfect graph) という．パーフェクトグラフ
は 1960 年代に Berge によって定義された． パーフェクトグラフの邦訳として理想グラフ，完
璧グラフなどが用いられる場合もあるが，本論文ではパーフェクトグラフと呼ぶことにする．
形容詞的に「グラフ G はパーフェクトである」ということもある．本論文ではパーフェクト
でないグラフを非パーフェクトグラフと呼ぶ．図 2.1 にパーフェクトグラフと非パーフェクト
グラフの例を示す．
頂点数 n の連結グラフのうち全ての頂点の次数が 2 のものを閉路 (cycle) といい，Cn で表
す．k が 5 以上の奇数のとき閉路 Ck はパーフェクトでない．与えられたグラフ G の誘導部
分グラフのうち Ck （k は 5 以上の奇数）と同型なものを G の奇ホール (odd hole) という．
パーフェクトグラフの定義より，奇ホールを誘導部分グラフとして持つグラフはパーフェクト
でない．誘導部分グラフのうち Ck （k は 5 以上の奇数）の補グラフと同型なものを奇反ホー
ル (odd anti-hole) という．奇反ホールを誘導部分グラフとして持つグラフもパーフェクトで
ない．奇ホールや奇反ホールの頂点数が k のときは，k 奇ホール，k 奇反ホールなどと呼ぶこ
12
第2章
基本的な用語と記号
図 2.1. パーフェクトグラフ（左）と非パーフェクトグラフ（右）の例
ともある．
パーフェクトグラフに関しては，「パーフェクトグラフの補グラフはパーフェクトグラフで
ある」という弱パーフェクト定理 (perfect graph theorem) が，1972 年に Lovász によって証
明された [42]．また 2002 年には，
「奇ホールも奇反ホールも誘導部分グラフとして含まないこ
ととパーフェクトグラフであることは同値である」という強パーフェクト定理 (strong perfect
graph theorem) が，Chudnovsky, Robertson, Seymour, Thomas によって証明された [15]．
奇ホールも奇反ホールも誘導部分グラフとして含まないグラフは Berge グラフともよばれる．
これは強パーフェクト定理を予想した Berge に敬意を表したものである．
1981 年に Grötschel, Lovász, Schrijver は，パーフェクトグラフは強多項式時間で最適彩色
できることを証明した [31]．彼らの証明で提案されている解法は，Lovász 数 ϑ(G) を繰り返
し求めるものであり，ϑ(G) を求めるために楕円体法を用いている．その計算量は（Lovász 数
ϑ(G) を高々 O(|V (G)|3 ) 回求めればよいので）O(|V (G)|12 ) であるが，楕円体法は理論的な
精度を保証するためには，多倍長演算を実装する必要があり，実用的でないと考えられてい
る．より実用的な解法として，近年その進歩が著しい半正定値計画問題を用いて ϑ(G) を求め
る方法が挙げられる．詳細については Schrijver による著作 [59] などを参照されたい．
2005 年に Chudnovsky, Cornuéjols, Liu, Seymour, Vušković は，与えられたグラフが
Berge グラフか否か判定する方法を示した．その計算量は O(|V (G)|9 ) である．
2.4 単位円グラフ
2 次元平面上の頂点集合と正実数の閾値が与えられたとき，頂点間のユークリッド距離が閾
値以下ならばそのときに限り頂点が隣接であるグラフを単位円グラフ (unit disk graph) とい
う．より厳密には，有限集合 P ⊆ R2 と閾値 d ∈ R+ が与えられたとき，頂点集合 V = P ，枝
集合 E = {{u, v} | u, v ∈ V, dE (u, v) ≤ d} よりなるグラフ G = (V, E) を単位円グラフとい
う．ここで dE (x, y) は点 x, y 間のユークリッド距離である．直感的には，平面上に同じ直径
の円盤が複数あるとき，重なりを持つ円盤の中心同士を線で結んで得られる線図が単位円グラ
フである．単位円グラフは頂点集合 P ⊆ R2 と閾値 d ∈ R+ で定まるのでその対 (P, d) で表
すこともある．一般にグラフと言う場合には頂点集合とその隣接関係だけを扱う．よって頂点
2.4 単位円グラフ
13
の座標が与えられているものはグラフではなくグラフの埋め込みである．しかし単位円グラフ
の研究においては頂点の座標が与えられているものも単位円グラフとよんでいることが多い．
本論文では頂点の座標が与えられた（平面に埋め込まれた）ものを扱うことが多いのでそれを
単位円グラフと呼ぶことにし，単位円グラフとして平面に埋め込めるグラフを単位円的グラフ
と呼ぶことにする．K1,6 , K2,3 は単位円的グラフではない．図 2.2 に単位円グラフの例を示
し，図 2.3 に K1,6 , K2,3 を示す．図 2.2 の薄い円は単位円である．
図 2.2. 単位円グラフの例
図 2.3. K1,6 （左）と K2,3 （右）
1990 年に Clark, Colbourn によって単位円グラフの最大クリークは多項式時間で得られ
ることが示された [16]．彼らは単位円グラフの最大クリーク問題の部分問題を 2 部グラフの
最大安定集合問題に帰着した．2 部グラフの最大安定集合問題を全ての頂点対の数だけ解く
ため，その計算量は O(n4.5 ) である，ここで n はグラフの頂点数である．1990 年に Clark,
Colbourn は単位円グラフの彩色問題が NP-困難であることを示した [16]．その証明より直ち
に，単位円グラフの彩色問題の多項式時間近似解法で近似率が 4/3 より小さい解法があるな
らば P=NP であることがわかる．1995 年に Marathe, Breu, Hunt, Ravi, Rosen は単位円
グラフの彩色問題の多項式時間 3-近似解法を提案した [43]．彼らの解法は単純な貪欲解法で
14
第2章
基本的な用語と記号
あり，その計算量は O(m log n) である，ここで m はグラフの枝数，n はグラフの頂点数で
ある．彼らの解法は，平面に埋め込まれているとは限らない，単位円的グラフを入力とする．
1990 年に Clark, Colbourn は単位円グラフの最大安定集合問題が NP-困難であることを示し
た [16]．2000 年に Matsui は単位円グラフの最大安定集合問題に対して，O(rn4d2(r−1)/
√
3e
)
時間の (1 − 1/r)-近似解法（いわゆる PTAS）を提案した，ここで r は近似解法の精度と計算
量を決めるパラメーターである．Matsui の解法は平面に埋め込まれた単位円グラフを入力と
する．2004 年に Nieberg, Hurink, Kern は単位円グラフの最大重み安定集合問題に対して，
O(npoly.(r) ) 時間 (1/r)-近似解法（いわゆる PTAS）を提案した，ここで r は近似解法の精度
と計算量を決めるパラメーターである．彼らの解法は，平面に埋め込まれているとは限らな
い，単位円的グラフを入力とする．
2.5 格子状グラフ
非 負 整 数 m と n に 対 し て 2 次 元 座 標 平 面 上 の 整 数 格 子 点 の 部 分 集 合 S(m, n) を ，
def.
S(m, n) = {0, 1, 2, . . . , m − 1} × {0, 1, 2, . . . , n − 1} と定義する．非負整数 m と n に対
def.
して 2 次元平面上の三角格子点の部分集合 T (m, n) を，T (m, n) = {(xe1 + ye2 ) | x ∈
def.
def.
{0, 1, 2, . . . , m − 1}, y ∈ {0, 1, 2, . . . , n − 1}} と定義する，ここで e1 = (1, 0), e2 =
√
(1/2, 3/2) である．
単位円グラフ (S(m, n), d) を Sm,n (d) で表す．特に Sm,n (1) を四角格子グラフと呼ぶ．単
位円グラフ (T (m, n), d) を Tm,n (d) で表す．特に Tm,n (1) を三角格子グラフと呼ぶ．
グラフ G が与えられたとき，頂点集合が G と同じであり，頂点対間の「G 上の」距離が k
以下ならばそのときに限り隣接とするグラフを G の k 乗グラフ (the kth power of G) とよび
k
で，Tm,n (1) の k 乗グ
Gk で表す．明らかに G1 = G である．Sm,n (1) の k 乗グラフを Sm,n
k
ラフを Tm,n
で表す．
k
k
本論文では，(S(m, n), d), Tm,n (d), Sm,n
, Tm,n
を格子状グラフと呼ぶ．
2.6 近似解法
問題の解を有限時間で見つける手続きは「解法」「算法」「アルゴリズム」などいろいろな呼
ばれ方をするが，本論文では解法と呼ぶことにする．得られる解の近似精度が保証されている
解法を精度保証付き近似解法 (approximation algorithm) という．組合せ最適化問題の近似
解法に関しては Vazirani の著書によくまとめられている [63]．得られる解の近似精度が保証
されていない，発見的解法 (heuristics) も近似解法と呼ぶ文献もあるが，本論文では両者を区
別して呼ぶことにする．本論文では精度保証付き多項式時間近似解法を多項式時間近似解法と
略す．多項式時間解法とは問題の入力の大きさの多項式で計算時間が抑えられる解法のことで
ある．本論文では主に精度保証付き多項式時間近似解法を扱う．
目的関数が最小化であるような組合せ最適化問題を I とする．問題例 (instance) I ∈ I の
2.7 調和数
15
最適値を Z ∗ (I)，解法 A によって得られる目的関数値を A(I) としたとき
α × Z ∗ (I) ≥ A(I),
∀I ∈ I
が満たされる解法を（I に関する）α-近似解法という*1 ．また α を近似解法 A の近似率とい
う．最小化問題において近似率は常に 1 以上である．
2.7 調和数
自然数 n の調和数 (Harmonic number)Hn は
def.
Hn =
n
X
1
i=1
i
で定義される．Hn = O(log n) であることが知られている．
*1
最大化問題の場合には別の定義がある．しかし本論文では最小化問題のみを扱うので，ここでは定義を紹介し
ない．
16
第3章
格子状グラフの多重彩色問題
本章では多重彩色問題の近似解法を論じる．パーフェクトグラフの最適多重彩色は多項式時
間で得られることが既存の研究より知られている．これを基に本研究では，パーフェクトでな
いグラフのパーフェクトな誘導部分グラフを見つけることにより，多重彩色問題の多項式時間
近似解法を構築する．提案する近似解法は，パーフェクトでないグラフの多重彩色にパーフェ
クトグラフの多重彩色法を用いるという一般的な枠組みに拡張することができる．本章で提案
する近似解法の枠組みは一般のグラフに適用可能であるが，特に，格子状グラフに適用した場
合には良い近似率を達成する．格子状グラフの多重彩色問題は，最小スパンチャネル割当問題
の素直な単純化になっており，実用上重要な問題でもある．格子状グラフを扱う背景に関して
は 1.4 節を参照されたい
本章では
• 三角格子点上の単位円グラフ，
• 四角格子点上の単位円グラフ，
• 三角格子グラフの k 乗グラフ，
• 四角格子グラフの k 乗グラフ
を扱うが， 提案する解法の枠組みはこれら全てのグラフに適用することができる．よって解
法の記述においては，三角格子点上の単位円グラフを主に用いる．本章では多重彩色問題の多
項式時間近似解法を示すだけでなく，最大重み安定集合問題の多項式時間近似解法や有理彩色
問題の最適値の見積もりや非パーフェクト率の見積もりも示す．これらの結果は全て，グラフ
がパーフェクトとなる条件を整理したことにより得られている．
本章で示す内容の多くは Miyamoto, Matsui による文献 [48, 50, 51] で既に発表されている
ものである．既に発表されている定理，補題，系に関しては対応する文献を明記してある．対
応する文献が明記されていないものは本論文で初めて記されるものである．
以下本章の構成を示す．3.1 節では各種格子状グラフと多重彩色問題を定義する．3.2 節で
は各種格子状グラフがパーフェクトである条件とパーフェクトでない条件を示す．特に四角格
子点上の単位円グラフ以外に関しては必要十分条件になっている．3.3 節では有理彩色問題の
最適値と非パーフェクト率の見積もりを示す．3.5 節では多重彩色問題の多項式時間近似解法
3.1 格子グラフと多重彩色問題の定義
17
を示す．3.4 節では最大重み安定集合問題の多項式時間近似解法を示す．3.6 節では各種格子
状グラフの多重彩色問題の計算困難性について論じる．3.8 節では本章の結果をまとめ今後の
課題を論じる．
3.1 格子グラフと多重彩色問題の定義
非 負 整 数 m と n に 対 し て 2 次 元 座 標 平 面 上 の 整 数 格 子 点 の 部 分 集 合 S(m, n) を ，
def.
S(m, n) = {0, 1, 2, . . . , m − 1} × {0, 1, 2, . . . , n − 1} と定義する．非負整数 m と n に対
def.
して 2 次元平面上の三角格子点の部分集合 T (m, n) を，T (m, n) = {(xe1 + ye2 ) | x ∈
def.
def.
{0, 1, 2, . . . , m − 1}, y ∈ {0, 1, 2, . . . , n − 1}} と定義する，ここで e1 = (1, 0), e2 =
√
(1/2, 3/2) である．
単位円グラフ (S(m, n), d) を Sm,n (d) で表す．特に Sm,n (1) を四角格子グラフと呼ぶ．単
位円グラフ (T (m, n), d) を Tm,n (d) で表す．特に Tm,n (1) を三角格子グラフと呼ぶ．Sm,n (1)
k
k
で表す．以下本章では Sm,n (d)，
で，Tm,n (1) の k 乗グラフを Tm,n
の k 乗グラフを Sm,n
k
k
を扱う．
，Tm,n (d)，Tm,n
Sm,n
グラフ G = (V, E) と非負整数頂点重み関数 w : V → Z+ が与えられたとき，クリーク
P
C ⊆ V のうちその重み v∈C w(v) が最大となるものを最大重みクリークという．最大重み
P
クリークの重み v∈C w(v) を最大重みクリーク数といい ω(G, w) で表す．
グラフ G = (V, E) と非負整数頂点重み関数 w : V → Z+ が与えられたとき，どの頂点 v
にも w(v) 個の自然数が割り当てられ，どの隣接する頂点対も同じ値を共有しない自然数の
割当 c : V → 2N を (G, w) の多重彩色 (multicoloring, weighted coloring) という．すなわち
(G, w) の多重彩色 c とは ∀v ∈ V, |c(v)| ≥ w(v) と ∀{u, v} ∈ E, c(u) ∩ c(v) = ∅ を満たす
割当といえる．割当に使われた自然数を「色」と呼ぶこともある．(G, w) の多重彩色のうち，
必要とされる色数が最小の多重彩色を見つける問題を多重彩色問題 (multicoloring problem,
weighted coloring problem) という*1 ．多重彩色問題は
minimize
subject to
| ∪v∈V c(v) |
c(u) ∩ c(v) = ∅, ∀{u, v} ∈ E,
| c(v) | ≥ w(v), ∀v ∈ V,
c(v) ∈ 2N , ∀v ∈ V
と定式化することができる．多重彩色問題の最適値を多重彩色数といい χ(G, w) で表す．
∀v ∈ V, w(v) = 1 のとき多重彩色問題は頂点彩色問題となる，すなわち多重彩色問題は頂点
彩色問題の拡張になっている．よって多重彩色問題は（入力が一般のグラフの場合）NP-困難
であり，入力グラフが最大次数 4 の平面グラフであっても NP-困難であることが知られてい
る [24]．
多重彩色数 χ(G, w) と最大重みクリーク数 ω(G, w) は常に
χ(G, w) ≥ ω(G, w)
*1
使われる自然数のうち最大のものを最小化する問題とも本質的に等価である．
18
第3章
格子状グラフの多重彩色問題
を満たす．また，多重彩色数 χ(G, w) と最大安定数 α(G) は常に
P
χ(G, w) ≥
w(v)
α(G)
v∈V
を満たす．
3.2 パーフェクトグラフと非パーフェクトグラフの整理
多重彩色数が多項式時間で得られるグラフのクラスとしてパーフェクトグラフが知られてい
る（パーフェクトグラフの定義などについては 2.3 節を参照されたい）
．この事実に着目し，本
章では，入力として与えられたグラフがパーフェクトでない場合でも，パーフェクトな誘導部
分グラフを見つけることにより，問題を多項式時間で最適化可能な部分問題に分解し，得られ
た解を統合する分割統治法を用いた近似解法を提案する．本章では各種格子状グラフに対する
近似解法を提案し，後の節で近似解法の一般的なフレームワークを示す．
パーフェクトグラフでは，その定義より，クリーク数と彩色数が一致する．1981 年に
Grötschel, Lovász, Schrijver はパーフェクトグラフの最適彩色は多項式時間で得られること
を示した [31]． この結果は同時に，パーフェクトグラフの最大重みクリーク数と多重彩色数
が一致することと，パーフェクトグラフの最適多重彩色が多項式時間で見つかることも示して
いた．よって多重彩色問題の効率的に解ける部分問題を見つける際にパーフェクトグラフを利
k
k
がパーフェクトであるた
, Sm,n
用することは自然なことである．3.2.1 節では Tm,n (d), Tm,n
めの必要十分条件を整理する．3.2.2 節では Sm,n (d) がパーフェクトであるための必要条件と
十分条件を整理する．3.2.3 節では，3.2.1 節と 3.2.2 節で見つけたパーフェクトな部分グラフ
を最適多重彩色する効率的な方法を論じる．
3.2.1
k
k
Tm,n (d), Tm,n
, Sm,n
がパーフェクトであるための必要十分条件
k
k
, Sm,n
に関して以下の定理 1，定理 2，定理 3 がそれぞれ成り立つ．
Tm,n (d), Tm,n
定理 1 (Miyamoto, Matsui [50]). n ≤ 3 のときグラフ Tm,n (d) はパーフェクトである．
n ≥ 4 かつ d ≥ 1 のとき，「∀m ∈ Z+ において Tm,n (d) がパーフェクトであること」と
√
「d ≥ n2 − 3n + 3 であること」は同値である．
0 < d < 1 のとき，Tm,n (d) には枝がなく明らかにパーフェクトなので定理 1 では扱っていな
い．小さな n, d において Tm,n (d) がパーフェクトな場合と非パーフェクトな場合を表 3.1 に
示す．
k
定理 2 (Miyamoto, Matsui [51]). n ≤ 3 のとき，グラフ Tm,n
はパーフェクトである．
k
n ≥ 4 のとき，「∀m ∈ Z+ において Tm,n
がパーフェクトであること」と「k ≥ n − 1 である
こと」は同値である．
k
小さな n, k において Tm,n
がパーフェクトな場合と非パーフェクトな場合を表 3.2 に示す．
3.2 パーフェクトグラフと非パーフェクトグラフの整理
19
表 3.1. 三角格子点上の単位円グラフがパーフェクトな場合と非パーフェクトな場合
H
HH
d
1···
H
HH
n
H
√
√
7···
√
13 · · ·
21 · · ·
1
2
3
4
パーフェクト
5
6
..
.
非パーフェクト
表 3.2. 三角格子グラフの k パワーグラフがパーフェクトな場合と非パーフェクトな場合
HH
k
H
12
HH
n
H
H
3
4
5
6
7
8
1
2
3
4
パーフェクト
5
6
7
8
非パーフェクト
9
..
.
k
がパーフェ
定理 3 (Miyamoto, Matsui [51]). k ≥ 2 のとき，「∀m ∈ Z+ において Sm,n
クトであること」と「k ≥ 2n − 3 であること」は同値である．
1
Sm,n
= Sm,n は明らかに 2 部グラフでありパーフェクトなので定理 3 では扱っていない．小
k
さな n, k において Sm,n
がパーフェクトな場合と非パーフェクトな場合を表 3.3 に示す．
以下では「条件を満たすグラフがパーフェクトである」ことと「条件を満たさないグラフが
非パーフェクトである」ことと分けて示すことによって，定理 1，定理 2，定理 3 を示す．
「条件を満たすグラフがパーフェクトである」ことを示すため，比較可能グラフ (compara-
bility graph) とその補グラフである補比較可能グラフ (co-comparability graph) を定義する．
−
→
グラフ G = (V, E) の全ての枝を向き付けした有向グラフ G = (V, F ) で「(a, b) ∈ F かつ
(b, c) ∈ F ならば (a, c) ∈ F 」を満たすものが存在するとき，そのグラフは推移的に向き付け
20
第3章
格子状グラフの多重彩色問題
表 3.3. 四角格子グラフの k 乗グラフがパーフェクトな場合と非パーフェクトな場合
HH
k
H
2
HH
n
H
H
34
56
78
9 10
11 12
13 14
1
2
3
パーフェクト
4
5
6
7
非パーフェクト
8
..
.
可能であるという．推移的に向け付け可能なグラフを比較可能グラフという．比較可能グラ
フの補グラフを補比較可能グラフという．補比較可能グラフはパーフェクトである．これは
Dilworth の分解定理から直ちに得られる．
定理 4 (Dilworth の分解定理 [19]). (S, ≤) を半順序集合とする．このとき S を被覆する鎖
(chain) の最小数は反鎖 (antichain) の最大サイズに等しい
補比較可能グラフを G = (V, E) とし，その補グラフ（すなわち比較可能グラフ）で推移的に
−
→
向き付けされたグラフを H = (V, F ) とする．向き付けされた比較可能グラフの集合族と半
−
→
順序集合族の間には自然な全単射が存在する．その写像において H に対応する半順序集合を
(S, ≤) とする．このとき，G の安定集合は (S, ≤) の鎖に対応し G のクリークは (S, ≤) の反
鎖に対応する．このことと定理 4 より，G の彩色数とクリーク数は一致することが導かれる．
この事実と，補比較可能グラフの誘導部分グラフは再び補比較可能グラフとなる事実から，補
比較可能グラフがパーフェクトであることがわかる．
Dilworth の分解定理は 1950 年に Dilworth によって証明された．この定理は半順序集合に
関するものであり，グラフ理論と直接結びついていたわけではない．パーフェクトグラフが
Berge によって定義されたのは 1960 年代であることから，
「補比較可能グラフがパーフェクト
であること」はパーフェクトグラフの定義と同時に知られていたことになる．
本論文には直接関係しないが，Dilworth の分解定理に関してはその双対「被覆する反鎖の
最小数は鎖の最大サイズに等しい」も成り立つことが知られている．この事実から直ちに，比
較可能グラフもパーフェクトであることがわかる．また一般に，パーフェクトグラフの補グラ
フはパーフェクトであることが，1972 年に Lovász によって証明されている．
定理 5 (弱パーフェクトグラフ定理 [42]). パーフェクトグラフの補グラフはパーフェクトグ
ラフである．
3.2 パーフェクトグラフと非パーフェクトグラフの整理
21
比較可能グラフと補比較可能グラフに関しては，様々なパーフェクトグラフクラスについてま
とめられている Golumbic による著作 [29] 等を参照されたい．
三角格子点上の単位円グラフ Tm,n (d) については以下が成り立つ．
補題 1. ∀n ≥ 1 に対して d ≥
√
n2 − 3n + 3 ならば Tm,n (d) は補比較可能グラフである．
証明. n ≤ 2 のときは自明である．n ≥ 3 かつ d ≥
√
n2 − 3n + 3 のときに Tm,n (d) の補グラ
フが比較可能グラフであることを示せば十分である．Tm,n (d) の補グラフを T m,n (d) で表す．
T m,n (d) の全ての枝を以下のように向き付けする．T m,n (d) の枝 e = {v1 , v2 } を，v1 の x 座
標が v2 の x 座標より小さいならば v1 から v2 へ向き付けする．ここで，定理の条件が満たさ
れるならば T m,n (d) の隣接する頂点対で x 座標が一致するものはないことに注意する．この
ようにして向きづけられたグラフを G0 で表す．G0 が推移律を満たすことを以下で示す．
明らかに G0 は非巡回的 (acyclic) である．ここで G0 に有向枝 (v1 , v2 ) と (v2 , v3 ) があると
する．頂点 vi の座標を (xi , yi ) で表す，ただし xi は vi の x 座標，yi は vi の y 座標である．
G0 の定義より x1 < x2 < x3 である．以下で x2 − x1 > d/2 を示す．
√
√
（場合 1）|y2 −y1 | < ( 3/2)n の場合を考える．このとき明らかに |y2 −y1 | ≤ ( 3/2)(n−2)
である．n ≤ 3 かつ v1 と v2 のユークリッド距離は d 以上なので，
x2 − x1 >
≥
>
≥
である．
p
d2 − |y2 − y1 |2
p
d2 − (3/4)(n − 2)2
p
d2 − (3/4)(n2 − 3n + 3)
p
d2 − (3/4)d2 = d/2
√
（場合 2）|y2 − y1 | ≤ ( 3/2)(n − 1) を仮定する．v1 , v2 ∈ P (m, n) なので明らかに
√
|y2 − y1 | = q( 3/2)(n − 1) が成り立つ．ある x0 に対して (x2 , y2 ) = (x1 , y1 ) + (x0 e1 +
(n − 1)e2 ) であると仮定して一般性を失わない．0 < x2 − x1 = (n − 1)/2 + x0 なので
x0 > −(n − 1)/2 である．もし x0 ≤ −1 ならば |x2 − x1 |2 + |y2 − y1 |2 = (x0 + (n −
1)/2)2 + (3/4)(n − 1)2 ≤ (−1 + (n − 1)/2)2 + (3/4)(n − 1)2 = n2 − 3n + 3 ≤ d2 であ
り Tm,n (d) 上で v1 と v2 が隣接でないことに矛盾する．よって x0 が整数であることから，
√
x0 ≥ 0 かつ |x2 − x1 | = (n − 1)/2 + x0 ≥ (n − 1)/2 = |y2 − y1 |/ 3 である．よって式
d2 < |x1 − x2 |2 + |y1 − y2 |2 ≤ |x1 − x2 |2 + 3|x1 − x2 |2 = 4|x1 − x2 |2 から d/2 < x2 − x1 と
なる．
同様に x3 − x2 > d/2 であることも簡単に示せる．このため x3 − x1 > d であり，かつ，v1
と v3 の距離は d より大きい．G0 の定義より，有向グラフ G0 は枝 (v1 , v3 ) を含む．
以下の補題 2 と補題 3 は補題 1 と同様に示せる．
k
補題 2. ∀n ≥ 2 に対して k ≥ n − 1 ならば Tm,n
は補比較可能グラフである．
k
補題 3. ∀n ≥ 1 に対して k ≥ 2n − 3 ならば Sm,n
は補比較可能グラフである．
22
第3章
格子状グラフの多重彩色問題
三角格子グラフ Tm,n (1) に関しては以下の補題が成り立つ．
1
補題 4. ∀m ∈ Z+ に対して Tm,3 (1) = Tm,3
はパーフェクトある．
証明. H を Tm,3 (1) の誘導部分グラフとする．ω(H) ≤ 2 のとき H は長さ 3 のサイクルを含
まない．このとき H は 2 部グラフなので明らかに ω(H) = χ(H) である．ω(H) ≥ 3 のとき，
ω(Tm,3 (1)) = 3 でありかつ Tm,3 (1) は自明な 3 彩色を持つので，ω(H) = 3 かつ χ(H) ≤ 3
であることは明らかである．
ここで，Tm,3 (1) はパーフェクトだが，比較可能グラフでも補比較可能グラフでもないことに
注意されたい．
補題 1 と補題 4 は定理 1 の条件を満たすグラフがパーフェクトであることを示している．
補題 2 と補題 4 は定理 2 の条件を満たすグラフがパーフェクトであることを示している．補
題 3 は定理 3 の条件を満たすグラフがパーフェクトであることを示している．
以下ではグラフが非パーフェクトである条件を，グラフが奇ホールを持つことにより導く．
これ以降本章では，頂点 (xe1 + ye2 ) ∈ P (m, n) を hx, yi で表す．
補題 5. 1 ≤ d <
証明. 1 ≤ d <
√
√
7 ならば ∀m ≥ 5, Tm,4 (d) は奇ホールを持つ．
3 ならば
{ h2, 0i, h1, 1i, h0, 2i, h0, 3i, h1, 3i, h2, 3i, h3, 2i, h3, 1i, h3, 0i }
により誘導される部分グラフは 9 ホールである（図 3.1 参照）.
図 3.1. Tm,4 (1) における誘導部分グラフ C9
√
3 ≤ d < 2 ならば
{ h3, 0i, h1, 1i, h0, 2i, h1, 3i, h2, 3i, h4, 2i, h4, 1i }
により誘導される部分グラフは 7 ホールである（図 3.2 参照）.
2≤d<
√
7 ならば
{ h2, 0i, h0, 2i, h1, 3i, h3, 2i, h3, 0i }
により誘導される部分グラフは 5 ホールである（図 3.3 参照）.
以上をまとめると，1 ≤ d <
て補題は示された．
√
7 のとき T5,4 (d) は少なくとも 1 つは奇ホールを持つ．よっ
3.2 パーフェクトグラフと非パーフェクトグラフの整理
23
√
図 3.2. Tm,4 ( 3) における誘導部分グラフ C7
図 3.3. Tm,4 (2) における誘導部分グラフ C5
補題 6. 1 ≤ d <
証明. 1 ≤ d <
√
√
√
13 ならば ∀m ≥ 6, Tm,5 (d) は奇ホールを持つ．
7 ならば補題 5 の証明にある奇ホールは T6,5 (d) の誘導部分グラフである．
7 ≤ d < 3 ならば
{ h2, 0i, h0, 2i, h1, 4i, h4, 2i, h4, 0i }
により誘導される部分グラフは 5 ホールである（図 3.4 参照）.
√
図 3.4. Tm,5 ( 7) における誘導部分グラフ C5
3≤d<
√
13 ならば
{ h3, 0i, h0, 3i, h2, 4i, h5, 3i, h5, 0i }
により誘導される部分グラフは 5 ホールである（図 3.5 参照）.
24
第3章
格子状グラフの多重彩色問題
図 3.5. Tm,5 (3) における誘導部分グラフ C5
以上をまとめると，1 ≤ d <
√
13 のとき T6,5 (d) は少なくとも 1 つの奇ホールを持つ．よっ
て補題は示された．
補題 7. n ≥ 6 かつ
√
n2 − 5n + 7 ≤ d <
√
n2 − 3n + 3 のとき，
{ hn − 3, 0i, h0, n − 2i, hn − 4, n − 1i, h2n − 7, n − 2i, h2n − 6, 0i }
により誘導される Tm,n (d) の部分グラフは 5 ホールである．
証明. 以下では，主張の 5 点が定理の条件の下で閉路をなしており，かつ，5 本の対角線の長
さが全て d より長いことを示す．
まず，閉路に関して以下の (1)–(5) を示す．
(1) 頂点 hn − 3, 0i と h0, n − 2i のユークリッド距離は
|(n − 3)e1 + (0)e2 − {(0)e1 + (n − 2)e2 }| = |(n − 3)e1 + (−n + 2)e2 |
p
√
= (n − 3)2 + (−n + 2)2 + (n − 3)(−n + 2) = n2 − 5n + 7 ≤ d なので隣接している．
(2) 頂点 h0, n − 2i と hn − 4, n − 1i のユークリッド距離は |(0)e1 + (n − 2)e2 − {(n −
p
4)e1 + (n − 1)e2 }| = |(−n + 4)e1 + (−1)e2 | = (−n + 4)2 + (−1)2 + (−n + 4)(−1) =
p
√
√
n2 − 7n + 13 = {n2 − 5n + 7} − 2(n − 3) ≤ n2 − 5n + 7 ≤ d (∵ n ≥ 3) なので隣接
している．
(3) 頂点 hn − 4, n − 1i と h2n − 7, n − 2i のユークリッド距離は |(n − 4)e1 + (n − 1)e2 −
p
{(2n − 7)e1 + (n − 2)e2 }| = |(−n + 3)e1 + e2 | = (−n + 3)2 + (1)2 + (−n + 3)(1) =
p
√
√
n2 − 7n + 13 = {n2 − 5n + 7} − 2(n − 3) ≤ n2 − 5n + 7 ≤ d (∵ n ≥ 3) なので隣接
している．
(4) 頂点 h2n − 7, n − 2i と h2n − 6, 0i のユークリッド距離は |(2n − 7)e1 + (n − 2)e2 −
p
{(2n − 6)e1 + (0)e2 }| = |(−1)e1 + (n − 2)e2 | =
(−1)2 + (n − 2)2 + (−1)(n − 2) =
√
n2 − 5n + 7 ≤ d なので隣接している．
(5) 頂 点 h2n − 6, 0i と hn − 3, 0i の ユ ー ク リ ッ ド 距 離 は |(2n − 6)e1 + (0)e2 − {(n −
p
√
3)e1 + (0)e2 }| = |(n − 3)e1 + (0)e2 | = (n − 3)2 + (0)2 + (n − 3)(0) = n2 − 6n + 9 =
p
√
{n2 − 5n + 7} − (n − 2) ≤ n2 − 5n + 7 ≤ d (∵ n ≥ 2) なので隣接している．
3.2 パーフェクトグラフと非パーフェクトグラフの整理
25
次に対角線に関して d より長いことを以下の (6)–(10) で示す．
(6) 頂点 hn−3, 0i と hn−4, n−1i のユークリッド距離は |(n−3)e1 +(0)e2 −{(n−4)e1 +(n−
p
√
1)e2 }| = |(1)e1 + (−n + 1)e2 | = (1)2 + (−n + 1)2 + (1)(−n + 1) = n2 − 3n + 3 > d
なので隣接していない．
(7) 頂点 hn − 4, n − 1i と h2n − 7, n − 2i のユークリッド距離は |(n − 4)e1 + (n − 1)e2 − {(2n −
p
7)e1 +(n−2)e2 }| = |(−n+4)e1 +(−n+2)e2 | = (−n + 4)2 + (−n + 2)2 + (−n + 4)(−n + 2) =
√
3n2 − 18n + 28
p
√
= {n2 − 3n + 3} + (2n − 5)(n − 5) ≥ n2 − 3n + 3 > d (∵ n ≥ 5) なので隣接していな
い．
(8) 頂点 h0, n−2i と h2n−7, n−2i のユークリッド距離は |(0)e1 +(n−2)e2 −{(2n−7)e1 +(n−
p
√
2)e2 }| = |(−2n + 7)e1 + (0)e2 | = (−2n + 7)2 + (0)2 + (−2n + 7)(0) = 4n2 − 28n + 49
p
√
= {n2 − 3n + 3} + 3(n − 6)2 + 11(n − 6) + 4 ≥ n2 − 3n + 3 > d (∵ n ≥ 6) なので隣
接していない．
(9) 頂点 h0, n − 2i と h2n − 6, 0i のユークリッド距離は |(0)e1 + (n − 2)e2 − {(2n − 6)e1 +
p
(0)e2 }| = |(−2n + 6)e1 + (n − 2)e2 | = (−2n + 6)2 + (n − 2)2 + (−2n + 6)(n − 2) =
√
3n2 − 18n + 28
p
√
= {n2 − 3n + 3} + (2n − 5)(n − 5) ≥ n2 − 3n + 3 > d (∵ n ≥ 5) なので隣接していな
い．
(10) 頂点 hn − 4, n − 1i と h2n − 6, 0i のユークリッド距離は |(n − 4)e1 + (n − 1)e2 − {(2n −
p
6)e1 + (0)e2 }| = |(−n + 2)e1 + (n − 1)e2 | = (−n + 2)2 + (n − 1)2 + (−n + 2)(n − 1) =
√
n2 − 3n + 3 > d なので隣接していない．
補題 8. ∀n ≥ 4 に対して 1 ≤ d <
√
n2 − 3n + 3 ならば ∃m ∈ Z+ , Tm,5 (d) は非パーフェク
トである．
証明. 以下では ∀n ≥ 4 に対して 1 ≤ d <
√
n2 − 3n + 3 ならば「∃m ∈ Z+ ，Tm,n (d) は少な
くとも 1 つの奇ホールを持つ」ことを n の帰納法により示す．n = 4, 5 のとき，補題 5，6 よ
り明らかである．
今，1 ≤ d <
p
(n0 − 1)2 − 3(n0 − 1) + 3 であるという仮定の下で n = n0 ≥ 6 の場合を考
える．このとき ∃m0 ∈ Z+ ，Tm0 ,n0 −1 (d) は少なくとも 1 つの奇ホールを持つ．Tm0 ,n0 −1 (d) は
p
√
(n0 − 1)2 − 3(n0 − 1) + 3 = n02 − 5n0 + 7
√
ならば Tm0 ,n0 (d) は少なくとも 1 つ奇ホールを持つ．残りの場合，すなわち n02 − 5n0 + 7 ≤
√
d < n02 − 3n0 + 3 のとき，頂点集合
Tm0 ,n0 (d) の誘導部分グラフなので，1 ≤ d <
{ hn0 − 3, 0i, h0, n0 − 2i, hn0 − 4, n0 − 1i, h2n0 − 7, n0 − 2i, h2n0 − 6, 0i }
は，m00 = 2n0 − 5 ならば，P (m00 , n0 ) に含まれる．n0 ≥ 6 かつ
√
√
n02 − 5n0 + 7 ≤ d <
n02 − 3n0 + 3 のとき，上記の 5 頂点が Tm00 ,n0 (d) の 5 ホールを誘導することは簡単に示せ
る（図 3.6 と補題 7 参照）．
26
第3章
格子状グラフの多重彩色問題
x
図 3.6. Tm,6 (d),
√
13 ≤ d <
√
21 の誘導部分グラフ C5
1
k
は非パーフェクトである．∀n ≥ 4 に対して k ≤ n − 2 ならば ∃m ∈ Z+ , Tm,n
補題 9. T4,4
は非パーフェクトである．
k
が少なくとも 1 つ奇ホールを持
証明. 以下では，∀n ≥ 4，1 ≤ k ≤ n − 2，∃m ∈ Z+ ，Tm,n
つことを，n に関する帰納法により，示す．n = 4 かつ k = 1 のとき
{ h2, 0i, h1, 1i, h0, 2i, h0, 3i, h1, 3i, h2, 3i, h3, 2i, h3, 1i, h3, 0i }
により誘導される部分グラフは 9 ホールである（図 3.1 参照）．n = 4 かつ k = 2 のとき
{ h0, 2i, h1, 3i, h3, 2i, h3, 0i, h2, 0i }
により誘導される部分グラフは 5 ホールである（図 3.3 参照）．
最後に，1 ≤ k ≤ n0 − 3 であるという仮定の下で n = n0 ≥ 5 の場合を考える．このと
k
k
k
き ∃m0 ∈ Z+ , Tm
0 ,n0 −1 は少なくとも 1 つの奇ホールを持つ．Tm0 ,n0 −1 は Tm0 ,n0 の誘導部分
k
グラフなので，1 ≤ k ≤ n0 − 3 ならば Tm
0 ,n0 は少なくとも 1 つの奇ホールを持つ．残りの
k = n0 − 2 の場合は
{ h0, n0 − 2i, hn0 − 3, n0 − 1i, h2n0 − 5, n0 − 2i, h2n0 − 5, 0i, hn0 − 2, 0i }
により誘導される部分グラフは 5 ホールである（図 3.7）．
2
補題 10. S3,3
は非パーフェクトである．
2
証明. S3,3
の誘導部分グラフのうち，
{ (0, 0), (2, 0), (2, 1), (1, 2), (0, 2) }
により誘導される部分グラフは 5 ホールである．
k
補題 11. n ≥ 4 のとき，k ≤ 2n − 4 ならば非負整数 m が存在して Sm,n
は非パーフェクトで
ある．
3.2 パーフェクトグラフと非パーフェクトグラフの整理
27
3
図 3.7. Tm,5
における誘導部分グラフ C5
証明. 奇ホールの存在を帰納法により示す．
n = 4 かつ k = 3 のとき，
{ (0, 0), (0, 3), (2, 3), (3, 3), (3, 0) }
により誘導される部分グラフは 5 ホールである．n = 4 かつ k = 4 のとき，
{ (0, 0), (0, 3), (2, 3), (4, 3), (4, 0) }
により誘導される部分グラフは 5 ホールである．
k
n = n0 ≥ 5 の場合を考える．3 ≤ k ≤ 2n0 − 6 ならば非負整数 m0 が存在して Sm
0 ,n0 −1 に
k
k
0
は奇ホールがあると仮定する．Sm
0 ,n0 −1 は Sm0 ,n0 の誘導部分グラフなので，3 ≤ k ≤ 2n − 6
k
0
ならば Sm
0 ,n0 には奇ホールがある．k = 2n − 5 ならば
{ (0, 0), (0, n0 − 1), (n0 − 2, n0 − 1), (2n0 − 5, n0 − 1), (2n0 − 5, 0) }
により誘導される部分グラフは 5 ホールであり，k = 2n0 − 4 ならば
{ (0, 0), (0, n0 − 1), (n0 − 2, n0 − 1), (2n0 − 4, n0 − 1), (2n0 − 4, 0) }
により誘導される部分グラフは 5 ホールである．
補題 8 より，定理 1 で条件を満たさないグラフは非パーフェクトであることが示された．補
題 9 より，定理 2 で条件を満たさないグラフは非パーフェクトであることが示された．補題
10 と補題 11 より，定理 3 で条件を満たさないグラフは非パーフェクトであることが示され
た．ここまでで定理が示されたことになる．
上記の補題より，以下の系が直ちに導かれる
系 1. Tm,3 (1) はパーフェクトである．d > 1 のとき，n ≤
√
3+ 4d2 −3
2
ならば Tm,n (d) は補比
較可能グラフである．
1
k
系 2. Tm,3
はパーフェクトである．k ≥ 2 のとき，n ≤ k + 1 ならば Tm,n
は補比較可能グラ
フである．
系 3. k ≥ 2 のとき，n ≤
k+3
2
k
ならば Sm,n
は補比較可能グラフである．
28
第3章
格子状グラフの多重彩色問題
3.2.2 Sm,n (d) がパーフェクトである条件
k
k
3.2.1 節では Sm,n
, Tm,n (d), Tm,n
を扱い，それぞれがパーフェクトである必要十分条件
を論じた．Sm,n (d) がパーフェクトであるための必要十分条件は分かっていない．本節では
「Sm,n (d) がパーフェクトであるための十分条件」と「Sm,n (d) が非パーフェクトであるため
の十分条件」を示す．
補題 1 と同じ方法で以下の補題 12 を示すことができる．
補題 12. n ≥ 1 のとき，d ≥
√2 (n
3
− 1) ならば Sm,n (d) は比較可能グラフである．
Tm,n (d) の場合と同様に，補比較可能ではないがパーフェクトな部分グラフが Sm,n (d) にも
存在する．
√
補題 13 (Miyamoto, Matsui [48]). Sm,3 ( 2) はパーフェクトである．
√
証明. (Sm,3 ( 2), w) の多重彩色 c : V → 2Z+ を O(m) で見つける解法を示す．まず最大重み
√
√
クリーク数 ω(Sm,3 ( 2), w) を計算する．Sm,3 ( 2) のクリーク数は 4 であり，極大クリーク
は 2m 個なのでその計算は O(m) 時間でできる．次に奇数 x ∈ {1, . . . , m} に対して
c(x, 1) ={i ∈ Z+ | w(x, 2) < i ≤ w(x, 2) + w(x, 1)},
c(x, 2) ={i ∈ Z+ | 1 ≤ i ≤ w(x, 2)},
c(x, 3) ={i ∈ Z+ | w(x, 2) < i ≤ w(x, 2) + w(x, 3)}
とし，偶数 x ∈ {1, . . . , m} に対して
√
√
c(x, 1) ={i ∈ Z+ | ω(Sm,3 ( 2), w) − w(x, 2) ≥ i > ω(Sm,3 ( 2), w) − w(x, 2) − w(x, 1)},
√
√
c(x, 2) ={i ∈ Z+ | ω(Sm,3 ( 2), w) ≥ i > ω(Sm,3 ( 2), w) − w(x, 2)},
√
√
c(x, 3) ={i ∈ Z+ | ω(Sm,3 ( 2), w) − w(x, 2) ≥ i > ω(Sm,3 ( 2), w) − w(x, 2) − w(x, 3)}
とする．この手続きにかかる時間は明らかに O(m) である．また，この手続きで得られる多重
√
彩色で使われる色数は明らかに ω(Sm,3 ( 2), w) 以下である．よってこの手続きは最適多重彩
色を見つける．
上記の解法は多重彩色問題の解法であり，多重彩色問題は彩色問題を特殊な場合として含む
√
ので，彩色問題にも適用できる．よって Sm,3 ( 2) の彩色数とクリーク数が一致することはす
√
√
ぐに分かる．さらに，Sm,3 ( 2) の任意の誘導部分グラフの彩色問題は Sm,3 ( 2) の多重彩色
問題として表せるので，やはりその場合にも上記の解法が適用可能であり彩色数とクリーク数
√
が一致することが分かる．よってパーフェクトグラフの定義を満たすので Sm,3 ( 2) はパー
フェクトである．
d ≤ 1 のとき，Sm,n (d) は明らかに 2 部グラフでありパーフェクトである．よって d ≤ 1 の
場合を補題 12，補題 13 では扱っていない．ちなみに，補題 12 の条件は満たしていないが
√
Sm,3 ( 5) は補比較可能グラフでありパーフェクトである．
3.2 パーフェクトグラフと非パーフェクトグラフの整理
29
補題 14. 2n ≤ d < 2(n + 1), n ≥ 2 のとき Sm,2n+1 (d) は非パーフェクトである．
証明. 図 3.8 に示す奇ホールが誘導部分グラフとしてある．
(n + 1, 2n)
長さ 2n + 2
長さ
(0, 2n − 1)
長さ
√
√
n2 + 2n + 2
(2n + 2, 2n − 1)
5n
長さ
(1, 0)
√
4n2 − 4n + 2
(2n + 1, 0)
長さ 2n
長さ
p
(2n + 1)2 + (2n − 1)2
図 3.8. Sm,n (d) における奇ホール C5
補題 14 より直ちに以下の系 4 が得られる．
系 4. n ≥ 5 のとき，4 ≤ d < 2b n+1
2 c ならば Sm,n (d) は非パーフェクトである．
系 4 の例を表 3.4 に示す．
表 3.4. 四角格子点上の単位円グラフが非パーフェクトな場合
HH
HH d 4 · · ·
H
n
H
H
5
6···
8···
6
7
8
非パーフェクト
9
10
√
2 ≤ d ≤
√
10 のとき Sm,4 (d) は非パーフェクトである．小さな d, n の場合，Sm,n (d)
が パ ー フ ェ ク ト か 否 か ま と め る と ，表 3.5 と な る ．表 3.5 か ら も 分 か る 通 り ，パ ー
フ ェ ク ト な 場 合 と 非 パ ー フ ェ ク ト な 場 合 の 境 界 は 単 調 で は な い ．ち な み に S3,m (2) は
{(0, 0), (2, 0), (2, 1), (1, 2), (0, 2)} からなる 5 ホールを含むので非パーフェクトである（図 3.9
参照）．
30
第3章
格子状グラフの多重彩色問題
表 3.5. 四角格子点上の単位円グラフがパーフェクトな場合と非パーフェクトな場合
HH
H
n
d
1···
HH
H
H
1
2
√
2···
2···
√
5···
パーフェクト
3
4
非パーフェクト
図 3.9. S3,m (2) における奇ホール C5
3.2.3 パーフェクトな格子状グラフの多重彩色解法
3.2.1 節 と 3.2.2 節 で は パ ー フ ェ ク ト な 部 分 グ ラ フ を 論 じ た ．パ ー フ ェ ク ト グ ラ フ は
Grötschel, Lovász, Schrijver の解法 [31] により多項式時間で多重彩色できるが，本章で
扱っているグラフは特殊なグラフであるため，その性質を使えば時間計算量の意味でより効率
的な解法を構築可能である．本節ではそのような解法を紹介し提案する．
まず補比較可能グラフの多重彩色法を紹介する．補比較可能グラフ G と，推移律が成り立
つように枝が向き付けされた G の補グラフ H が与えられたものと仮定する．このとき G の
安定集合はいずれも H の鎖（有向パス）に対応する．よって，G の多重彩色問題は H の最
小数鎖被覆問題と本質的に同値である．G のクリークはそれぞれ H の反鎖 (anti-chain) に
対応する．これらの考察および Dilworth の分解定理 [19] （3.2.1 節の定理 4 参照）から等式
ω(G) = χ(G) が得られる． 非巡回グラフの最小数鎖被覆は，最小費用サイクル流を見つける
アルゴリズムを用いれば，多項式時間で見つかることがよく知られている（例えば [59] 参照）
．
以下簡単に，補比較可能グラフ G = (V, E) と頂点重み関数 w が与えられたとき，その多重
彩色問題を最大流問題に帰着する方法を記す．本論文で扱っている補比較可能グラフの補グラ
フ（すなわち比較可能グラフ）の推移的な向き付けは容易に得られるため，G の補グラフで推
−
→
移的な枝の向き付けがされているものを H = (V, F ) とする，ここで F は有向枝集合である．
以下説明のため V = {v1 , . . . , vn } とする．
頂点集合 V+
:= {v1+ , . . . , vn+ }, V − := {v1− , . . . , vn− } と ，有 向 枝 集 合 F 0 :=
{(vi+ , vj− ) | (vi , vj ) ∈ F }, F 00 := {(vi− , vi+ ) | i ∈ {1, . . . , n}}, F − := {(s, vi− ) | i ∈
{1, . . . , n}}, F + := {(vi+ , t) | i ∈ {1, . . . , n}} を 導 入 す る ．有 向 グ ラ フ H 0 を
3.2 パーフェクトグラフと非パーフェクトグラフの整理
31
H 0 := (V + ∪ V − ∪ {s, t}, F − ∪ F 0 ∪ F 00 ∪ F + ) と 定 義 す る ．H 0 の 枝 上 に 定 義 さ れ た
非負関数 f : F − ∪ F 0 ∪ F 00 ∪ F + → Z+ を（H 0 上の）フローと呼ぶ．以下の条件
1. f (vi− , vi+ ) = w(vi ), ∀i ∈ {1, . . . , n},
2. V + ∪ V − 中の全ての頂点における流量保存，
def.
を 満 た す f を「 実 行 可 能 な フ ロ ー f 」と 呼 ぶ ．フ ロ ー f の 流 量 flow(f ) を flow(f ) =
Pn
i=1
f (s, vi− ) と定義する．実行可能なフロー f において明らかに flow(f ) =
Pn
i=1
f (vi+ , t)
が成り立つ．「実行可能なフロー f 」から「(G, w) の多重彩色で彩色数が flow(f ) に等しい
もの」を多項式時間で構築できることは，ネットワークフロー分解定理（詳しくは Ahuja,
Magnanti, Orlin による著作 [2] の 3.5 節を参照されたい）より明らかである．
−
→
定理 6 (ネットワークフロー分解定理). 有向グラフ H = (V, F ) に関して，「有向路に沿った
（非負）フロー」と「有向閉路に沿った（非負）フロー」の和集合は（非負）フローとして唯一
の表現を持つ．逆に，（非負）フローは以下の条件 (a), (b) を満たすように「有向路に沿った
（非負）フロー」と「有向閉路に沿った（非負）フロー」に分解できる．(a) 有向路に沿ったフ
ローは全て，湧き出しを始点とし，吸い込みを終点とする．(b) 高々 |V | + |F | 個の，「有向路
に沿ったフロー」と「有向閉路に沿ったフロー」に分解できる．
−
→
有向グラフ H = (V, F ) 上のフローの分解は O(|V ||F |) の手間で得られることが知られてい
る．また，H 0 は比較可能グラフであるため有向閉路を持たない．よってネットワークフロー
分解定理より，
「 H 0 上の実行可能なフロー f 」から「(G, w) の多重彩色で彩色数が flow(f ) に
等しいもの」を O(|V |3 ) で構築できる．逆に，「(G, w) の c-多重彩色」から「flow(f ) = c を
満たす H 0 上の実行可能なフロー f 」を構築できることも，ネットワークフロー分解定理より
明らかである．よって多重彩色問題 (G, w) は多項式時間でネットワーク整数流問題
NIF(H 0 ) : minimize
flow(f ) =
subject to
f (vi− , vi+ )
n
X
i=1
X
f (s, vi− ) =
n
X
f (vi+ , t)
i=1
= w(vi ), ∀i ∈ {1, . . . , n},
X
f (v, u), ∀v ∈ V + ∪ V − ,
f (u, v) =
−
u∈δH
0 (v)
+
u∈δH
0 (v)
f (e) ∈ Z+ , ∀e ∈ F − ∪ F 0 ∪ F 00 ∪ F + ,
def.
def.
−
+
0
0
に帰着できる，ここで δH
0 (v) = {u | (u, v) ∈ E(H )}, δH 0 (v) = {u | (v, u) ∈ E(H )} で
ある．
NIF(H 0 ) は，以下のように，最大流問題に変形することができる．有向枝集合 F + :=
{(t0 , vi+ ) | i ∈ {1, . . . , n}}, F − := {(vi− , s0 )


w(vi ),
c(e) = w(vi ),


+∞,
| i ∈ {1, . . . , n}} を導入し，枝容量関数 c を
e = (t0 , vi+ ) ∈ F + ,
e = (vi− , s0 ) ∈ F − ,
e ∈ F0
32
第3章
格子状グラフの多重彩色問題
と定義する．これを用いて枝容量制約付きのネットワーク H 00 := (V + ∪ V − ∪ {s0 , t0 }, F + ∪
F 0 ∪ F − , c) を定義する．H 00 の枝上に定義された関数 f 0 : F + ∪ F 0 ∪ F − → Z+ を（H 00 上
の）フローと呼ぶ．V + ∪ V − 中の全ての頂点において流量保存則を満たす f 0 を「H 00 上の
実行可能なフロー f 0 」と呼ぶ．
「H 0 上の実行可能なフロー f 」と「H 00 上の実行可能なフロー
f 00 」には自然な全単射が存在するため，NIF(H 0 ) は多項式時間で最大整数流問題
MIF(H 00 ) : maximize
n
X
f (t0 , vi+ ) =
i=1
subject to
n
X
f (vi− , s0 )
i=1
f (t0 , vi+ ) ≤ w(vi ), f (vi− , s0 ) ≤ w(vi ), ∀i ∈ {1, . . . , n},
X
X
f (u, v) =
f (v, u), ∀v ∈ V + ∪ V − ,
−
u∈δH
00 (v)
+
u∈δH
00 (v)
f (e) ∈ Z+ , ∀e ∈ F + ∪ F 0 ∪ F − ,
に帰着できる．MIF(H 00 ) の線形緩和問題には必ず整数最適解があり，その整数最適解は多項
式時間で得られることが知られている [2]．よって NIF(H 0 ) は多項式時間で最大流問題
00
MF(H ) : maximize
n
X
f (t
0
, vi+ )
i=1
subject to
=
n
X
f (vi− , s0 )
i=1
f (t0 , vi+ ) ≤ w(vi ), f (vi− , s0 ) ≤ w(vi ), ∀i ∈ {1, . . . , n},
X
X
f (u, v) =
f (v, u), ∀v ∈ V + ∪ V − ,
−
u∈δH
00 (v)
+
u∈δH
00 (v)
f (e) ≥ 0, ∀e ∈ F + ∪ F 0 ∪ F −
に帰着できる．
以下では，補比較可能グラフ G 上の多重彩色問題 (G, w) の最適解を得るための計算量を見
積もる．(G, w) から NIF(H 0 )，NIF(H 0 ) から MF(H 00 ) を構築する手間はそれぞれ O(|V |2 )
である．MF(H 00 ) の整数最適解を得る手間は，例えば 1974 年に Karzanov [39] によって提案
された preflow-push 法を用いれば，O(|V |3 ) である．最大流問題の入力グラフが疎な場合に
は，計算量が競合的な解法が多数知られているが [3, 4, 14, 28]，ここで最大流問題の入力とし
て扱っているグラフは，多重彩色問題の入力グラフの「補グラフ」の枝を向き付けし，頂点や
有向枝を追加したものなので，注意が必要である．MF(H 00 ) の整数最適解から NIF(H 0 ) の最
適解を得る手間は O(|V |2 ) である．NIF(H 0 ) の最適解から多重彩色問題 (G, w) の最適解を得
る手間は，ネットワーク分解定理より，O(|V |3 ) である．以上をまとめると，補比較可能グラ
フ G 上の多重彩色問題 (G, w) の最適解を得るための計算量は O(|V |3 ) となる．
√
1
1
は補
以下では Tm,3 (1) = Tm,3
の多重彩色を論じる．グラフ Sm,3 ( 2) と Tm,3 (1) = Tm,3
√
比較可能グラフではないため，上記の解法を用いることができない．グラフ Sm,n ( 2) の多重
1
彩色については，O(m) 時間の解法を補題 13 の証明中で明示した． 以下では Tm,3 (1) = Tm,3
の多重彩色を効率的に見つける解法を提案する．
3.3 有理彩色と非パーフェクト率
33
(Tm,3 (1), w) の最適多重彩色を見つける解法
以下では，頂点重み付きグラフ (Tm,3 (1), w) を多重彩色する強多項式時間厳密解法を記
す．色の集合を C ∗ = {1, 2, . . . , ω ∗ } で表す．ここで ω ∗ = ω(Tm,3 (1), w) である．グラフ
G の頂点集合を V (G) とする．以下で記す解法は，∀v ∈ V (T 1 (m, 3)), |c(v)| = w(v) と
∗
∀{u, v} ∈ E(Tm,3 (1)), c(u) ∩ c(v) = ∅ を満たす色割当 c : V (Tm,3 (1)) → 2C を見つける．
任意の x ∈ {0, 1, . . . , m − 1} に対して，頂点 xe1 + 2e2 , xe1 + 1e1 , xe1 + 0e2 をそれ
ぞれ tx+1 , ux+1 , vx で表す．よって {t1 , t2 , . . . , tm }，{u1 , u2 , . . . , um }，{v0 , v1 , . . . , vm−1 }
は V (T 1 (m, 3)) の分割になる．w(v0 ) = w(tm ) = w(um ) = 0 と仮定して一般性を失わない．
我々が提案する解法は以下のように頂点に色を割り当てる．任意の i ∈ {1, 2, . . . , j} に対して
c(ti ) ⊆ c(vi ) あるいは c(ti ) ⊇ c(vi ) を満たす色割当 c : P 0 → 2C が既に得られていると仮定
する．ここで P 0 = {t1 , t2 , . . . , tj } ∪ {u1 , u2 , . . . , uj } ∪ {v0 , v1 , . . . , vj } である．ここで次に
uj+1 に色を割り当てる．w(v0 ) = w(tm ) = w(um ) = 0 なので，w(tj ) ≥ w(vj ) と仮定して一
般性を失わない．{uj , tj , uj+1 } は 3 クリークなので |c(uj )| + |c(tj )| + w(uj+1 ) ≤ w∗ である．
よって |C1 | = w(uj+1 ) を満たし c(uj ) ∪ c(tj ) と交わりがない色部分集合 C1 が存在する．こ
こで C1 に c(uj+1 ) をセットする．次に tj+1 に色を割り当てる．{tj , uj+1 , tj+1 } は 3 クリー
クなので |C2 | = w(tj+1 ) を満たす色集合 C2 ⊆ C ∗ \ (c(tj ) ∪ c(uj+1 )) が存在する．次に C2 に
c(tj+1 ) をセットする．最後に vj+1 に色を割り当てる．ここで 3 つの場合に分けて説明する．
（場合 1）w(tj+1 ) ≥ w(vj+1 ) ならば，要素数が w(vj+1 ) となるような c(tj+1 ) の部分集合を
c(vj+1 ) に割り当てる．
（場合 2）w(tj+1 ) < w(vj+1 ) かつ w(tj ) + w(tj+1 ) ≥ w(vj ) + w(vj+1 ) の場合を考える．
このとき要素数が w(vj+1 ) − w(tj+1 ) となる色部分集合 C3 ⊆ c(tj ) \ c(vj ) が存在する．
c(vj+1 ) = c(tj+1 ) ∪ C3 を割り当てる．
（場合 3）w(tj+1 ) < w(vj+1 ) かつ w(tj )+w(tj+1 ) < w(vj )+w(vj+1 ) の場合を考える．このと
き c(vj+1 ) = c(tj+1 )∪(c(tj )\c(vj ))∪C4 と割り当てる．ここで，C4 と v(tj )∪c(uj+1 )∪c(tj+1 )
は互いに素であり w(vj+1 ) = w(tj+1 ) + (w(tj ) − w(vj )) + |C4 | が成り立つ．{vj , uj+1 , vj+1 }
は 3 クリークなので，上記を満たす色部分集合があることは簡単に確認できる．
上記の解法は色集合 C ∗ をそのまま扱っているので，単純に実装すると擬多項式時間解法
になる．しかし，色集合を区間の和集合で表し，注意深く実装すれば m の多項式時間解法に
なる．
3.3 有理彩色と非パーフェクト率
k
k
本節では，(Tm,n (d), w)，(Tm,n
, w)，(Sm,n (d), w)，(Sm,n
, w) の有理多重彩色問題の近似
解法を提案する．また，この近似解法は非パーフェクト率の上界を与える．
グラフ G = (V, E) と非負有理数頂点重み関数 w : V → Q+ が与えられたとき，以下の線形
34
第3章
格子状グラフの多重彩色問題
計画問題
minimize
X
yS
S∈S
subject to
X
yS ≥ w(v), ∀v ∈ V,
S3v
yS ≥ 0, ∀S ∈ S
で定義される問題を有理多重彩色問題 (fractional multicoloring problem) という．ここで S
は G の全ての安定集合からなる族である．(G, w) の有理彩色問題の最適値を有理多重彩色数
(fractional multicoloring number) といい χf (G, w) で表す．
一般のグラフの有理多重彩色数を求める問題は NP-困難であることが知られている [59]．
一般のグラフ G に関して ω(G, w) ≤ χf (G, w) ≤ χ(G, w) が成り立つ．パーフェクトグラフ
G に関しては ω(G, w) = χf (G, w) = χ(G, w) が成り立つので，パーフェクトグラフの有理多
重彩色数は多項式時間で得られる．
定理 1，定理 2，定理 3, 補題 12 より直ちに以下の系が導かれる．
1
系 5. Tm,n (1) = Tm,n
の
def.
Vi = {(x, y) | (x, y) ∈ T (m, n), y ∈ {i, i + 1, i + 2} (mod 4)},
i ∈ {1, 2, 3, 4}
により誘導される 4 つの部分グラフは全てパーフェクトである．
def.
簡単のため以下本章では K1 =
j
k
√
def.
3+ 4d2 −3
，K 2 =
2
j
k
√
3+ 4d2 −3
2
j
+
√2 d
3
k
と定義する．
系 6. Tm,n (d) において，任意の i ∈ {1, 2, . . . , K2 } に対し，
def.
Vi = {(x, y) | (x, y) ∈ T (m, n), y ∈ {i, i + 1, . . . , i + K1 − 1} (mod K2 )}
により誘導される部分グラフは補比較可能でありパーフェクトである．
k
系 7. Tm,n
において，任意の i ∈ {1, 2, . . . , 2k + 1} に対し，
def.
Vi = {(x, y) | (x, y) ∈ T (m, n), y ∈ {i, i + 1, . . . , i + k} (mod 2k + 1)}
により誘導される部分グラフは補比較可能でありパーフェクトである．
©
ª
+ k に対し，
½
½
¹
º¾ µ
¹
º
¶¾
k+3
k+3
def.
Vi = (x, y) | (x, y) ∈ S(m, n), y ∈ i, i + 1, . . . , i +
mod
+k
2
2
k
において，任意の i ∈ 1, 2, . . . ,
系 8. k ≥ 2 のとき，Sm,n
¥ k+3 ¦
2
により誘導される部分グラフは補比較可能でありパーフェクトである．
n
j√
k
o
1, . . . , 3+2
d
+
1
に対し，
2
(
(
$√ %
) Ã
$√
%
!)
3
3+2
def.
Vi = (x, y) | (x, y) ∈ S(m, n), y ∈ i, i + 1, . . . , i +
d +1
mod
d +1
2
2
系 9. Sm,n (d) において，任意の i ∈
により誘導される部分グラフは補比較可能でありパーフェクトである．
3.3 有理彩色と非パーフェクト率
35
系 6 より，三角格子点上の単位円グラフの有理多重彩色に関して以下の定理 7 が成り立つ．
³
j
定理 7. (Tm,n , w) の有理多重彩色問題には多項式時間 1 +
√2 d
3
k j √
k´
2 −3
-近似解法
/ 3+ 4d
2
がある．
証明. まず，解法の概要を示す．
解法の最初のステップとして K2 種類の頂点重み関数 wk0 , k ∈ {0, 1, . . . , K2 − 1} を
(
wk0 (x, y)
=
0,
w(x,y)
K1 ,
n
j
k
o
y ∈ k, k + 1, . . . , k + √23 d − 1 (mod K2 ),
それ以外
と設定する．
解 法 の 次 の ス テ ッ プ と し て K2 個 の 有 理 多 重 彩 色 問 題 を 厳 密 に 解 く ．す な わ ち
(Tm,n (d), wk0 )，
k ∈ {0, 1, . . . , K2 − 1} の有理多重彩色問 題を別 々に解く．前節で 議論した ように，正
の 重 み の 頂 点 集 合 に よ り 誘 導 さ れ る 部 分 グ ラ フ の 連 結 成 分 は パ ー フ ェ ク ト な の で ，そ
れぞれの問題は多項式時間で厳密に解ける．パーフェクトグラフの有理多重彩色数は多
項式時間で見つかる．特に，補比較可能グラフの有理多重彩色数は最小費用サイクル流
問 題 の 解 法 を 用 い て 多 項 式 時 間 で 見 つ か る ．よ っ て ∀k ∈ {0, 1, . . . , K2 − 1} に 対 し て
χf (Tm,n (d), wk0 ) = (1/K1 )ω(Tm,n (d), K1 wk0 ) である．解法の最後のステップとして，得られ
た K2 個の有理多重彩色を合わせて元の問題の有理多重彩色とする．
解 法 の 近 似 率 を 見 積 も る ．頂 点 重 み 関 数 wk0 の 定 義 よ り ，∀k ∈ {0, 1, . . . , K2 − 1},
ω(Tm,n (d), K1 wk0 ) ≤ ω(Tm,n (d), w) で あ る ．よ っ て ，得 ら れ た 有 理 多 重 彩 色 は 高 々
(K2 /K1 )ω(Tm,n (d), w) 色を使っている．
定理 7 と同様にして，系 5，系 7，系 8，系 9 から以下の定理 8，定理 9，定理 10，定理 11 が
得られる．
1
, w) の有理多重彩色問題には多項式時間 (4/3)-近似解法がある．
定理 8. (Tm,n (1), w) = (Tm,n
k
定理 9. (Tm,n
, w) の有理多重彩色問題には多項式時間
³
2k+1
k+1
´
-近似解法がある．
³
定理 10. (Sm,n (d), w) の有理多重彩色問題には多項式時間 1 + bdc/
j√
3
2 d
k´
-近似解法が
ある．
¡
k
定理 11. (Sm,n
, w) の有理多重彩色問題には多項式時間 1 + k/
¥ k+3 ¦¢
2
-近似解法がある．
有理多重彩色問題は有理彩色問題を特殊な場合として含むので，上記の定理は，グラフが定理
の条件を満たすならば有理彩色問題にも近似解法があることを示している．
有理多重彩色数と最大重みクリーク数から「グラフがどのくらいパーフェクトでないか」を
導く指標として非パーフェクト率 (imperfection ratio) がある．グラフ G の非パーフェクト
率 Imp(G) は
½
def.
Imp(G) = max
w6=0
χf (G, w)
ω(G, w)
¾
36
第3章
格子状グラフの多重彩色問題
で定義される [26, 27, 46]．非パーフェクト率は，その定義より明らかに，常に 1 以上である．
定理 7，定理 9，定理 10，定理 11 より以下の系 10 が直ちに導かれる．
系 10. 非パーフェクト率は
k
j
1 ≤Imp(Tm,n (d)) ≤ 1 +
√2 d
3
k
j √
3+ 4d2 −3
2
4
≤ 1 + √ = 1.4619 . . . ,
5 3
2k + 1
≤ 2,
k+1
bdc
2
1 ≤Imp(Sm,n (d)) ≤ 1 + j √ k ≤ 1 + √ = 2.1547 . . . ,
3
3
2 d
k
1 ≤Imp(Tm,n
)≤
k
k
1 ≤Imp(Sm,n
) ≤ ¥ k+3 ¦ ≤ 2
2
を満たす．
3.4 最大重み安定集合問題の多項式時間近似解法
本節で扱う最大重み安定集合問題は，与えられたグラフ G = (V, E) と非負有理数頂点重み
関数 w : V → Q+ に対して，その重み
P
w(v) が最大となるような安定集合 S ⊆ V を見
P
つける問題である．最大重み安定集合の重み v∈C w(v) を最大重み安定数といい，α(G, w)
v∈S
で表す．
最大重み安定集合問題に関しては以下の定理が成り立つ．
定
 理 12. d
—
√
3+
j
>
1 の と き ，(Tm,n (d), w) の 最 大 重 み 安 定 集 合 問 題 の 多 項 式 時 間
4d2 −3
2

k — √ 2
3+ 4d −3
+
2
2
√
d
3
-近似解法がある．
j
証明. 簡単のため K1 =
½
Vi = (x, y)
def.
k
√
3+ 4d2 −3
，K2
2
j
=
k
√
3+ 4d2 −3
2
j
+
√2 d
3
k
と定義する．まず，
¯
½
¹
º
¾
¾
¯
¯ (x, y) ∈ P (m, n), y ∈ i, i + 1, . . . , i + √2 d − 1 (mod K2 )
¯
3
により誘導される K2 個の部分グラフ Li ，i ∈ {0, 1, . . . , K2 − 1} を作る．本章の主定理より
Li はパーフェクトである．さらにいうならば補比較可能グラフである．次に，(Li , w) の最大
重み安定集合問題を別々に解く．すなわち K2 個の最大安定集合問題を解く．こうして得られ
た (Li , w) の最大重み安定集合を Si∗ とする．最後に，w(S ∗ ) = maxi {w(Si∗ )} を達成する安
def.
∗
定集合 S ∗ ∈ {S0∗ , . . . , SK
} を出力する，ここで w(S) =
2 −1
P
v∈S
w(v) である．
(Tm,n (d), w) の最大重み安定集合を S max とする．この証明ではこれ以降 K1 w(S max ) ≤
def.
K2 w(S ∗ ) を示す．Simax = S max ∩ Vi と定義する．どの頂点も K2 個の誘導部分グラフに
PK2
w(Simax ) = K1 w(S max ) である．Simax は安定
よってちょうど K1 回カバーされるので i=1
3.5 多重彩色問題の多項式時間近似解法
集合であり，Si∗ は (Li , w) の最大重み安定集合なので
PK2
i=1
37
w(Simax ) ≤ K2 w(Si∗ ) である．
よって K1 w(S max ) ≤ K2 maxi {w(Si∗ )} である．
定理 12 と同様にして以下の定理 13，定理 14，定理 15，定理 16 も示せる．
1
定理 13. (Tm,n (1), w) = (Tm,n
, w) の最大重み安定集合問題には多項式時間 (3/4)-近似解法
がある．
k
定理 14. (Tm,n
, w) の最大重み安定集合問題には多項式時間
³
k+1
2k+1
´
µ
定理 15. (Sm,n (d), w) の最大重み安定集合問題には多項式時間
ある．
定理 16.
µ
k
(Sm,n
, w)
の最大重み安定集合問題には多項式時間
-近似解法がある．
j√
j√
k
3
2 d
k
3
2 d
+bdc
¶
-近似解法が
¶
b k+3
2 c
-近似解法がある．
b k+3
2 c+k
3.5 多重彩色問題の多項式時間近似解法
k
k
, w) の多重彩色問題の近似解法
, w)，(Sm,n (d), w)，(Sm,n
この節では (Tm,n (d), w)，(Tm,n
を提案する．近似解法の概要は定理 7 の証明で提案した解法と同じである．
k
McDiarmid，Reed [47] は (Tm,n (d), w) = (Tm,n
, w) の多重彩色問題の近似解法を提案し
た．彼らの解法で見つかる多重彩色は高々 (4/3)ω(Tm,n , w) + 1/3 色しか使わない．
提案する解法を以下の定理の証明で説明する．
定理 17. (Tm,n (d), w) の多重彩色問題に対して高々

1 +
j
k

√2 d
3
k  ω(Tm,n (d), w)
j √
3+ 4d2 −3
2
³j
+
k
√
3+ 4d2 −3
2
´
− 1 χ(Tm,n (d))
色しか必要としない多重彩色が得られる近似解法がある．
証明. 解法の概要を示す．
解法の最初のステップとして K2 個の頂点重み関数 wk0 ，k ∈ {0, 1, . . . , K2 − 1} を

j
k
 0,
√2 d − 1} (mod K2 ),
y
∈
{k,
k
+
1,
.
.
.
,
k
+
3
j
k
wk0 (x, y) =
 w(x,y) , その他の場合
K1
と設定する．解法の次のステップとして K2 個の多重彩色問題すなわち (Tm,n (d), wk0 )，
k ∈ {0, 1, . . . , K2 − 1} により定義される多重彩色問題を厳密に解き，K2 個の多重彩色を得る．
重みが正の頂点の集合により誘導される部分グラフの連結成分は全てパーフェクトなので，
それぞれの問題は多項式時間で厳密に解ける．そのため ∀k ∈ {0, 1, . . . , K2 − 1} に対して，
χ(Tm,n (d), wk0 ) = ω(Tm,n (d), wk0 ) である．w00 = w −
PK2 −1
k=0
wk0 とする．このとき w00 の各
要素は K1 − 1 以下である．そのため (Tm,n (d), w00 ) の多重彩色は Tm,n (d) の自明な彩色を
38
第3章
格子状グラフの多重彩色問題
K1 − 1 個合わせることによって得られる．得られた多重彩色は高々 (K1 − 1)χ(Tm,n (d)) 色し
か使わない．解法の最後のステップとして，得られた K2 + 1 個の多重彩色を合わせたものを
元の問題の多重彩色として出力する．頂点重み関数 wk0 の定義より ∀k ∈ {0, 1, . . . , K2 − 1}，
K1 ω(Tm,n (d), wk0 ) ≤ ω(Tm,n (d), w) である．このため，得られる多重彩色が使う色数は高々
(K2 /K1 )ω(Tm,n (d), w) + (K1 − 1)χ(Tm,n (d)) である．
以下の補題 15 は Tm,n (d) の彩色数の上界と下界を与えている．
2
補題 15. m, n が十分大きいならば，χ(Tm,n (d)) = db である．ここで db は P (m, n) 上の
頂点間のユークリッド距離のうち，d より大きいものの中で最小の値である．明らかに，
d < db ≤ bd + 1c である．
証明. 例えば McDiarmid [47] を参照されたい．
√
定 理 18 (Miyamoto, Matsui [48]). 多 重 彩 色 問 題 (Sm,n ( 2, w)) に 対 し て 高 々
√
(4/3)ω(Sm,n ( 2), w) + 4 色しか使わない多重彩色が得られる O(mn) 時間近似解法が存在
する．
証明. k ∈ {0, 1, 2, 3} に関して，頂点集合 S(m, n) を 4 つの分割 {Ak , Bk , Ck , Dk } に分ける．
すなわち
def.
Ak = {(x, y) ∈ S(m, n) | y = k (mod 4)},
def.
Bk = {(x, y) ∈ S(m, n) | y = k + 2 (mod 4)},
def.
Ck = {(x, y) ∈ S(m, n) | y = k + 1 (mod 4), x is odd}
∪ {(x, y) ∈ S(m, n) | y = k + 3 (mod 4), x is even},
def.
Dk = {(x, y) ∈ S(m, n) | y = k + 1 (mod 4), x is even}
∪ {(x, y) ∈ S(m, n) | y = k + 3 (mod 4), x is odd}
と定義する．そして頂点重み関数 wk , k ∈ {0, 1, 2, 3} を以下のように設定する．Ak に属する
def.
頂点の重みは 0 とする．Bk に属する頂点 v の重みは wk (v) = bw(v)/3c とする．Ck に属す
る頂点 v の重みは
(
bw(v)/3c,
w(v) = 0 (mod 3),
wk (v) =
bw(v)/3c + 1, w(v) ∈ {1, 2} (mod 3)
def.
とする．Dk に属する頂点 v の重みは
(
bw(v)/3c,
w(v) ∈ {1, 2} (mod 3),
wk (v) =
bw(v)/3c + 1, w(v) = 0 (mod 3)
def.
とする．定義より明らかに ∀v ∈ V, w(v) = w0 (v) + w1 (v) + w2 (v) + w3 (v) である．こうし
√
て得られた多重彩色問題 (Sm,n ( 2), wk ) は O(mn) で最適解が得られるのでそれらを合わせ
√
て多重彩色問題 (Sm,n ( 2), w) の実行可能解を得られる．
3.5 多重彩色問題の多項式時間近似解法
39
√
得られる多重彩色が高々 (4/3)ω(Sm,n ( 2), w) + 4 色しか使わないことを示す．それには
√
√
ω(Sm,n ( 2), wk ) ≤ (1/3)ω(Sm,n ( 2), w) + 1, ∀k ∈ {0, 1, 2, 3} を示せば十分である．V 0 を
√
def.
Sm,n ( 2) のクリークとし，V 00 = {(x, y) ∈ V 0 | wk (x, y) = bw(x, y)/3c + 1} と定義する．
|V 0 ∩ Ck | ≤ 1 かつ |V 0 ∩ Dk | ≤ 1 なので，wk の定義と合わせて考えると |Vk00 | ≤ 2 であ
P
P
る．Vk00 = ∅ ならば明らかである．|Vk00 | = 1 ならば， v∈V 0 w(v) ≥ 3( v∈V 0 wk (v) − 1) =
P
3 v∈V 0 wk (v) − 3 が成り立つ．|Vk00 | = 2 ならば，|V 0 ∩ Ck | = |V 0 ∩ Dk | = 1 なので，
P
P
P
v∈V 0 w(v) ≥ 3(
v∈V 0 w(v) − 2) + 1 + 2 = 3
v∈V 0 wk (v) − 3 である．よって定理は示さ
れた．
d = 1 のとき定理 17 は，(Tm,n (1), w) に対して必要とされる色数が高々 (4/3)ω(Tm,n (1), w)+
6 色である多重彩色を見つける近似解法の存在を示しているにすぎない．しかし，定理 18 の
証明と同様に重みの振り分けを工夫することによって多重彩色問題 (T m, n(1), w) のより良い
近似解法を構築できる．すなわち以下の定理 19 が得られる．
定理 19. 多重彩色問題 (Tm,n (1), w) に対して高々 (4/3)ω(Tm,n (1), w) + 4 色しか使わない多
重彩色が得られる多項式時間近似解法がある．
図 3.10 に定理 17 と定理 19 が示す，多重彩色問題 (Tm,n (d), w) に対する近似率の数値例を
示す．d = 2 のとき，Feder，Shende [20] は 7/3-近似解法を提案した．一方その場合，我々
2.2
2.1
2
1.9
ratio
1.8
1.7
1.6
1.5
1.4
1.3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
d
図 3.10. 定理 17 が示す近似率の数値例
の解法を適用すると得られる多重彩色で必要とされる色数は高々 (5/3)ω(Tm,n (d), w) + 14 で
ある．
定理 17 と同様に，以下の定理 20 が得られる．
40
第3章
格子状グラフの多重彩色問題
k
定理 20 (Miyamoto, Matsui [51]). k > 1 のとき，(Tm,n
, w) の多重彩色問題に対して高々
µ
2k + 1
k+1
¶
k
k
ω(Tm,n
, w) + kχ(Tm,n
)
色しか使わない多重彩色が得られる多項式時間近似解法がある．
m, n が十分大きいとき，χ(T k (m, n)) が O(k 2 ) で押さえられることは明らかである．図 3.11
に定理 20 と定理 19 が示す近似率の数値例を示す．
2
1.9
1.8
ratio
1.7
1.6
1.5
1.4
1.3
2
4
6
8
10
12
14
16
18
20
d
図 3.11. 定理 20 と定理 19 が示す近似率の数値例
k
, w) の多重彩色問題に対して高々
定理 21 (Miyamoto, Matsui [51]). (Sm,n
Ã
k
1 + ¥ k+3 ¦
!
µ¹
k
ω(Sm,n
, w)
+
2
º
¶
k+3
k
− 1 χ(Sm,n
)
2
色しか使わない多重彩色が得られる多項式時間近似解法がある．
図 3.12 に定理 21 が示す近似率の数値例を示す．
定理 22. (Sm,n (d), w) の多重彩色問題に対して高々


Ã$ √ %
!
bdc
3
1 + j √ k  ω(Sm,n (d), w) +
d − 1 χ(Sm,n (d))
3
2
d
2
色しか使わない多重彩色が得られる多項式時間近似解法がある．
図 3.13 に定理 22 が示す近似率の数値例を示す．
3.6 各種格子状グラフの多重彩色問題の計算困難性
41
3
2.8
2.6
ratio
2.4
2.2
2
1.8
1.6
1.4
2
4
6
8
10
12
14
16
18
20
16
18
20
d
図 3.12. 定理 21 が示す近似率の数値例
3
ratio
2.5
2
1.5
1
2
4
6
8
10
12
14
d
図 3.13. 定理 22 が示す近似率の数値例
3.6 各種格子状グラフの多重彩色問題の計算困難性
k
k
本節では (Tm,n (d), w), (Tm,n
, w), (Sm,n (d), w), (Sm,n
, w) の多重彩色問題の計算困難性
を論じる．McDiarmid, Reed は，次数が高々 3 の平面グラフが 3 彩色可能か判定する問題を
1
帰着することによって，(Tm,n (1), w) = (Tm,n
, w) の多重彩色問題が NP-困難であることを証
明した．よって d も入力としたときの多重彩色問題 (Tm,n (d), w) が NP-困難であることは明
らかである．しかし d が 1 より大きい定数のとき，多重彩色問題 (Tm,n (d), w) が NP-困難で
42
第3章
格子状グラフの多重彩色問題
あるか否かは自明ではない．詳しい証明は省略するが，与えられた Tm,n (1) と d に対して，そ
れを誘導部分グラフとして含む Tm0 ,n0 (d) が存在するような定数 m0 , n0 が必ず存在する．よっ
て d が 1 より大きい定数のとき，多重彩色問題 (Tm,n (d), w) は NP-困難である．同様の論法
k
k
が Tm,n
に対しても成り立つので，k が 1 より大きい定数のとき多重彩色問題 (Tm,n
, w) は
NP-困難である．
k
一般に，k が 2 以上の定数のとき多重彩色問題 (Sm,n
, w) が NP-困難であるか否かはわかっ
ていない．同様に，d が 1 より大きい定数のとき多重彩色問題 (Sm,n (d), w) が NP-困難で
√
2 のとき，すなわち重み付き対角格子グラフ
√
(Sm,n ( 2), w) の多重彩色問題は NP-困難である．
あるか否かはわかっていない．ただし d =
√
定 理 23 (Miyamoto, Matsui [48]). (Sm,n ( 2), w) が 与 え ら れ た と き ，そ れ が
√
(4/3)ω(Sm,n ( 2), w) より少ない色数で多重彩色できるか否か判定する問題は NP-完全で
ある．
証明. 頂点の次数が 3 あるいは 4 の平面グラフ H が 3 彩色可能か否か判定する問題は NP困難であることが知られている（例えば文献 [24] を参照）．この問題例（インスタンス）で
あるグラフ H が与えられたとき，「H が 3 彩色可能ならば，そのときに限り，3 彩色可
√
能な (Sm,n ( 2), w)」を H の大きさの多項式時間で作る手続きを示す．以下この証明では
√
(Sm,n ( 2), w) を m 行 n 列の非負整数行列 w ∈ Zm×n
で表す．行と列の添え字はそれぞれ
+
{1, . . . , m}，{1, . . . , n} とする．
まず，以下の 3 つの特別な対角格子グラフ L0 , L1 , L2 ：

0
0

L0 = 
1
0
0
0
2
0
2
0
1
0
0
0
1
0
2
0
2
0


0 0
0
0 2
0



1
 , L1 =  1 0
0 2
0
0 0
0

0 0
0 0

L2 = 
1 1
0 0
0 0
1
0
0
0
1
0
2
0
2
0
0
0
1
0
0
0
0
2
0
0
0
2
0
0
0
1
0
0
0
0
0
2
1
0
0
0
0
0
2
0
0
0
1
0
0

0
0

1

0
0
0
0
2
0
0
0
0
1
0
0
0
0
2
0
0

0
0

1
,
0
0
を用意する．添え字 {(1, 3), (3, 1), (3, 5), (5, 3)} に対応する L0 の 4 つの要素を「接点」と呼
ぶ．L0 を 3 色で塗るためには，すべての接点が同じ色でなければならない．同様に添え字
{(1, 3), (3, 1), (3, 5), (3, 11)} に対応する L1 の 4 つの要素を接点と呼ぶ．L1 を 3 色で塗るた
めには，すべての接点が同じ色でなければならない．添え字 {(3, 1), (3, 7)} に対応する L2 の
2 つの要素も接点と呼ぶ．L2 を 3 色で塗るためには，この 2 つの接点が異なる色でなければ
ならない．
次に，全ての頂点次数が 3 か 4 の平面グラフ H の細分を平面に埋め込み，H 0 を得る．この
とき以下の条件 (1)∼(4) を満たすようにする．(1)H 0 は H の細分である．(2)H 0 の全ての頂
点は整数格子点 {1, . . . , m0 } × {1, . . . , n0 } 上にある．(3)H 0 の全ての枝は水平か垂直であり，
3.6 各種格子状グラフの多重彩色問題の計算困難性
43
その長さは 1 である．(4)m0 と n0 は H の頂点数の多項式で押さえられる．例として図 3.14
に完全グラフ K4 の細分埋め込み H 0 を示す．H 0 のそれぞれの枝に 9 つの頂点を挿入して，
図 3.14. K4 の細分埋め込み
より細かい細分 H 00 を得る．例として，図 3.14 の細分埋め込みのより細かい細分を図 3.15 に
√
√
示す．次に，S10m0 ,10n0 ( 2) を作る．容易に分かるように，H 00 は S10m0 ,10n0 ( 2) の部分グラ
図 3.15. K4 の（より細かい）細分埋め込み
フである．与えられたグラフに対し，平面埋め込みを見つけるか，あるいは平面グラフでない
ことを判定する線形時間解法があるので [34]，ここまでの手続きは H の頂点数の多項式時間
44
第3章
格子状グラフの多重彩色問題
でできる．
最後に，頂点重みを決める．まず，全ての頂点の重みを 0 にする．H 00 の頂点のうちその次
√
√
数が 2 より大きいものに対応する S10m0 ,10n0 ( 2) の頂点からユークリッド距離で 2 2 以下の
ものを行列 L0 の重みで置き換える．グラフ H のそれぞれの枝に対応して H 00 のパス Pe があ
る．ここでそのパス Pe を頂点の並び (v0 , v1 , . . . , v10k ) で表す．その (v2 , . . . , v8 ) の重みを，
L2 あるいはそれを回転したものの重みで置き換える．このとき {v2 , v8 } が L2 の接点になる
ようにする．ここで L0 の重みで置き換えた頂点と L2 重みで置き換えたの頂点は，5 つ重な
りがあることに注意する．k ≥ 2 の場合は以下を繰り返す．全ての k 0 ∈ {1, 2, . . . , k − 1} に対
して，部分パス (v10k0 −2 , v10k0 −1 , . . . , v10k0 +8 ) およびその周辺の頂点の重みを L1 あるいはそ
の回転したものの重みで置き換える．そのとき頂点 v10k0 −2 が L1 の (1, 3), (3, 1), (5, 3) のい
ずれかに対応し，頂点 v10k0 +8 が L1 の (3, 11) に対応するようにする．先ほどと同様に，重な
る頂点は 5 つ出てくる．例として，図 3.15 の H 00 に対応して頂点の重みを置き換えたものを
図 3.16 に示す．（図 3.16 で重みが 0 の頂点は空白にしてある．）
1
2
2
2
1
1
2
2
2
2
1
1
1
2
2
2
1 2
1
1
2
1
2
1
2
1
1
2
2
2
2
1 2 1 2 1 2 1
2
2
1
1
2
2
1 2 1 2 1 2 1
2
2
1
1 1
1 1
2
2
1
1
2
1
2
1
2
2
2
2
1
2
1
2
2
1
1
1
2
2
2
1 2
1
1
2
2
1 1
2
1
2
1
2
1
2
2
1
1 1
2
1
2
1
2
1
2
2
1
1
2
1
2
1
2
1
1
2
1
2
1
2
1
1
2
2
2
2
2
2
1
1
1
図 3.16. K4 の帰着の図
√
L0 , L1 , L2 の定義より，こうして作られた (Sm00 n00 ( 2), w) は 4 彩色可能であり，そのク
リーク数が 3 であることは明らかである．そして H が 3 彩色可能であるならば，そのときに
√
限り，(Sm00 n00 ( 2), w) が 3 彩色可能であることは明らかである．よって元の問題が NP-完全
√
√
であることから，与えられた (Smn ( 2), w) が (4/3)ω(Smn ( 2), w) より少ない色数で多重彩
3.7 パーフェクトグラフを利用した解法の枠組み
45
色可能か否か判定する問題は NP-完全である．
この定理より，d も入力としたときの多重彩色問題 (Sm,n (d), w) は NP-困難であることがわ
かる．
3.7 パーフェクトグラフを利用した解法の枠組み
本節では，3.3 節，3.5 節で提案した解法を一般化し，有理多重彩色問題及び多重彩色問題に
対するパーフェクトな部分グラフを利用した解法の枠組みを提案する．
グラフと頂点重み関数の組 (G, w) に対して，頂点部分集合族 {V1 , . . . , Vk } は
1. すべての i に関して Vi により誘導される部分グラフ G[Vi ] がパーフェクトである，
2. ∪ki=1 Vi (G) = V (G) を満たす，
とする．また，グラフと頂点重み関数の組 (G, w) と頂点部分集合 V1 , . . . , Vk に対して，係数
a1 , . . . , ak は
P
i:v∈Vi
1/ai ≥ 1, ∀v ∈ V (G) を満たすものとする．まず，有理多重彩色問題に
対するパーフェクトグラフを利用した近似解法の枠組みを提案する．入力は有理多重彩色問題
(G, w)（ここで w : V (G) → Q+ ），頂点部分集合の列 (V1 , . . . , Vk )，係数ベクトル (a1 , . . . , ak )
である．出力は有理多重彩色 c : S(G) → Q+ である，ここで S(G) はグラフ G の安定集合族
である（すなわち，c は安定集合の重み関数である）．
有理多重彩色問題に対するパーフェクトグラフを利用した近似解法の枠組み
ステップ 1
i = 1, . . . , k に関して wi (v) := w(v)/ai , ∀v ∈ Vi とする．
ステップ 2
i = 1, . . . , k に関して，多重彩色問題 (G[Vi ], wi ) を独立に解く．得られた k 個の
多重彩色をそれぞれ c1 , c2 , . . . , ck とする．ここで ci は G[Vi ] の安定集合の重み関数で
あるが，便宜的に ci (S) := 0, ∀S ∈ S(G) \ S(G[Vi ]) とする．
ステップ 3
c1 , . . . , ck を合わせて c とする．すなわち c(S) :=
Pk
i=1 ci (S),
∀S ∈ S(G) と
する．
一般に，安定集合族 S(G) の大きさは G の大きさの多項式では押さえられない．よってス
テップ 2 は，ci を陽に出力すると，入力の多項式の手間では終わらない．しかし，Grötschel,
Lovász, Schrijver [31] によって提案された，パーフェクトグラフの多重彩色法を用いれば，
ci (S) > 0 を満たす S についてのみ ci を出力する等の工夫によって，ci の出力の大きさも，ス
テップ 2 の計算量も入力の大きさの多項式でおさえることができる．3.2.3 節で示した多重彩
色法は，頂点を定義域とする多重彩色関数を出力するように記述されているが，それらは容易
に，安定集合の重み関数を出力するように変更できる．
Pk
i=1 (1/ai )ω(G, w) 色しか使っていない
Pk
ことを容易に示すことができる．この枠組みは多項式時間 ( i=1 (1/ai ))-近似解法である．ち
上記の枠組みにより得られる有理多重彩色は高々
なみに，入力として (G, w) と頂点集合 {V1 , . . . , Vk } のみが与えられた場合，近似率の上界で
ある
Pk
i=1 (1/ai )
を最小にするような ai を求める問題を，k 個の非負変数と |V | 本の線形不
46
第3章
格子状グラフの多重彩色問題
等式からなる線形計画問題
minimize
k
X
bi
i=1
subject to
X
bi ≥ 1, ∀v ∈ V (G),
i:v∈Vi
bi ≥ 0, ∀i ∈ {1, . . . , k},
ただし bi = 1/ai ，を用いて得ることもできる．
例えば 3.5 節の「三角格子点上の頂点重み付き単位円グラフの有理多重彩色問題」の近似解法
はこの枠組みの特殊な場合である．すなわち定理 7 の証明において，Tm,n (d) が G に，wk0 > 0
となる頂点により誘導される部分グラフが Vi に対応し，K2 = k に，K1 = a1 = a2 = · · · = ak
となっている．
次に，多重彩色問題に対するパーフェクトグラフを利用した解法の枠組みを提案する．この
枠組みでは G の彩色 c0 : S(G) → {0, 1} が与えられているものとする．彩色 c0 は最適彩色
でなくてもよい．入力は多重彩色問題 (G, w)，頂点部分集合の列 (V1 , . . . , Vk )，係数ベクトル
(a1 , . . . , ak )，G の彩色 c0 である．出力は多重彩色 c : S(G) → Z+ である．
多重彩色問題に対するパーフェクトグラフを利用した解法の枠組み
ステップ 1
P
i = 1, . . . , k に関して wi (v) := bw(v)/ai c, ∀v ∈ Vi とする．w := max{w(v) −
i:v∈Vi
ステップ 2
wi (v) | ∀v ∈ V (G)} とする．
i = 1, . . . , k に関して，多重彩色問題 (G[Vi ], wi ) を独立に解く．得られた k 個の
多重彩色を ci : S(G[Vi ]) → Z+ (i = 1, . . . , k) とする．ここで ci は G[Vi ] の安定集合
の重み関数であるが，便宜的に ci (S) := 0, ∀S ∈ S(G) \ S(G[Vi ]) とする．
ステップ 3
c1 , . . . , ck と w 個の c0 を合わせて c とする．すなわち c(S) :=
Pk
i=1 ci (S)
+
wc0 (S), ∀S ∈ S(G) とする．
上記の枠組みの w は，直感的には，ci による塗り残しの数を表している．
この枠組みにより得られる多重彩色は高々
0
Pk
0
i=1 (1/ai )ω(G, w) + w|c |
0
色しか使っていない
ことを容易に示すことができる，ここで |c | は c 彩色で使われる色数である．この枠組みは多
項式時間解法である．
例えば 3.5 節の「三角格子点上の頂点重み付き単位円グラフの多重彩色問題」の近似解法
はこの枠組みの特殊な場合である．定理 17 の証明において，Tm,n (d) が G に，wi0 > 0 を
満たす頂点部分集合が Vi に，Tm,n (d) の χ(Tm,n (d))-彩色が彩色 c0 に対応しており，また，
K2 = k, K1 = a1 = a2 = · · · = ak , w = K1 − 1 となっている．Tm,n (d) に代表される格子
状グラフの場合には，上記枠組みの w を定数として見積もれるため，上記枠組みは近似解法
となる．
3.8 まとめと考察
47
3.8 まとめと考察
k
k
本章では Tm,n (d), Tm,n
, Sm,n (d), Sm,n
がパーフェクトである条件を整理し，有理多重彩
色問題の多項式時間近似解法，最大重み安定集合問題の多項式時間近似解法，多重彩色問題の
√
多項式時間近似解法を提案した．さらに Sm,n ( 2) の多重彩色問題が NP-困難であることも
示した．
k
k
Tm,n (d), Tm,n
, Sm,n
に関しては n, d, k の観点からパーフェクトであるための必要十分条
件を示し，パーフェクトである場合と非パーフェクトである場合の境界が単調になるという
k
k
美しい結果を得た．Tm,n (d), Tm,n
, Sm,n
が「パーフェクトであるための十分条件」と「非
パーフェクトであるための十分条件」を別々に示しながら結果としてパーフェクトであるため
の必要十分条件になっていることは興味深い．残念ながら Sm,n (d) に関しては n, d の観点か
らパーフェクトであるための必要十分条件を導くには至らなかった．Sm,n (d) に関しては n, d
の観点からパーフェクトであるための十分条件と非パーフェクトであるための十分条件を別々
に示した．n, d の観点から Sm,n (d) がパーフェクトであるための必要十分条件を導くことは
1
今後の課題といえる．Tm,3 (1) = Tm,3
がパーフェクトであることは本論文で初めて得られた
1
結果であると思われる．Tm,3 (1) = Tm,3
はパーフェクトであるが，比較可能グラフ，補比較
可能グラフ，三角化可能グラフなどの有名なパーフェクトグラフクラスには含まれていない．
しかし，2005 年現在，200 種類以上のパーフェクトグラフクラスが知られていると言われてお
り，そのどれにも含まれないか否か確認することは容易ではない．今までに知られているパー
フェクトグラフクラスに含まれるか否か確認することも今後の課題である．
k
k
がパーフェクトである条件を元に有理多重彩色問題の多項
, Sm,n (d), Sm,n
Tm,n (d), Tm,n
式時間近似解法，最大重み安定集合問題の多項式時間近似解法，多重彩色問題の多項式時間近
似解法を提案した．表 3.6 に本章で提案した近似解法の近似率をまとめる．有理多重彩色問
題と多重彩色問題の近似率は同じであり，最大重み安定集合問題の近似率は多重彩色問題の
k
k
, Sm,n
がパーフェクトである条件が必要十分条
近似率の逆数になっている．Tm,n (d), Tm,n
表 3.6. 各近似解法の近似率
k
Tm,n
Tm,n (d)
j
1+
（有理）多重彩色問題
—
√
最大重み安定集合問題
—
√
4d2 −3
√
2
3+ 4d2 −3
√
2
k
Sm,n
k
2
√
d
— √3
3+ 4d2 −3
√
2
3+
Sm,n (d)
2k+1
k+1
1+
j
k
+ √23 d
j
k+1
2k+1
j
j bdc k
2
√
d
3
k
2
√
d
3
k
2
√
d
3
+bdc
1+
k
b k+3
2 c
b k+3
2 c
b k+3
2 c+k
48
第3章
格子状グラフの多重彩色問題
件であることから，多重彩色問題に対してこれ以上良い近似率を持つ近似解法を，同様の方
法で構築することは困難と思われる．以下，本章で提案した近似解法の近似率を既存の結果
と比較する．McDiarmid, Reed [47] は三角格子グラフ Tm,n 上の多重彩色問題 (Tm,n , w) の
多項式時間近似解法を提案している．彼らの解法により高々 (4/3)ω(Tm,n , w) + (1/3) 色しか
使わない多重彩色が得られる．彼らの解法は 2 フェイズからなるものであり，フェイズ 1 で
ω(Tm,n , w) 色を使って各頂点に色を割り当て，フェイズ 2 で塗り残されている重みの分の色を
割り当てる，というものである．特にフェイズ 2 において「塗り残しがある頂点により誘導さ
れる部分グラフが 2 部グラフになる」という性質を使って良い近似率を達成している．この性
質は入力グラフが三角格子グラフであるという事実に強く依存しており，より広いグラフクラ
スへの拡張が難しいと思われる．なおフェイズ 1 は格子状のグラフであれば拡張可能であり，
実際，Tm,n (2) 上の多重彩色問題 (Tm,n (2), w) の Feder, Shende による (7/3)-近似解法 [20]
はフェイズ 1 の拡張になっている．一方本章で提案した三角格子点上の単位円グラフの多重
彩色問題の多項式時間近似解法を三角格子グラフに適用した場合は高々 (4/3)ω(Tm,n , w) + 4
色しか使わない多重彩色が得られる．近似率において，定数項の分だけ McDiarmid, Reed の
解法に劣るが，本章で論じたとおり三角格子グラフを含む広いグラフクラスに適用可能であ
ることが特長である．(Tm,n (2), w) に適用した場合は高々 (5/3)ω(Tm,n (2), w) + 21 （定数項
は ω(Tm,n (2)) = 7 より得られる）色しか使わない多重彩色が得られ，定数項を無視すれば
Feder, Shende の解法より優れている．
なお，3.5 節で示した多重彩色問題の解法は，得られる解の目的関数値が αZ ∗ + β の形で表
されるものであり，厳密には近似率が α の近似解法（α-近似解法）と呼べるものではない．た
√
だし d < 6 3 のときは，簡単な改訂により (Tm,n (d), w) の多項式時間 2-近似解法を構築でき
る．なぜならば
½
V1 = (x, y)
def.
¯
½
¹
º¾
¾
¯
¯ (x, y) ∈ T (m, n), y ∈ 1, 2, . . . , √2 d
(mod K2 )
¯
3
により誘導される Tm,n (d) の部分グラフはパーフェクトであり，T (m, n) \ V1 により誘導され
る Tm,n (d) の部分グラフもパーフェクトだからである．これら 2 つのグラフについて多重彩
色問題を厳密に解き，それを統合することで 2-近似解法を構築することができる．上記の解法
を (Tm,n (2), w) に適用した場合の近似率は 2 である．よって多重彩色問題 (Tm,n (2), w) の近
似解法としては，上記の解法は近似率の意味で Feder, Shende [20] の (7/3)-近似解法よりも
良い．
最大重み安定集合問題の近似解法は同時に最小重み被覆問題の近似解法にもなっている．一
般のグラフの最小重み被覆問題の 2-近似解法が知られており，また，本章で提案した解法を最
小重み被覆問題に適用した場合の近似率は 2 以上である．よって最小重み被覆問題の近似解法
という観点では，良い近似率が得られているわけではない．
本章では，既存の研究および Philadelphia 問題例の抽象化という観点から，平面上の格子
点を頂点集合とするグラフを扱った．本章で行ったパーフェクトな部分グラフの特徴付けおよ
びそれを基にした近似解法の構築は，3 次元以上の高次元空間内の格子点を頂点集合とするグ
ラフに対しても適用できる．しかし本章の手法を高次元の問題に適用すると近似率は非常に悪
3.8 まとめと考察
49
いものとなる．本章の手法の近似率は「与えられたグラフの頂点数」における「最適に解ける
誘導部分グラフの頂点数」の割合に依存しており，次元が高くなるとその割合は減少するから
である．また，高次元空間に拡張した問題に対する具体的な応用はほとんど知られていない．
今後の課題として近似解法のタイトな例を見つけることも挙げられる．三角格子グラフの多
重彩色問題と対角格子グラフの多重彩色問題のみ NP-困難性の証明からタイトであると分か
るが，それ以外の問題例に関してはタイトかどうかは分からない．
本研究の動機の 1 つとして，単位円グラフの頂点彩色問題の近似解法の構築があった．与え
られた単位円グラフを三角格子点上の単位円グラフで効率よく近似できれば，単位円グラフの
彩色問題の近似率が 3 より小さい多項式時間近似解法を構築できるかもしれない．今後の課題
として三角格子点上の単位円グラフの多重彩色問題の近似解法を元にして，一般の単位円グラ
フの彩色問題の近似解法を構築することも挙げられる．
50
第4章
チャネル割当問題
本章では最小スパンチャネル割当問題の多項式時間近似解法を論じる．入力グラフとして
パーフェクトグラフ，単位円グラフ，Philadelphia 問題例の入力グラフなどを扱う．最小スパ
ンチャネル割当問題およびそのベンチマークの一つである Philadelphia 問題例，単位円グラ
フ上のチャネル割当問題などの実用的な背景に関しては 1.4 節を参照されたい． 本章で示す
結果の多くは Miyamoto, Matsui による文献 [52, 53, 49] で既に発表されているものである．
既に発表されている定理，補題，系に関しては対応する文献を明記してある．対応する文献が
明記されていないものは本論文で初めて示されるものである．
4.1 チャネル割当問題の定義
グラフ G = (V, E)，非負整数頂点重み関数 w : V → Z+ ，非負整数枝長さ関数 l : E → Z+ ，
非負整数定数 k ∈ Z+ が与えられたとき，割当 f : V → 2N で
|f (v)| ≥ w(v),
∀v ∈ V,
|f1 − f2 | ≥ k,
∀v ∈ V, ∀f1 , f2 ∈ f (v),
|f1 − f2 | ≥ l({u, v}),
∀{u, v} ∈ E, ∀f1 ∈ f (u), ∀f2 ∈ f (v)
を満たすものを (G, w, l, k) のチャネル割当という．本論文では，チャネル割当 f (v) の
def.
要素である自然数をチャネルと呼ぶ．チャネル割当 f のスパン span(f ) を span(f ) =
max{f1 − f2 + 1 | f1 , f2 ∈ ∪v∈V f (v)} と定義する．(G, w, l, k) のチャネル割当 f のうち，
そのスパン span(f ) が最も小さいチャネル割当を見つける問題を (G, w, l, k) の最小スパン
チャネル割当問題という．以下本章では最小スパンチャネル割当問題をチャネル割当問題
と略す．チャネル割当問題は多重彩色問題を特殊な場合として含む．正確に述べるならば，
∀{u, v} ∈ E, l({u, v}) = 1 かつ k = 1 のとき，チャネル割当問題は多重彩色問題となる．
よって明らかに，チャネル割当問題は NP-困難である．また，ハミルトン路問題を G が完全
グラフであるチャネル割当問題に多項式時間帰着できるため，入力グラフを完全グラフに限定
しても，チャネル割当問題は NP-困難である．入力グラフを完全グラフに限定した多重彩色問
題は自明に多項式時間で解けることと対照的である．
4.2 枝の重みが全て同じ場合のチャネル割当問題の近似解法
51
4.2 枝の重みが全て同じ場合のチャネル割当問題の近似解法
本節では，枝の重みが全て同じ場合のチャネル割当問題の多項式時間近似解法を提案する．
すなわち本節では，0 < ∃l ≤ k, ∀e ∈ E, l(e) = l を仮定する．以下ではグラフ G = (V, E)，
非負整数頂点重み関数 w : V → Z+ ，正整数枝長さ l ∈ N，非負整数 k ∈ Z+ ，ただし l ≤ k ，
を入力とする多重チャネル割当問題 (G, w, l, k) を考える．この問題は NP-困難である．なぜ
ならば，本節の仮定を入れてもなお，チャネル割当問題は一般のグラフの多重彩色問題を特殊
な場合として含むからである．
グラフ G と頂点重み関数 w が与えられたとき，その重みが d 以上の頂点で誘導される部分
グラフを (G, w)≥d とする．すなわち
def.
(G, w)≥d = G[V 0 ],
V 0 = {v ∈ V | w(v) ≥ d}
と定義する．明らかに，d ≤ d0 ならば (G, w)≥d0 は (G, w)≥d の誘導部分グラフである．本節
では頂点重み w(v) の最大値を W で表す．以下にチャネル割当法 1 を提案する．チャネル割
当法 1 の入力はチャネル割当問題 (G, w, l, k)，出力はチャネル割当 f である．
チャネル割当法 1
ステップ 1
グラフ (G, w)≥1 の彩色を見つける（最適彩色でなくてもよい）．見つけた彩色に
使った色を {1, . . . , c} とする．
ステップ 2
色 i が割り当てられた頂点 v のチャネル割当を
f (v) := {1 + (i − 1)l, 1 + (i − 1)l + max{cl, k}, . . . , 1 + (i − 1)l + (w(v) − 1) max{cl, k}}
とし，f を出力する．
チャネル割当法 1 が出力するチャネル割当 f のスパン span(f ) は
span(f ) ≤ 1 + (c − 1)l + (W − 1) max{cl, k} ≤ cl + (W − 1) max{cl, k} ≤ W max{cl, k}
を満たす．特に ω(G) = 1 のとき χ(G) = ω(G) = 1 が成り立ち，G の自明な 1-彩色が存在
し，これを用いたチャネル割当法 1 は任意の頂点重みに対し最適解を出力する．本節の仮定よ
り l ≤ k なので，ステップ 1 で 1-彩色が用いられたとき，span(f ) ≤ 1 + (W − 1)k が成り立
つ．ステップ 2 で割り当てられるチャネルは等差数列となっている．この等差数列
( 1 + (i − 1)l, 1 + (i − 1)l + max{cl, k}, . . . , 1 + (i − 1)l + (w(v) − 1) max{cl, k} )
を陽に記憶するために必要な領域は w(v) に比例する．しかし，上記の等差数列の初項
1 + (i − 1)l，公差 max{cl, k}，項数 w(v) のみを記憶すれば記憶に必要な領域を削減すること
ができる．よって，ステップ 1 で多項式時間彩色法を使い，かつ，得られたチャネル割当を
表す等差数列を（初項，公差，項数）の 3 つ組で出力するならば，チャネル割当法 1 の計算
時間は問題の入力サイズの多項式で押さえられる．ここでチャネル割当問題の入力の大きさは
O(|V |dlog(W + 1)e + |E|dlog(L + 1)e + dlog ke) である．ただし L は枝長さの最大値である．
52
第4章
チャネル割当問題
列 (W (1), W (2), . . . , W (n)) を
def.
W (q) = max{d | ω((G, w)≥d ) ≥ q},
q ∈ {1, . . . , n}
と定義する．ただし n は与えられたグラフの頂点数である．この定義より，直感的には
(W (1), W (2), . . . , W (n)) は「重みの昇順に頂点を除いていったときにクリーク数が減る頂点
の重みを並べた数列」と理解できる．明らかに W = W (1) ≥ W (2) ≥ · · · ≥ W (n) である．
頂点重み関数列 (w1 , w2 , . . . , wn ) を
def.
∀v ∈ V,
def.
∀v ∈ V,
wn (v) = min{W (n), w(v)},
wq (v) = min{W (q), w(v)} − min{W (q + 1), w(v)},
∀q ∈ {1, . . . , n − 1}
と定義する．この定義より
wn (v) + wn−1 (v) + · · · + wq (v) = min{W (q), w(v)},
∀v ∈ V,
∀q ∈ {1, 2, . . . , n}
が成り立つことが確認できる．また明らかに w1 (v) + w2 (v) + · · · + wn (v) = w(v), ∀v ∈ V
も成り立つ．以下にチャネル割当法 2 を提案する．チャネル割当法 2 では，与えられた問題を
wq (v) で定義される部分問題に分解し，各部分問題をチャネル割当法 1 で独立に解き，得られ
た解を統合して出力する．チャネル割当法 2 の入力はチャネル割当問題 (G, w, l, k)，出力は
チャネル割当 f である．
チャネル割当法 2
ステップ 1
W = 1 ならば，(G, w, l, k) をチャネル割当法 1 で解き，得られた割当 f を出力
し，終了する．
ステップ 2
W (1), . . . , W (n) を計算し，(w1 , . . . , wn ) を構成する．
ステップ 3
それぞれの q ∈ {1, . . . , n} に対してチャネル割当問題 (G, wq , l, k) をチャネル割
当法 1 で解く．得られた割当をそれぞれ f q とする．
ステップ 4
f q を統合してチャネル割当問題 (G, w, l, k) の割当 f を構成する．すなわち
f (v) := ∪nq=1 {c + p0 + p1 + · · · + pq−1 | c ∈ f q (v)},
∀v ∈ V
とする．ここで
(
0,
q = 0 あるいは span(f q ) = 0,
p =
span(f q ) + k − 1, それ以外,
q
である．
チャネル割当法 2 において
span(f ) ≤
n
X
span(f q ) + (k − 1)(W − 1)
q=1
が成り立つ．なぜならば任意の頂点 v に対して
Pn
q=1
wq (v) ≤ W かつ ∀q, wq (v) ≥ 0 が成り
立つので ∃v ∈ V, wq (v) > 0 となる q は W 個以下であり，span(f q ) > 0 が出力されるチャネ
4.2 枝の重みが全て同じ場合のチャネル割当問題の近似解法
53
ル割当問題 (G, wq , l, k) は W 個以下だからである．特に ω(G) = 1 のとき，χ(G) = ω(G) = 1
が自明に成り立ち，チャネル割当法 2 はチャネル割当法 1 と本質的に一致し，最適解を出力
する．
チャネル割当問題の最適値の下界に関して以下の補題 16 が成り立つ．
補題 16. チャネル割当問題 (G, w, l, k) の最適値 Z ∗ は
Z ∗ ≥ 1 − k + kW,
Z ∗ ≥ 1 − l + qlW (q),
∀q ∈ {2, . . . , n}
を満たす．
証明. 頂点 v には少なくとも w(v) 個のチャネルを割り当てなければならない．そして同じ頂
点に割り当てるチャネルは少なくとも k 以上離れなければならない．よって ∀v ∈ V, Z ∗ ≥
1 + k(w(v) − 1) = 1 − k + kw(v) である．ここで w(v) = W を満たす頂点を選ぶと，
Z ∗ ≥ 1 − k + kW
(4.1)
が成り立つ．
W (q) の定義より，頂点数が q のクリークで，属する頂点の重みが全て W (q) 以上のものが
少なくとも 1 つ存在する．そのクリーク中の頂点に割り当てるチャネルの総数は少なくとも
qW (q) 以上である．そして割り当てるチャネルは，任意の対において少なくとも min{l, k} = l
以上離れなければならない．よって
Z ∗ ≥ l(qW (q) − 1) + 1 = 1 − l + lqW (q),
∀q ∈ {2, . . . , n}
(4.2)
である．
式 (4.1)，(4.2) により補題は示された．
チャネル割当法 1，チャネル割当法 2 の直後で述べたとおり，与えられたグラフのクリー
ク数が 1 の場合には，チャネル割当法 1，チャネル割当法 2 は最適解を出力する．以下では
ω(G) ≥ 2 かつ W = 1 のときのチャネル割当法 2 の近似率を見積もる．
補題 17. ω(G) ≥ 2 かつ W = 1 のとき，チャネル割当法 2 の近似率は (c − 1)/(ω(G) − 1) 以
下である．
証明. W = 1 のとき，チャネル割当法 1 が出力する割当のスパンは 1 + (c − 1)l である．補題
16 より ∀q ∈ {2, . . . , n}, Z ∗ ≥ 1 − l + lqW (q) であり，特に Z ∗ ≥ 1 − l + lω(G)W (ω(G)) で
ある．c ≥ ω(G) ≥ 2 より，チャネル割当法 2 の近似率は
1 + (c − 1)l
1 + (c − 1)l
c−1
1 + (c − 1)l
≤
=
≤
∗
Z
1 − l + lω(G)W (ω(G))
1 + (ω(G) − 1)l
ω(G) − 1
を満たす．
グラフ (G, wq )≥1 のクリーク数に関して以下の補題が成り立つ．
54
第4章
チャネル割当問題
補題 18. 任意の q ∈ {1, . . . , n} に関して，グラフ (G, wq )≥1 のクリーク数は q 以下である．
証明. 背理法で示す．グラフ (G, wq )≥1 が大きさ q + 1 以上のクリーク Q を持つと仮定する．
クリーク Q の頂点 v の重みに関して 0 < wq (v) = min{W (q), w(v)} − min{W (q + 1), w(v)}
が成り立つ．よって w(v) > W (q + 1) である．これより Q はグラフ (G, w)≥W (q+1)+1 に含
まれることになるが，Q の大きさが q + 1 であるという仮定に矛盾する．
4.2.1 パーフェクトグラフに適用した場合の近似率
ここでは，パーフェクトグラフにチャネル割当法 2 を適用した場合について論じる．パー
フェクトグラフの任意の誘導部分グラフは再びパーフェクトとなるため，そのクリーク数は入
力の大きさの多項式時間で計算できることが知られている．よって (W (1), . . . , W (n)) を，頂
点重みに関する二分探索を行うことにより，多項式時間で計算できる．ゆえにチャネル割当法
2 の計算時間は入力の大きさの多項式で押さえられる．
定理 24. G をパーフェクトグラフとする．W = 1 のとき，チャネル割当法 2 はチャネル割当
問題 (G, w, l, k) の最適解を出力する．W ≥ 2 のとき，チャネル割当法 2 はチャネル割当問題
³
³
(G, w, l, k) の多項式時間 1 + 1 +
1
W −1
´
´
Hω(G) -近似解法である．
証明. ω(G) = 1 の場合は自明なので省略する．
ω(G) ≥ 2 かつ W = 1 のとき，補題 17 より近似率は
χ(G)−1
ω(G)−1
= 1 で押さえられる．よって
このときチャネル割当法 2 は最適解を出力する．
ω(G) ≥ 2 かつ W ≥ 2 のとき，G がパーフェクトであることより χ((G, wq )≥1 ) =
ω((G, wq )≥1 ) であり，補題 18 より ω((G, wq )≥1 ) ≤ q である．q ∈ {1, . . . , n} に関して，
G がパーフェクトであることよりチャネル割当法 1 のステップ 1 において多項式時間で
(G, wq )≥1 の最適彩色を得ることができる．よってチャネル割当法 1 は q ∈ {1, . . . , n} に
関して，そのスパンが W q max{ql, k} で押さえられるチャネル割当を出力する，ここで
W q = max{wq (v) | v ∈ V } である．以下の証明では W (n + 1) = 0 とする．チャネル割当問
4.2 枝の重みが全て同じ場合のチャネル割当問題の近似解法
55
題 (G, w, l, k) の最適値を Z ∗ とし，チャネル割当法 2 の出力を f とすると
span(f ) ≤ (k − 1)(W − 1) +
n
X
W q max{ql, k}
q=1
ω(G)
= (k − 1)(W − 1) +
X
W q max{ql, k}
q=1
ω(G)
≤ k(W − 1) +
X
(W (q) − W (q + 1)) max{ql, k}
q=1
ω(G)
∗
≤ Z + W (1) max{l, k} +
X
W (q)(max{ql, k} − max{(q − 1)l, k})
q=2
ω(G)
∗
≤ Z + Wk +
X
W (q)l
q=2
ω(G)
≤ Z ∗ + (Z ∗ + k − 1) + (Z ∗ + l − 1)
X 1
q
q=2
ω(G)
∗
∗
∗
≤ Z + (Z + k) + (Z + k)
X 1
q
q=2
µ
¶ ω(G)
Z∗ − 1 X 1
≤Z + Z +
W − 1 q=1 q
µ
µ
¶
¶
1
Hω(G) Z ∗
≤ 1+ 1+
W −1
∗
∗
が成り立つ．
4.2.2 単位円グラフに適用した場合の近似率
ここでは単位円グラフにチャネル割当法 2 を適用した場合について論じる．本節では入力グ
ラフの頂点数を n とする．1990 年に Clark, Colbourn, Johnson によって，単位円グラフの
最大クリークを O(n4.5 ) で得る解法が提案された [16] （2.4 節参照）．ゆえに頂点重みに関す
る二分探索を用いることにより，(W (1), . . . , W (n)) を多項式時間で求めることができる．ま
た，1995 年に Marathe, Breu, Hunt, Ravi によって，単位円グラフ G の彩色問題の多項式時
間解法として，高々 3ω(G) − 2 の色数の彩色を O(n2 ) で得る解法が提案されている [43]（2.4
節参照）． この解法をチャネル割当法 1 のステップ 1 で用いることにより，計算量が多項式
時間となるチャネル割当法 2 を構築することができる．こうして構築されたチャネル割当法 2
に関して以下の定理 25 が成り立つ．
定理 25. G を単位円グラフとする．W = 1 のとき，チャネル割当法 2 はチャネル割当問題
(G, w, k, l) の多項式時間 3-近似解法である．W ≥ 2 のとき，チャネル割当法 2 はチャネル割
56
第4章
チャネル割当問題
³
当問題 (G, w, k, l) の多項式時間 1 +
1
W −1
´
(3Hω(G) − 1) -近似解法である．
証明. ω(G) = 1 のときは自明なので省略する．
ω(G) ≥ 2 かつ W = 1 のとき，補題 17 より近似率は
c−1
3ω(G) − 2 − 1
≤
=3
ω(G) − 1
ω(G) − 1
である．
ω(G) ≥ 2 かつ W ≥ 2 の場合を考える．補題 18 より ω((G, wq )≥1 ) ≤ q が成り立ち，
q ∈ {1, . . . , n} に関して，チャネル割当法 1 のステップ 1 において多項式時間で (G, wq )≥1
の (3q − 2)-彩色を得ることができる．よってチャネル割当法 1 は q ∈ {1, . . . , n} に関し
て，そのスパンが W q max{(3q − 2)l, k} で押さえられるチャネル割当を出力する，ここで
W q = max{wq (v) | v ∈ V } である．以下の証明では W (n + 1) = 0 とする．チャネル割当問
題 (G, w, l, k) の最適値を Z ∗ とし，チャネル割当法 2 の出力を f とすると
span(f ) ≤ (k − 1)(W − 1) +
n
X
W q max{(3q − 2)l, k}
q=1
ω(G)
= (k − 1)(W − 1) +
X
W q max{(3q − 2)l, k}
q=1
ω(G)
≤ k(W − 1) +
X
(W (q) − W (q + 1)) max{(3q − 2)l, k}
q=1
ω(G)
X
≤ Z ∗ + W (1) max{l, k} +
W (q)(max{(3q − 2)l, k} − max{(3q − 5)l, k})
q=2
ω(G)
≤ Z∗ + W k +
X
W (q)3l
q=2
ω(G)
∗
∗
∗
≤ Z + (Z + k − 1) + (Z + l − 1)
ω(G)
≤ 2(Z ∗ + k) + (Z ∗ + k)
ω(G)
X 3
q
q=2
X 1
− (Z ∗ + k)
q
q=1
µ
¶
∗
Z −1
≤ Z∗ +
(3Hω(G) − 1)
W −1
µ
¶
1
≤ 1+
(3Hω(G) − 1)Z ∗
W −1
∗
≤ (Z + k)3
が成り立つ．
X 3
q
q=2
4.2 枝の重みが全て同じ場合のチャネル割当問題の近似解法
57
4.2.3 より広いグラフクラスへの適用
ここまではパーフェクトグラフにチャネル割当法 2 を適用した場合の近似率，単位円グラフ
にチャネル割当法 2 を適用した場合の近似率を議論した．以下ではより広いグラフクラスへの
チャネル割当法 2 の適用を議論する．
グラフクラス G において以下の性質が満たされるとする．
1. 任意の G ∈ G において，H が G の誘導部分グラフならば，H ∈ G である．
2. 任意の G ∈ G において，G の彩色問題に対する多項式時間 α-近似解法がある．
3. 任意の G ∈ G において，G の最大クリーク問題に対する多項式時間厳密解法がある．
このときチャネル割当法 2 は G ∈ G 上のチャネル割当問題を解く多項式時間
³
³
1+ 1+
´
αHω(G) -近 似 解 法 と な る ．パ ー フ ェ ク ト グ ラ フ は α = 1 の 場 合 で あ
³
´
り，単位円グラフは α = 3 の場合である．ただし 1 + 1 + W1−1 αHω(G) の α に 3 を代入す
1
W −1
´
ると，定理 25 で示された近似率よりも若干悪くなる．これは定理 25 で近似率を見積もる際
に，3-近似解法ではなく，高々 3ω(G) − 2 色を使う彩色解法を用いて議論したためである．こ
のように彩色問題の近似解法において，よりタイトな見積もりを使えば，チャネル割当法 2 に
おける近似率も改善されることがある．単位円グラフはその一例である．また 3 章の結果よ
√
り，Tm,n (d), d < 6 3 は α = 2 の例になっている．
次に，一般のグラフにチャネル割当法 2 を適用する場合の近似率に関して議論する． 一般
のグラフのクリーク数を計算する問題は NP-困難であり，(W (1), W (2), . . . , W (n)) を多項式
時間で計算するのは困難である．故に，多項式時間解法としてチャネル割当法 2 を構築するの
は難しい．以下では，グラフ G の c-彩色が与えられているという仮定のもとで，チャネル割
当法 2 を改訂して一般のグラフに適用することを考える．与えられたグラフの任意の誘導部
分グラフにおいて枝集合が空か否かは多項式時間で判定できるため，頂点重みに関する 2 分
探索を用いれば W (2) は多項式時間で計算できる．この事実に注目し，新たに頂点重み関数
w
e1 , w
e2 を導入し
def.
w
e2 (v) = min{W (2), w(v)},
def.
w
e1 (v) = w(v) − w
e2 (v),
∀v ∈ V,
∀v ∈ V
と定義する．以下にチャネル割当法 2 を改訂したチャネル割当法 3 を提案する．チャネル割
当法 3 ではチャネル割当問題 (G, w, l, k) を部分問題 (G, w
e1 , l, k), (G, w
e2 , l, k) に分解し，部
分問題をチャネル割当法 1 で独立に解いて，得られた解を統合して出力する．ただしチャネル
割当問題 (G, w
e2 , l, k) をチャネル割当法 1 で解く際は与えられた c-彩色をステップ 1 で用い
ることとする．以下にこの解法を簡単に記す．チャネル割当法 3 の入力はチャネル割当問題
(G, w, l, k) と G の c-彩色，出力はチャネル割当 f である．
チャネル割当法 3
58
第4章
ステップ 1
チャネル割当問題
W = 1 ならばチャネル割当問題 (G, w, l, k) を与えられた c-彩色を用いてチャネ
ル割当法 1 で解き，得られた割当を出力し終了する．
ステップ 2
W (2) を計算し，w
e1 , w
e2 を構成する．
ステップ 3
チャネル割当問題 (G, w
e1 , l, k), (G, w
e2 , l, k) をそれぞれチャネル割当法 1 で解
く．得られた割当をそれぞれ f 1 , f 2 とする．（ただし (G, w
e2 , l, k) を解く際は，与えら
れた c-彩色を用いる．
）
ステップ 4
f 1 , f 2 を統合してチャネル割当問題 (G, w, l, k) の割当 f を構成する．すなわち
f (v) := f 1 (v) ∪ {c + (k − 1) + span(f 1 ) | c ∈ f 2 (v)},
∀v ∈ V
とする．
チャネル割当法 3 に関して以下の定理が成り立つ．
定理 26. グラフ G の c-彩色（c > 1）が与えられているとする．W = 1 のとき，チャネル割
当法 3 はチャネル割当問題 (G, w, l, k) の多項式時間 (c − 1)-近似解法である．W ≥ 2 のとき，
³ ³
チャネル割当法 3 はチャネル割当問題 (G, w, l, k) の多項式時間
1
2
1+c+
c−1
W −1
´´
-近似解
法である．
証明. W (2) = 0 の場合は明らかなので省略する．
W (2) > 0 のとき，ω(G) ≥ 2 である．W (2) > 0 かつ W = 1 のとき，補題 17 より近似率は
c−1
≤c−1
ω(G) − 1
である．
W (2) > 0 かつ W ≥ 2 の場合を考える．チャネル割当法 3 のステップ 2 で得られる f 1 の
f 1 − 1)k を満たす，ここで W
f 1 = max{w
スパン span(f 1 ) は span(f 1 ) ≤ 1 + (W
e1 | v ∈ V }
である．チャネル割当法 3 のステップ 2 で得られる f 2 のスパン span(f 2 ) は span(f 2 ) ≤
f 2 − 1) max{cl, k} を満たす，ここで W
f 2 = max{w
1 + (c − 1)l + (W
e2 | v ∈ V } である．チャ
4.3 Philadelphia 問題例
59
ネル割当問題 (G, w, l, k) の最適値を Z ∗ とし，チャネル割当法 3 の出力を f とすると
f 1 − 1)k) + (k − 1) + (1 + (c − 1)l + (W
f 2 − 1) max{cl, k})
span(f ) ≤ (1 + (W
≤ (1 + (W − W (2) − 1)k) + (k − 1) + (1 + (c − 1)l + (W (2) − 1) max{cl, k})
= (1 + W k − k) + (c − 1)l + (W (2) − 1)(max{cl, k} − k)
= (1 + W k − k) + (c − 1)l + (W (2) − 1)(max{cl, k} − max{l, k})
≤ Z ∗ + (c − 1)l + (W (2) − 1)(cl − l)
= Z ∗ + W (2)(c − 1)l
Z∗ + l − 1
(c − 1)l
2l
1
1
= Z ∗ + (c − 1)Z ∗ + (c − 1)(l − 1)
2
2
1
1
∗
= (c + 1)Z + (c − 1)k
2µ
2 ¶
1
c−1
≤
1+c+
Z∗
2
W −1
≤ Z∗ +
が成り立つ．
平面グラフは多項式時間で 4-彩色可能である．チャネル割当問題の文脈で現れる三角格子グ
ラフは自明に 3-彩色可能である．これらの事実と定理 26 から以下の系 11 が直ちに導かれる．
系 11. W ≥ 2 のとき以下が成り立つ．グラフ G が平面グラフのとき，チャネル割当法 3 は
チャネル割当問題 (G, w, l, k) の多項式時間 (2.5 +
1.5
W −1 )-近似解法である．グラフ
G の 3-彩
色が与えられているとき，チャネル割当法 3 はチャネル割当問題 (G, w, l, k) の多項式時間
(2 +
1
W −1 )-近似解法である．
4.3 Philadelphia 問題例
4.2 節では枝の重みが全て同じ問題を考えた．提案した手法は，枝の重みが全て同じとは限
らない場合にも拡張可能であるが，その場合，近似率の評価が煩雑になる．しかし，枝の重み
が具体的に数値として与えられた場合には比較的簡単に近似解法を構築可能である．本節では
現実に近い数値設定の問題群にチャネル割当法 1 を適用した場合の近似率を見積もる．
まずチャネル割当問題のベンチマーク問題としてよく用いられている Philadelphia 問題
例 [6] を紹介する．問題例の背景に関しては 1.4 節を参照されたい． 最初に三角格子上の点
v1 := (1e1 + 3e2 ), v2 := (2e1 + 3e2 ), v3 := (3e1 + 3e2 ), v4 := (4e1 + 3e2 ),
v5 := (5e1 + 3e2 ), v6 := (0e1 + 2e2 ), v7 := (1e1 + 2e2 ), v8 := (2e1 + 2e2 ),
v9 := (3e1 + 2e2 ), v10 := (4e1 + 2e2 ), v11 := (5e1 + 2e2 ), v12 := (6e1 + 2e2 ),
v13 := (0e1 + 1e2 ), v14 := (1e1 + 1e2 ), v15 := (2e1 + 1e2 ), v16 := (3e1 + 1e2 ),
v17 := (4e1 + 1e2 ), v18 := (5e1 + 1e2 ), v19 := (3e1 + 0e2 ), v20 := (4e1 + 0e2 ),
v21 := (5e1 + 0e2 )
60
第4章
チャネル割当問題
を導入し，
VP := {v1 , . . . , v21 }
とする．Philadelphia 問題例の入力グラフは三角格子点の部分集合 VP 上の単位円グラフ
(VP , d) である．次に，枝長さを
(
2, dE (u, v) ≤ 1,
l1 ({u, v}) :=
1, それ以外のとき,
(
2, dE (u, v) < 2,
l2 ({u, v}) :=
1, それ以外のとき
と定義する．最後に 5 種類の頂点重み
(w1 (v1 ), . . . , w1 (v21 )) : = (8, 25, 8, 8, 8, 15, 18, 52, 77, 28, 13, 15, 31, 15, 36, 57, 28, 8, 10, 13, 8),
(w2 (v1 ), . . . , w2 (v21 )) : = (5, 5, 5, 8, 12, 25, 30, 25, 30, 40, 40, 45, 20, 30, 25, 15, 15, 30, 20, 20, 25),
(w3 (v1 ), . . . , w3 (v21 )) : = (20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20),
(w4 (v1 ), . . . , w4 (v21 )) : = (16, 50, 16, 16, 16, 30, 36, 104, 154, 56, 26, 30, 62, 30, 72, 114, 56, 16, 20, 26, 16),
(w5 (v1 ), . . . , w5 (v21 )) : = (32, 100, 32, 32, 32, 60, 72, 208, 308, 112, 52, 60, 124, 60, 144, 228, 112, 32, 40, 52, 32)
を導入する．Philadelphia 問題例 P1 , . . . , P9 とその最適値を以下に示す；
P1 = ((VP , 3), w1 , l1 , 5),
最適値 = 426,
P2 = ((VP , 2), w1 , l1 , 5),
最適値 = 426,
P3 = ((VP , 3), w2 , l1 , 5),
最適値 = 257,
P4 = ((VP , 2), w2 , l1 , 5),
最適値 = 252,
P5 = ((VP , 3), w3 , l1 , 5),
最適値 = 239,
P6 = ((VP , 2), w3 , l1 , 5),
最適値 = 179,
P7 = ((VP , 3), w4 , l1 , 5),
最適値 = 885,
P8 = ((VP , 3), w1 , l2 , 5),
最適値 = 524,
P9 = ((VP , 3), w5 , l1 , 5),
最適値 = 1713.
図 4.1 に問題 P1, P3, P5, P7, P8, P9 の入力グラフである (VP , 3) を示す．
v1
v6
v13
v7
v14
v2
v8
v15
v3
v9
v16
v19
v4
v10
v17
v20
v5
v11
v12
v18
v21
図 4.1. (VP , (3))
本節では，Philadelphia 問題例 P1, P3, P5, P7, P9 を含む問題として，チャネル割当問
題 (Tm,n (3), w, l1 , 5) を取り上げ，チャネル割当法 1 を適用した場合の近似率を見積もる．
4.3 Philadelphia 問題例
61
チャネル割当問題 (Tm,n (3), w, l1 , 5) は NP-困難である．なぜならば，チャネル割当問題
(Tm,n (3), w, l1 , 5) は多重彩色問題 (Tm,n (3), w) を含み，多重彩色問題 (Tm,n (3), w) は NP-困
難だからである．
以下に Tm,n (3) の彩色 c∗ を示す；

1,





2,





3,




4,





5,



6,
def.
c∗ (v) =
7,





8,




9,





10,





11,



12,
v
v
v
v
v
v
v
v
v
v
v
v
∈ {(2x + 4y)e1 + (2x − 2y)e2 + (0, 0) | x, y ∈ Z},
∈ {(2x + 4y)e1 + (2x − 2y)e2 + (0, 2) | x, y ∈ Z},
∈ {(2x + 4y)e1 + (2x − 2y)e2 + (2, 0) | x, y ∈ Z},
∈ {(2x + 4y)e1 + (2x − 2y)e2 + (−1, 0) | x, y ∈ Z},
∈ {(2x + 4y)e1 + (2x − 2y)e2 + (−1, 2) | x, y ∈ Z},
∈ {(2x + 4y)e1 + (2x − 2y)e2 + (1, 0) | x, y ∈ Z},
∈ {(2x + 4y)e1 + (2x − 2y)e2 + (0, −1) | x, y ∈ Z},
∈ {(2x + 4y)e1 + (2x − 2y)e2 + (2, −1) | x, y ∈ Z},
∈ {(2x + 4y)e1 + (2x − 2y)e2 + (0, 1) | x, y ∈ Z},
∈ {(2x + 4y)e1 + (2x − 2y)e2 + (1, −1) | x, y ∈ Z},
∈ {(2x + 4y)e1 + (2x − 2y)e2 + (−1, 1) | x, y ∈ Z},
∈ {(2x + 4y)e1 + (2x − 2y)e2 + (−1, −1) | x, y ∈ Z}.
Tm,n (3) には大きさ 12 のクリークがあるので，c∗ は Tm,n (3) の最適彩色の 1 つである．図
4.2 に Tm,5 (3) を c∗ で彩色した例を示す．
1
6
10
5
8
2
9
1
3
11
4
12
6
5
2
9
1
7
3
12
6
10
5
4
7
3
8
2
1
6
10
5
11
4
8
2
9
1
3
4
12
6
3
図 4.2. Tm,5 (3) の c∗ による彩色
チャネル割当問題 (Tm,n (3), w, l1 , 5) にチャネル割当法 1 を適用し，チャネル割当法 1 のス
テップ 1 で彩色 c∗ を採用する場合，チャネル割当法 1 で得られる出力 f が (Tm,n (3), w, l1 , 5)
のチャネル割当となっていることは明らかである．このとき f のスパン span(f ) は span(f) ≤
12 + 12(W − 1) = 12W を満たす．
補題 16 はチャネル割当問題 (Tm,n (3), w, l1 , 5) に対しても成り立つので，チャネル割当問題
(Tm,n (3), w, l1 , 5) の最適値は 1 + 5(W − 1) = 5W − 4 以上である．よって以下の補題 19 が
成り立つ．
62
第4章
チャネル割当問題
補題 19. チャネル割当問題 (Tm,n (3), w, l1 , 5) の最適値を Z ∗ ，チャネル割当法 1 による出力
を f とすると
span(f ) ≤ 12W =
12
48
12 ∗ 48
(5W − 4) +
≤
Z +
5
5
5
5
が成り立つ．
本 節 で は Philadelphia 問 題 例 P1, P3, P5, P7, P9 を 含 む チ ャ ネ ル 割 当 問 題
(Tm,n (3), w, l1 , 5) に チ ャ ネ ル 割 当 法 1 を 適 用 し た 場 合 の 近 似 率 を 見 積 も っ た ．同 様 に
して他の Philadelphia 問題例を含むチャネル割当問題 (Tm,n (d), w, l, 5) を定義し近似率を見
積もることも可能である．
4.4 単位円グラフのチャネル割当の近似解法
本節では単位円グラフのチャネル割当問題の近似解法を提案する．4.2.2 節では枝の重みが
全て同じ場合の単位円グラフのチャネル割当の近似解法を考えたが，本節では枝の重みが異な
る場合を扱う．本節では ∀v ∈ V, w(v) = 1 の場合を論じる．その場合，チャネル割当問題
(G, w, l, k) の解は k に依存しない．よってチャネル割当問題をグラフと枝長さ関数の組 (G, l)
で表す．本節で提案する解法は，Marathe, Breu, Hunt, Ravi, Rosenkrants が提案した単位
円グラフの彩色問題の 3-近似解法 [43] の自然な拡張であるため，単位円グラフの彩色問題に
適用した場合には全く同じ解を出力する．
本節で提案するチャネル割当法は「順列生成」と「貪欲チャネル割当」の 2 つのフェイズか
ら成る．「順列生成」のフェイズでは，グラフの頂点に「スコア」を導入し，そのスコアを用
いて頂点の順列を生成する．「貪欲チャネル割当」のフェイズでは「順列生成」のフェイズで
生成された順列を元に貪欲 (greedy) にチャネルを割り当てる．詳細は以下の通りである．
本節ではグラフ G の頂点数を n で，枝数を m で表す．まず，頂点のスコアを導入する．グ
ラフ G = (V, E) と枝長さ関数 l : E → Z+ が与えられたとき，G の誘導部分グラフ G0 にお
ける頂点 v ∈ V (G0 ) のスコア score(v|G0 ) を
X
def.
score(v|G0 ) =
(2l(e) − 1)
e={u,v}∈E(G0 )
で定義する．誘導部分グラフ G0 において v に接続しその長さが l0 である枝の数を dl0 (v|G0 )
def.
で表す．すなわち dl0 (v|G0 ) = |{{u, v} ∈ E(G0 ) | l({u, v}) = l0 }| と定義する．このとき
score(v|G0 ) =
X
(2l − 1)dl0 (v|G0 )
(4.3)
l0 ∈Z+
が成り立つ．式 (4.3) は本節で提案する解法の近似率の見積もりで重要な役割を果たす．本節
で提案する順列生成法では「誘導部分グラフにおいてスコアが最も小さい頂点を見つけてそれ
をグラフから除去する」という操作をグラフが空になるまで繰り返す．そして頂点を除去し
た順番を順列として出力する．順列生成法を以下に正確に記す．順列生成法の入力はグラフ
G = (V, E) と枝長さ関数 l : E → Z+ ，出力は頂点順列 Π = (v1 , v2 , . . . , vn ) である．
4.4 単位円グラフのチャネル割当の近似解法
63
順列生成法
ステップ 1（初期処理） V1 := V とする．Π = () とする．
ステップ 2（繰り返し） 以下のステップ 2-1 からステップ 2-3 を i = 1, . . . , n に関して繰り
返す．
ステップ 2-1
minv∈Vi score(v|G[Vi ]) を実現する頂点（の 1 つ）を vi とする．
ステップ 2-3
vi を Π の末尾に加える．
ステップ 2-2
Vi+1 := Vi \{vi } とする．
次に，順列生成法で得られた頂点順列を基に貪欲にチャネルを割り当てる「貪欲チャネル割
当法」を提案する．貪欲チャネル割当法では順列生成で得られた順列の逆順にチャネルを貪欲
に割り当てる．貪欲に割り当てるとは，既にチャネルを割り当てられた頂点を考慮した上で実
行可能な最小のチャネルを割り当てること，を意味する．貪欲チャネル割当法の入力はグラ
フ G = (V, E) と枝長さ関数 l : E → Z+ と頂点順列 Π = (v1 , . . . , vn )，出力はチャネル割当
f : V → N である．
貪欲チャネル割当法
ステップ 1
以下のステップ 1-1，ステップ 2-1 を i = n, . . . , 1 に関して繰り返す．
ステップ 1
Vi := {vi , vi+1 , . . . , vn } とする．
ステップ 2
f (vi ) := min{x ∈ N | |x − f (v)| ≥ l({vi , v}), ∀{vi , v} ∈ E(G[Vi ])} と
する．
順列生成法と貪欲チャネル割当法を組み合わせた，チャネル割当法 4 を以下に提案する．チャ
ネル割当法 4 の入力はチャネル割当問題 (G = (V, E), l)，出力はチャネル割当 f : V → N で
ある．
チャネル割当法 4
ステップ 1
順列生成法を適用し，順列を得る．
ステップ 2
問題の入力とステップ 1 で得られた頂点順列を，貪欲チャネル割当法に適用し
チャネル割当 f を得る．
ここで提案したチャネル割当法 4 は文献 [43] で提案されている解法の拡張になっている．す
なわち枝長さが全て 1 の場合には，同じ解法になる．また，チャネル割当法 4 は頂点の座標を
必要としない上，入力として与えられるグラフが単位円グラフでなくとも正しく動く．
チャネル割当法 4 の時間計算量に関して以下の補題が成り立つ．δ(v) で頂点 v に接続する
def.
枝の集合を表し，∆ でグラフの最大次数を表す．すなわち ∆ = maxv∈V |δ(v)| と定義する．
補題 20. チャネル割当法 4 の時間計算量は O(m log ∆ + n log n) である．
証明. 順列生成法と貪欲チャネル割当法に関して別々に計算量を見積もる．
まず順列生成法にかかる時間を見積もる．グラフ G の全ての頂点 v のスコア score(v|V ) を
計算するのにかかる時間は O(m + n) である．順列生成法のステップ 2-1 でスコアを計算する
64
第4章
チャネル割当問題
際に，score(v|G[Vi ]) 6= score(v|G[Vi+1 ]) となる頂点 v が δ(vi ) 個以下であることに注目すれ
ば，順列生成法のステップ 2 でスコアの更新にかかる時間は順列生成法全体で O(m + n) で
すむことが分かる．スコアをバイナリヒープで保持すれば，最小のスコアを実現する頂点を
見つけてその頂点に隣接する頂点のスコアを更新する時間は順列生成法全体で O(m log n) と
なる．バイナリヒープの代わりに Fibonacci ヒープによってスコアを保持すれば計算時間を
O(m + n log n) にできる [22]．
次に貪欲チャネル割当法にかかる時間を見積もる．頂点 vi にチャネルを割り当てるとき，
接続する頂点 v ∈ G[Vi ] に関してチャネルの区間 [c(v) − l({v1 , v}) + 1, c(v) + l({vi , v}) − 1]
が禁止されている．頂点 vi に割り当てるチャネルを見つけるには，禁止されているチャネル
区間の和を求める必要がある．区間の数が s のとき，それぞれの区間の端を並べ替えれば和を
求めることができるので，要する時間は O(s log s) である．ここで明らかに s ≤ |δ(vi )| なの
で，1 回の割当にかかる時間は O(1 + |δ(vi )| log |δ(vi )|) = O(1 + |δ(vi )| log ∆) である．よっ
て貪欲チャネル割当の全体でかかる時間は
P
vi ∈V
O(1 + |δ(vi )| log ∆) = O(n + m log ∆) で
ある．
順列生成法と貪欲チャネル割当法の両方合わせると，全体でかかる時間は O(m log ∆ +
n log n) である．
単位円グラフ G = (V, E) と非増加実数列 (r1 , r2 , . . . , rL+1 ) に対して，「任意の {u, v} ∈ E
に対して rl0 ≥ dE (u, v) > rl0 +1 ならば l(u, v) = l0 」が l0 = 1, . . . , L に関して成り立つと
き，枝長さ関数 l は同心円状であるという．G が単位円グラフで l が同心円状のとき，チャ
ネル割当法 4 はチャネル割当問題 (G, l) の近似解法となる．以下，順列生成法において得ら
れる順列 Π = (v1 , v2 , . . . , vn ) で定義される V = {v1 , v2 , . . . , vn } によって頂点集合を表記す
る．頂点集合の部分集合 Vi (i ∈ {1, 2, . . . , n}) を Vi = {vi , vi+1 , . . . , vn } によって定義する．
maxi∈{1,...,n} {score(vi |G[Vi ])} を実現する添え字（の 1 つ）を i∗ とする．
補題 21. (G = (V, E), l) を入力とするチャネル割当問題の最適値を Z ∗ ，チャネル割当法 4
で得られる出力を f とすると span(f ) ≤ 1 + score(v|G[Vi∗ ]), ∀v ∈ Vi∗ が成り立つ．
証明. スコアの定義より
score(vi |G[Vi ]) =
X
(2l({vi , v}) − 1),
∀i ∈ {1, . . . , n}
v:{vi ,v}∈E(G[Vi ])
である．vi と v ∈ Vi が G[Vi ] において隣接ならば，区間 [f (v) − l({v, vi }) + 1, f (v) +
l({v, vi }) − 1] に含まれるチャネルは vi の割り当てに使えない．この区間に含まれるチャネル
数は 2l({vi , v}) − 1 である．よって貪欲チャネル割当法のステップ 2 で，vi に割り当てるこ
とのできないチャネル数は
1+
X
(2l({vi , v}) − 1) = 1 + score(vi |Vi ),
i ∈ {1, . . . , n}
v:{vi ,v}∈E(G[Vi ])
以下である．貪欲チャネル割当法のステップ 2 では，使える範囲で最も小さいチャネルを vi
4.4 単位円グラフのチャネル割当の近似解法
65
に割り当てるので f (vi ) ≤ 1 + score(vi |G[Vi ]), ∀i ∈ {1, . . . , n} である．i∗ の定義より
span(f ) =
max
i∈{1,...,n}
f (vi ) ≤ 1 +
max
i∈{1,...,n}
score(vi |G[Vi ]) = 1 + score(vi∗ |G[Vi∗ ])
である．順列生成法のステップ 2-1 では最もスコアが小さい頂点が削除されている．よって
score(vi∗ |G[Vi∗ ]) ≤ score(v|G[Vi∗ ]), ∀v ∈ Vi∗ であり，補題は示された．
定理 27. グラフ G = (V, E) が単位円グラフで，枝長さ関数 l : E → Z+ が同心円状のとき，
チャネル割当法 4 はチャネル割当問題 (G, l) の多項式時間 (6HL − 3)-近似解法である，ここ
で L は枝長さの最大値を表す．
証明. チャネル割当問題 (G, l) の最適値を Z ∗ ，チャネル割当法 4 の出力を f で表す．以下で
は (6HL − 3)Z ∗ ≥ span(f ) を示す．補題 21 では span(f ) ≤ 1 + score(v|G[Vi∗ ]), ∀v ∈ Vi∗
が示されている．よって
∃v ∗ ∈ Vi∗ ,
(6HL − 3)Z ∗ ≥ score(v ∗ |G[Vi∗ ]) + 1
を示せば十分である．
以下の証明では，単位円グラフとして 2 次元平面上の頂点の座標が与えられているものとす
る．Vi∗ を平面上の点集合と見なしたとき，Vi∗ の凸包の境界にある頂点の 1 つを v ∗ とする．
このような v ∗ は，例えば，Vi∗ の頂点のうち最も x 座標が小さいものを選べばよい．
最適値 Z ∗ と
∗
score(v |G[V ]) =
L
X
i∗
(2l0 − 1)dl0 (v ∗ |G[Vi∗ ])
l0 =1
を比べる．以下この証明では簡単のため dw (v ∗ |G[Vi∗ ]) を dw で表記する．
中心が v ∗ ，半径が r1 の円盤 D1 を考える．点 v ∗ を境界上に持ち Vi∗ を含む閉半平面（の
1 つ）を H ∗ とする．半円盤 D1 ∩ H ∗ を D10 で表す．頂点 v ∈ Vi∗ が v ∗ に隣接する必要十
分条件は D10 に含まれることなので，D10 は v ∗ に隣接する d1 + d2 + · · · + dL 個の頂点を含
む．半円盤 D10 を v ∗ を通る 2 直線で，3 つの扇形の領域に等分する．このとき少なくとも
(d1 + d2 + · · · + dL )/3 個の頂点を含む扇形の領域が 1 つはある．各扇形の領域に含まれる頂
点対の距離は r1 以下なので，各扇形領域内の頂点集合はクリークになっている．v ∗ は各扇形
の領域に含まれているので，その大きさが (d1 + d2 + · · · + dL )/3 + 1 以上のクリークが少な
くとも 1 つはある．クリークに割り当てられるチャネルは全て異ならなければならないことか
ら最適値 Z ∗ は
Z∗ ≥
d1 + d2 + · · · + dL
+1
3
を満たす．
次に，より小さい円盤 D2 を考える．D2 の中心は v ∗ ，半径は r2 とする．D1 の場合と同様に
半円盤 H ∗ ∩ D2 を扇形に 3 等分する．上記と同様の議論から，大きさが (d2 + · · · + dL )/3 + 1
以上のクリークが少なくとも 1 つ存在する．また，そのクリークの枝重みは 2 以上である．こ
66
第4章
チャネル割当問題
のクリークに含まれる頂点にチャネルを割り当てる場合，各頂点のチャネルは 2 以上離れてい
なければならないので最適値 Z ∗ は
µ
Z∗ ≥
¶
d2 + · · · + dL
2
+ 1 − 1 × 2 + 1 = (d2 + · · · + dL ) + 1
3
3
を満たす．以上の観察により，最適値 Z ∗ は
Z∗ ≥
l0
(dl0 + · · · + dL ) + 1,
3
∀l0 ∈ {2, . . . , L}
(4.4)
を満たすことが分かる．この式を並べて書くと
3 ∗
3
Z ≥d1 + d2 + · · · + dL + ,
1
1
3 ∗
3
Z ≥d2 + · · · + dL + ,
2
2
..
.
3
3 ∗
Z ≥dL + ,
L
L
となる．不等号の両辺を足し合わせて式変形すると
µ
¶
3 ∗ 6 ∗ 6 ∗
6 ∗
(6HL − 3)Z =
Z + Z + Z + ··· + Z
1
2
3
L
µ
¶
µ
¶
3
3
≥ d1 + · · · + dL +
+ 2 d2 + · · · + dL +
1
2
µ
¶
µ
¶
3
3
+ 2 d3 + · · · + dL +
+ · · · + 2 dL +
3
L
∗
≥
L
X
(2l0 − 1)dl0 + 1 = score(v ∗ |G[Vi∗ ]) + 1
l0 =1
が成り立つことが分かる．よって定理は示された．
単 位 円 グ ラ フ G = (V, E) と「rl0 ≥ 2rl0 +1 , l0 = 1, . . . , L」を 満 た す 非 増 加 実 数 列
(r1 , r2 , . . . , rL+1 ) に対して，「任意の {u, v} ∈ E に対して rl0 ≥ dE (u, v) > rl0 +1 ならば
l(u, v) = l0 」が l0 = 1, . . . , L に関して成り立つとき，枝長さ関数 l は強同心円状であるとい
う．例えば，枝長さ関数が強同心円状である例として Philadelphia 問題例がある．
定理 28. グラフ G = (V, E) が単位円グラフで枝長さ関数 l : E → Z+ が強同心円状のとき，
チャネル割当法 4 はチャネル割当問題 (G, l) の多項式時間 (2HL + 3)-近似解法である，ここ
で L は枝長さの最大値を表す．
証明. 以下では，定理 27 の証明と同様に ∃v ∗ ∈ Vi∗ , (2HL + 3)Z ∗ ≥ score(v ∗ |G[Vi∗ ]) + 1 を
示す．v ∗ を定理 27 の証明と同様に定義する．
中心が v ∗ で半径が r2 の円盤 D2 を考える．D2 中の頂点対の距離は 2r2 以下であり，r1 ≥
2r2 なので，D2 中の頂点対の距離は r1 以下である．よって D2 には大きさ (d2 + · · · + dL ) + 1
4.5 まとめと考察
67
以上のクリークがあるので，Z ∗ ≥ (d2 + · · · + dL ) + 1 が満たされる．半径 r3 の円盤 D3 に関
しても同様に考えると Z ∗ ≥ 2(d3 + · · · + dL ) + 1 を満たすことがわかる．一般に
Z ≥ (l0 − 1)(dl0 + · · · + dL ) + 1,
l0 ∈ {2, . . . , L},
(4.5)
が成り立つ．
定理 27 の証明の式 (4.4) と式 (4.5) を合わせると (2HL + 3) ≥ socore(v ∗ |G[Vi∗ ]) + 1 が得
られる．よって定理は示された．
定理 27 と定理 28 が示す近似率の数値例を以下の表に示す．
表 4.1. 定理 27 と定理 28 の近似率の数値例
L
6HL − 3
2HL + 3
1
3
3
2
6
5
3
8
6
4
9.5
6.66 . . .
5
..
.
10.7
..
.
7.166 . . .
..
.
4.5 まとめと考察
本章では，枝の長さが全て同じ場合（4.2 節），頂点の重みが全て 1 の場合（4.4 節）に関し
てチャネル割当問題の解法を構築しその近似率を評価した．枝の長さが全て同じ場合の解法は
（枝の長さが同じではない）Philadelphia 問題例にも適用可能なため，Philadelphia 問題例に
適用した場合の近似率も評価した（4.3 節）．具体的には，枝の長さが全て同じで入力グラフ
³
³
´
Hω(G) -近似解法を，枝の長さが全て同じで入力
³
³
´
´
グラフが単位円グラフの場合には 1 + 1 + W1−1 (3Hω(G) − 1) -近似解法を，枝の長さが
³ ³
´´
c−1
全て同じで入力グラフが一般のグラフの場合には 21 1 + c + W
-近似解法を，頂点の重
−1
がパーフェクトな場合には 1 + 1 +
1
W −1
´
みが全て 1 で枝長さが同心円状の単位円グラフの場合には (6HL − 3)-近似解法を，頂点の重
みが全て 1 で枝長さが強同心円状の単位円グラフの場合には (2HL + 3)-近似解法を提案した．
ここで c は入力として与えられた彩色に使われた色数，W は最大頂点重み，L は最大枝長さ
である．
枝の長さが全て同じ場合の解法は 3 章の近似解法と似た枠組みを用いている．頂点の重みが
全て 1 の場合の解法は Marathe, Breu, Hunt, Ravi, Rosenkrantz [43] による単位円グラフの
彩色問題の多項式時間近似解法の拡張になっている．枝長さの最大値を L をすると，既存の
解法により自明に 3L-近似解法が得られるが，チャネル割当法 4 はそれよりも良い近似率を達
成している．そしてチャネル割当問題の入力として与えられるグラフが単位円グラフでなくて
68
第4章
チャネル割当問題
も正しく動く．すなわち，入力として与えられるグラフが単位円的グラフである場合には近似
解法になる，という意味で頑健な解法となっている．
提案した解法の近似率を比較すると，チャネル割当法 1，2，3 に比べ，チャネル割当法 4 は
圧倒的に大きい．しかし，チャネル割当法 1∼3 は部分問題に分け独立に処理しているのに対
してチャネル割当法 4 は問題を分けずに処理しているという特徴がある．実際に個々の問題例
にチャネル割当法 4 を適用した場合には，定理 27, 28 の理論的近似率より精度の良い解が得
られると予想される．
69
第5章
まとめと考察
本論文では多重彩色問題の近似解法とチャネル割当問題の近似解法を提案しその近似率を論
じた．3 章および 4 章では，与えられた問題を効率的に解ける部分問題に分割し，それぞれの
解を求め，得られた解を統合して元の問題の解を構築するという手法を提案している．従来研
究にはない新しい点として，効率的に解ける部分問題を見つける際にパーフェクトグラフを用
いていることがある．パーフェクトグラフそのものは，（グラフ上の）様々な組合せ最適化問
題を効率的に解けるグラフクラスとしてよく知られているが，パーフェクトとは限らないグラ
フ上の問題の解法の構築にパーフェクトグラフが役立つ例を示したという意義は大きい．また
この手法は，多重彩色問題以外の組合せ最適化問題にも適用可能ではないかと期待できる．本
論文で用いた「問題の分割」というアプローチは，組合せ最適化問題に対する分割統治法と見
なすことができるので，大きな枠組みとしては新しいものではない．しかし本論文で提案する
具体的な分割手法は，従来からある分割手法のいずれにも属さない新しいものである．
3 章では三角（または四角）格子点上の単位円グラフ，三角（または四角）格子グラフの k
乗グラフの多重彩色問題を扱った．これは従来研究にある三角格子グラフの多重彩色問題や三
角格子グラフの 2 乗グラフの多重彩色問題を特殊な場合として含む．従来研究で扱っている問
題に対しては，3 章で提案する近似解法の近似率は従来研究の近似率と同じか，より良い．従
来研究と同等以上の近似精度を保持したまま，より広い問題を扱える解法を提案したことが，
あるいはそのような問題を設定したことが本論文の理論的意義の 1 つとして挙げられる．ま
た，直接扱ってはいないものの，単位円グラフの彩色問題の多項式時間近似解法の近似率の示
唆を与えるものになっている．
4 章では，入力として与えられるグラフ，入力として与えられる枝長さ関数に現実的な仮定
を置き，それぞれの場合に応じた近似解法を提案している．本論文で提案した近似解法はいず
れも単純なものであり，単純な解法を用いた場合にどの程度の近似率が得られるかということ
を丁寧に見積もったことが本論文の特徴である．チャネル割当問題に対してそのような見積も
りをした従来研究は見あたらない．このような状況で近似解法を提案したことも本論文の重要
性を増している．
本論文では多項式時間（近似）解法を多数提案した．厳密解法については，多重彩色問題や
最小スパンチャネル割当問題の最適解の大きさが必ず入力の大きさの多項式で抑えられるか否
70
第5章
まとめと考察
かは自明ではない．最適解の大きさが入力の大きさの多項式で抑えられない問題例があるなら
ば，本章で提案する近似解法はその問題例に対して最適解を出力しない．多重彩色問題や最小
スパンチャネル割当問題に最適解の大きさが入力の大きさの多項式で抑えられない問題例があ
るか否か調べることは今後の課題と言える．
最後に実用という見地からの本論文の意義を考察する．実際に現場で現れるチャネル割当問
題には，より複雑な制約条件が課されていることが多く，本論文で提案する近似解法を現実の
問題に直接使える場面はあまり多くはないだろう．その際に役に立つのは，多くの場合，その
問題例専用に作られた，発見的解法である． しかし，本論文の 3 章で示されている「問題分
割手法」や「効率的に解ける部分問題」は発見的解法の構築でも利用できるものであり，本論
文の実用における価値はそこにあるといえる．一般に発見的解法は構築法と改善法の組み合わ
せからなり，計算精度を上げるために改善法に時間をかけることが多い．しかし，高度に複雑
な問題の改善法においては，1 回の改善で多大な時間がかかることも多く，十分な改善ができ
ないことも多い．その場合は構築法で精度の良い解が得られていることが重要である．この点
において，近似解法で構築される解は精度が良いことが多い上に精度の保証もある．発見的解
法を構築する際に役に立つような，理論的根拠のある道具を提供したことが本論文の実用にお
ける意義であると考える．
71
謝辞
本研究を進めるにあたり大変お世話になりました松井知己先生に感謝いたします．
72
参考文献
[1] K. I. Aardal, S. P. M. van Hoesel, A. M. C. A. Koster, C. Mannino, and A. Sassano.
Models and solution techniques for frequency assignment problems. Technical Report
01-40, ZIB, December 2001.
[2] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows. Prentice Hall, 1993.
[3] R. K. Ahuja and J. B. Orlin. A fast and simple algorithm for the maximum flow
problem. Operations Research, Vol. 37, pp. 748–759, 1989.
[4] R. K. Ahuja, J. B. Orlin, and R. E. Tarjan. Improved time bounds for the maximum
flow problem. SIAM Journal on Computing, Vol. 18, pp. 939–954, 1989.
[5] S. M. Allen, S. Hurley, D. H. Smith, and S. U. Thiel. Using lower bounds in minimum
span frequency assignment. In S. Voss, editor, Meta-Heuristics: Advances and Trends
in Local Search Paradigms for Optimization, pp. 191–204. Kluwer, 1999.
[6] L. G. Anderson. A simulation study of some dynamic channel assignment algorithms
in a high capacity mobile telecommunications system. IEEE Transactions on Communications, Vol. 21, pp. 1294–1301, 1973.
[7] K. Appel and W. Haken. Every planar map is four colorable. part I: Discharging.
Illinois Journal of Mathematics, Vol. 21, pp. 429–490, 1977.
[8] K. Appel, W. Haken, and J. Koch. Every planar map is four colorable. part II:
Reducibility. Illinois Journal of Mathematics, Vol. 21, pp. 491–567, 1977.
[9] S. Arora, C. Lund, R. Motowani, M. Sudan, and M. Szegedy. Proof verification and
intractability of approximation problems. In Proceedings of the 33rd IEEE Symposium
on Foundation of Computer Science, pp. 13–22, 1992.
[10] B. S. Baker. Approximation algorithms for NP-complete problem on planar graphs.
Journal of the Association for Computing Machinery, Vol. 41, No. 1, pp. 153–180,
1994.
[11] D. Beckmann and U. Killat. A new strategy for the application of genetic algorithms
to the channel-assignment problem. IEEE Transactions on Vehicular Technology,
Vol. 48, No. 4, pp. 1261–1269, July 1999.
[12] D. Beckmann and U. Killat. A powerful hybrid algorithm for the channel-assignment
problem basing on evolutionary optimization. In Proc. ”3rd European Personal Mo-
73
bile Communications Conference”, EPMCC’99, Paris, France, 1999.
[13] H. Breu and D. G. Kirkpatrick. Unit disk graph recognition is NP-hard. Computational Geometry: Theory and Applications, Vol. 9, pp. 3–24, 1998.
[14] J. Cheriyan and S. N. Maheshwari. Analysis of preflow push algorithms for maximum
network flow. SIAM Journal on Computing, Vol. 18, pp. 1057–1086, 1989.
[15] M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas. The strong perfect
graph theorem. Annals of Mathematics, to appear.
[16] B. N. Clark, C. J. Colbourn, and D. S. Johnson. Unit disk graphs. Discrete Mathematics, Vol. 86, pp. 165–177, 1990.
[17] S. A. Cook. The complexity of theorem proving procedures. In Proceedings of the
3rd Annual ACM Symposium on the Theory of Computing, pp. 151–158, 1971.
[18] D. de Werra. Heuristics for graph coloring. Computing, Vol. Suppl. 7, pp. 191–208,
1990.
[19] R. P. Dilworth. A decomposition theorem for partially ordered sets. Annals of
Mathematics, Vol. 51, pp. 161–166, 1950.
[20] T. Feder and S. M. Shende. Online channel allocation in FDMA network with reuse
constraints. Information Processing Letters, Vol. 67, pp. 295–302, 1998.
[21] M. Fischetti, C. Lepschy, G. Minerva, G. Romanin-Jacur, and E. Toto. Frequency assignment in mobile radio systems using branch-and-cut techniques. European Journal
of Operational Research, Vol. 123, pp. 241–255, 2000.
[22] M. L. Fredman and R. E. Tarjan. Fibonacci heaps and their uses in improved network
optimization problems. Journal of the Association for Computing Machinery, Vol. 34,
pp. 596–615, 1987.
[23] A. Gamst. Some lower bounds for a class of frequency assignment problems. IEEE
Transactions on Vehicular Technology, Vol. 35, pp. 8–14, 1986.
[24] M. R. Garey and D. S. Johnson. Computers and Intractability, A Guide to the Theory
of NP-Completeness. W. H. Freeman and Company, 1979.
[25] M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph
problems. Theoretical Computer Science, Vol. 1, pp. 237–267, 1976.
[26] S. Gerke and C. McDiarmid. Graph imperfection. Journal of Combinatorial Theory,
Vol. B 83, pp. 58–78, 2001.
[27] S. Gerke and C. McDiarmid. Graph imperfection II. Journal of Combinatorial Theory, Vol. B 83, pp. 79–101, 2001.
[28] A. V. Goldberg and R. E. Tarjan. A new approach to the maximum flow problem.
Journal of the ACM, Vol. 35, pp. 921–940, 1988.
[29] M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. North-Holland,
2004.
[30] A. Gräf, M. Stumpf, and G. Weibenfels. On coloring unit disk graphs. Algorithmica,
74
参考文献
Vol. 20, pp. 277–293, 1998.
[31] M. Grötschel, L. Lovász, and A. Schrijver. The ellipsoid method and its consequences
in combinatorial optimization. Combinatorica, Vol. 1, pp. 169–197, 1981.
[32] D. S. Hochbaum. Efficient bounds for the stable set, vertex cover and set packing
problems. Discrete Applied Mathematics, Vol. 6, pp. 243–254, 1983.
[33] D. S. Hochbaum. Various notions of approximations: Good, better, best and more. In
Approximation Algorithms for NP-hard Problems. PWS Publishing Company, 1997.
[34] J. E. Hopcroft and R. E. Tarjan. Efficient planarity testing. Journal of the Association
for Computing Machinery, Vol. 21, pp. 549–568, 1974.
[35] S. Hurley, D. H. Smith, and S. U. Thiel. FASoft: A system for discrete channel
frequency assignment. Radio Science, Vol. 32, pp. 1921–1939, 1997.
[36] T. R. Jensen and B. Toft. Graph Coloring Problems. Wiley-Interscience, 1995.
[37] D. Karger, R. Motwani, and M. Sudan. Approximate graph coloring by semidefinite
programming. Journal of the Association for Computing Machinery, Vol. 45, No. 2,
pp. 246–265, 1998.
[38] R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W.
Thatcher, editors, Complexity of Computer Computations, pp. 85–103. Plenum Press,
New York, 1972.
[39] A. V. Karzanov. Determining the maximal flow in a network by the method of
preflows. Soviet Mathematics Doklady, Vol. 15, pp. 434–437, 1974.
[40] A. M. C. A. Koster. Frequency Assignment—Models and Algorithms. PhD thesis,
Maastricht University, 1999.
[41] M. Kubale, editor. Graph Colorings. American Mathematical Society, 2004.
[42] L. Lovász. Normal hypergraphs and the perfect graph conjecture. Discrete Mathematics, Vol. 2, pp. 253–267, 1972.
[43] M. V. Marathe, H. Breu, H. B. Hunt, S. S. Ravi, and D. J. Rosenkrantz. Simple
heuristics for unit disk graph. Networks, Vol. 25, pp. 59–68, 1995.
[44] S. Matsui and K. Tokoro. Improving the performance of a genetic algorithm for
minimum span frequency assignment problem with an adaptive mutation rate and
a new initialization method. In Proc. of GECCO-2001 (Genetic and Evolutionary
Computation Conference), pp. 1359–1366. Morgan Kaufmann Publishers, July 2001.
[45] T. Matsui. Approximation algorithms for maximum independent set problems and
fractional coloring problems on unit disk graphs. In Lecture Notes in Computer
Science, Vol. 1763. Springer-Verlag, 2000.
[46] C. McDiarmid. Graph imperfection and channel assignment. In J. L. Ramı́rez Alfonsı́n and B. A. Reed, editors, Perfect Graphs. Wiley, 2001.
[47] C. McDiarmid and B. Reed. Channel assignment and weighted coloring. Networks,
Vol. 36, pp. 114–117, 2000.
75
[48] Y. Miyamoto and T. Matsui. Linear time approximation algorithm for multicoloring
lattice graphs with diagonals. Journal of the Operations Research Society of Japan,
Vol. 47, pp. 123–128, 2004.
[49] Y. Miyamoto and T. Matsui. Approximation algorithm for the minimum span channel
assignment problem on perfect graphs. Technical Report METR2005-28, Department
of Mathematical Informatics, Graduate School of Information Science and Technology, The University of Tokyo, 2005.
[50] Y. Miyamoto and T. Matsui. Multicoloring unit disk graphs on triangular lattice
points. In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms,
pp. 895–896, 2005.
[51] Y. Miyamoto and T. Matsui. Perfectness and imperfectness of the kth power of lattice
graphs. In Nimrod Megiddo, Yinfeng Xu, and Binhai Zhu, editors, Proceedings of
the 1st International Conference on Algorithmic Applications in Management, LNCS
3521, pp. 233–242. Springer, 2005.
[52] 宮本裕一郎. チャンネル割当問題の解法. 修士論文, 東京大学大学院, 工学系研究科 計数
工学専攻, 1998.
[53] 宮本裕一郎, 松井知己. チャネル割当問題の解法. 情報処理学会論文誌: 数理モデル化と
応用, Vol. 40, No. SIG2(TOM1), pp. 23–32, 1999.
[54] L. Narayanan and S. M. Shende. Static frequency assignment in cellular networks.
Algorithmica, Vol. 29, pp. 396–409, 2001.
[55] T. Nieberg, J. Hurink, and W. Kern. A robust PTAS for maximum weight independent sets in unit disk graphs. In Proceedings of the 30th International Workshop on
Graph-Theoretic Concepts in Computer Science, pp. 181–188, 2004.
[56] T. Nishizeki and N. Chiba. Planar Graphs: Theory and Algorithms. Elsevier Science,
1988.
[57] N. Robertson, D. Sanders, P. Seymour, and R. Thomas. The four-colour theorem.
Journal of Combinatorial Theory, Vol. B 70, pp. 2–44, 1997.
[58] 齋藤忠夫, 立川敬二. 移動通信ハンドブック. オーム社, 2000.
[59] A. Schrijver. Combinatorial Optimization. Springer-Verlag, 2003.
[60] D. H. Smith, S. Hurley, and S. U. Thiel. Improving heuristics for the frequency
assignment problem. European Journal of Operational Research, Vol. 107, pp. 76–86,
1998.
[61] C. W. Sung and W. S. Wong. Sequential packing algorithm for channel assignment
under cochannel and adjacent channel interference constraint. IEEE Transactions on
Vehicular Technology, Vol. 46, pp. 676–685, 1997.
[62] C. Valenzuela, S. Hurley, and D. H. Smith. A permutation based genetic algorithm
for minimum span frequency assignment. Lecture Notes in Computer Science, Vol.
1498, pp. 907–916, 1998.
76
参考文献
[63] V. V. Vazirani. Approximation Algorithms. Springer-Verlag, 2001.