Document

帰着の技術
- NP困難性と問題の一般化 -
★ 目指せNP-harder!
宇野 毅明
国立情報学研究所&総合研究大学院大学
2008年7月28日組合せ最適化セミナー
帰着とは
・ 帰着とは、ある問題のクラス A が、(計算量の意味で)他の
問題のクラス B の問題を解くことで解けるよう変換すること、
あるいは変換できることを示すこと
・ 帰着できると、問題クラス B が、(計算量の意味で)問題クラ
ス A よりも難しいことがいえる
- ある問題のクラスがある種の難しいクラスに属することを証
明する (NP完全、グラフ同型性完全・・・)
- ある問題クラスが、他の問題クラスを含む一般的なもので
あることを証明する (LP、最小費用流・・・)
- 現実問題を、ツールの組合せで解く (モデル化も含む?)
帰着の目的意識
・ 問題の難しさを示すときには、なるべく簡単な問題が難しいこ
とを示すことのほうが偉い
 なるべく特殊な状況(問題Aが○○が××で▲▲が■■
で...、というときでもNP完全)で示すのがいい
(コスト、グラフクラス、次数、パラメータの固定)
・ 問題の一般的さを示すときにも、やはりいろいろな制約がつ
いているほうが偉い
 なるべく一般的な状況(問題Aに○○と××と▲▲の制約
をつけても問題Bに帰着できる)で示すのがいい
(制約、目的関数のクラス、パラメータの追加)
帰着の副産物
・ 帰着ができるということは、問題が持つ難しさ、難しい構造が
わかったということ
 その問題がなぜ解けないのかわかる。また、どう問題設
定を変えれば解けるようになるのかわかる
(グラフクラス、パラメータの固定、特殊ケース、条件の除外)
・ 帰着ができないということは、問題が難しい構造を持たない
かもしれないということ
 多項式時間のアルゴリズムが存在するかどうか、考える
価値がある
実用場面での帰着
・ 応用問題(アプリケーション)では、今持っている問題を使え
るツールで解ける問題に落とし込む作業が重要
・ 帰着は、現実問題を直接的にツールが解く問題に落とし込む
・ 帰着は、ツールが解く問題の範囲を広げる
・ 現実問題の要点抽出とツールの拡張を行い、両者のうまいミ
ーティングポイントを見つけることが応用研究の肝
応用問題
実は、応用での帰着はとても重要!
アルゴリズム
ツール
応用での、帰着でない帰着
・ 応用問題(アプリケーション)では、問題を正確に解く必要は、
必ずしも無い
 精度、速度、運用の3点
・ 問題を、不正確に、しかし精度高く、他の簡単な問題に帰着
することが重要
 簡単に解ける、ツールで解ける、速く解ける、問題が小さく
なる...
・ 問題の構造を捕らえる力がないと、おかしな帰着をすること
になる
NP完全問題
・ クラスNPの中で一番難しい問題のクラス
・ ハミルトンサイクル
 TSP、配送計画
・ サブセットサム
 ナップサック問題、分割問題
・ セットカバー
 頂点被覆
・ クリーク、安定集合
 最大密部分グラフ
本授業では、主にNP完全の持つ難しさを扱う
NP完全問題の難しさ
・ 解の一部の変更が多くの場所に影響を及ぼす
 問題を局所に分割できない
・ 満たすべき制約があり、それを、限られた資源を使って満たすよう
にしなければならない
・ それぞれの選択は、一部しか影響できない
・ 選択に排他的な条件がある (合計が○○、この組は禁止…)
- 変数を使って節を満たす (SAT)
- 集合を使って、全体を覆う (set covering)
- 隣り合わないように多く詰め込む (independent set)
良い選択の組合せを見つけることが難しい
帰着の基本テク
・ 問題の帰着の仕方は大きく分けて3つ
1) 帰着する問題のコストや制約の意味を考えて他の問題の制
約に翻訳し、問題が等価、あるいは特殊ケースで有ることを示
す
2) 帰着する問題にアタッチメントのようにコンポーネントをつけて、
あるいはコストを変えて、他の問題の特殊ケースに落とし込む
3) ガジェットという部品を作り、他の問題の解が帰着する問題の
解を表すように問題を組みあげる
本授業の目的
・ 本授業では、何が何に帰着できるのかを知るのではなく
どうやって問題を帰着するのか
を理解することを目標とする
・ だから、結果を覚えることは重要でないし、これから証明する内
容が間違っていても、そこは重要ではない
・ 演習問題を解いてみることも重要。証明を完成させることでは
なく、証明に至るまでの道が見えることが重要
問題の等価性
・ 等価な問題であることを示して難しさを示す
等価性とは
・ 問題が等価であるとは、2つの問題の間で、解の集合と、各解
の目的関数値が等しいこと
・ ただし、問題の難しさを示す意味では、ときに多少異なるものも
等価と考えてもいいだろう
- 解の数が異なるが、多対一の対応があり、対応する解の目
的関数値は等しい (無意味な変数を一個追加する、とか)
- ある種の解の変換があり、片方の問題の解から機械的にも
う片方の問題の解が作れる
- 解の対応では、目的関数値が一致せずとも、大小関係が保
たれればよい
問題クラスの等価性とは
・ 問題のクラスが他の問題のクラスを含むとは、問題のクラスA
の任意の問題が、問題のクラスBの問題になっていること
 このとき、問題クラス B のほうが難しい問題のクラス
・ 問題のクラスが等価であるとは、問題のクラス A と B が互いに
包含関係を持つこと
 このとき、両クラスの難しさは同じ
・ 問題クラスの等価性を証明
するのは、ある意味で、問題を
他の言葉で言い換えるようなもの
問題A
問題B
段取り替えの問題
・ 段取り替えスケジューリング
機械が 1 台あり、それでいくつかの品物を加工する。品物 i を
加工した後品物 j を加工するには、段取り替えに時間 tij がか
かる。最短時間で作業を終わらせるには、どのような順序で作
業をしたらよいか
tij
i
j
・ これは、品物が都市だとみなし、時間 tij が都市間の距離だと
考えると、巡回セールスマン問題になる
・ 巡回セールスマン問題
n 個の都市があり、都市 i と都市 j の距離が tij であるとする。
このとき、同じ都市を2度通らずに全ての都市を通り元の都市
に戻ってくる最短の経路を見つけよ
複数機械だと
・ 段取り替えスケジューリング
機械が k 台あり、それでいくつかの品物を加工する。品物 i を
加工した後品物 j を加工するには、段取り替えに時間 tij がか
かる。最短時間で作業を全て終わらせるには、どの機械でど
のような順序で作業をしたらよいか
・ これは、品物が顧客だとみなし、時間 tij が都市間の距離だと
考えると、配送計画問題になる
・ 配送計画問題
顧客 n 人への配送を k 台トラックで行う、最短時間で全ての配
送が終わる方法を求める問題。ただし顧客 i と顧客 j の距離
が tij であるとする
サービス時間付き配送計画
・ サービスタイム付き配送計画
配送計画で、移動時間(距離)の他に、各顧客に到着後にかかる
時間(サービスタイム)が指定されている問題(顧客 i に到着し
た後、時間 pi をかけて、その顧客で作業をしなければならない)
pi
i
pj
tij
j
+pi
i
tij+pj
j
・ 顧客 i でのサービス時間 pi を、顧客 i への時間に足し込む
 顧客を回る移動時間が、自動的に顧客 i でのサービス時間を
含むようになる
 サービス時間はあってもなくても基本的に等価
問題の間に解構造が同じ問題への(1対1)対応がある
独立集合とクリーク
独立集合:
グラフ G の頂点部分集合で、任意の頂点間に枝のないもの
クリーク:
グラフ G の頂点部分誘導グラフで、任意の頂点間に枝があるもの
(ここでは、頂点集合=クリークともよぶ)
・ グラフ G の、大きさ k のクリークは
グラフ G の補グラフの、大きさ k の独立集合
r 部と頂点彩色
r 部グラフ(r-partite):
グラフ G の頂点集合が r 個に分割でき、分割してできたグループ
の頂点間には枝がないとき、G は r 部グラフであるという
頂点彩色:
グラフ G の各頂点に r 種類の色のどれかを塗り、隣接する頂点が
同じ色にならないようできるとき、 G は r 彩色可能であるという
・ グラフ G が r 部
 G は r 彩色可能
特殊ケースとしての包含関係
・ 制約を多く持つ問題クラス A が、ある特殊な状況(パラメータを1つ
固定する、特殊な頂点を含む、など)を設定すると、他の問題クラ
ス B と一致するとき、クラス B はクラス A のスペシャルケースで
あるという
・ 巡回セールスマン問題は、トラックが1台だけの配送計画と等価
・ ビンパッキングは、ビンにつめるアイテムを顧客に対応させ、顧客
間の移動コストを0、サービスタイムをアイテムの大きさとした配送
計画問題と等価
・ 最大マッチングは最小費用流の、最小費用流は線形計画の、線形
計画は凸2次計画の、凸2次計画は非線形計画の特殊ケース
問題クラスの等価性とは
・ クラスの等価性は便利な道具だが、少々条件が強い
 そこで、問題の等価性を利用する
・ 問題のクラス A の任意の問題に対して、クラス B の問題が存
在して、2つの問題は等価
 このとき、問題のクラス B のほうが難しい
問題A
問題B
ハミルトンパスとハミルトンサイクル
ハミルトンパス(サイクル):
全ての頂点を通るシンプルなパス(サイクル)
・ グラフに1頂点加え、その頂点から全ての頂点へ枝を張る
もとのグラフのハミルトンパス
 作ったグラフのハミルトンサイクル
・ グラフのある頂点を複製して、
それぞれにひげをつけると、
作ったグラフのハミルトンパス
 もとのグラフのハミルトンサイクル
次数制限全張木
次数制限付き最小木問題:
与えられたグラフに、どの頂点の次数も k 以下であるような全張
木が存在するかどうかを判定する問題
・ k=2 とすると、最大次数が 2 の木、つまり全張パス(=ハミルト
ンパス)を求める問題
葉数制限付き最小木問題:
与えられたグラフに、葉の数が k 以下であるような全張木が存在
するかどうかを判定する問題
・ k=2 とすると、葉の枚数が 2 の木、つまり全張パス(=ハミルト
ンパス)を求める問題
ハミルトンサイクル
・ 正確に等価な問題が存在することを示さずとも、問題の等価性
のようなことはいえる
・ ハミルトンサイクル問題
グラフの全ての頂点を含む単純なサイクルは存在するか?
・ グラフの枝があるところを距離 0、枝のないところを距離1とす
ると、巡回セールスマン問題の最適解の集合は、(存在すれ
ば)ハミルトンサイクルの集合になる
(あるいは、距離の総和が 0 の解)
等価性のまとめ
・ 問題の制約と目的関数の意味を、なるべく抽象的に考えること
で、他の問題との(部分的な)等価性が見えてくる
・ コストや制約は、なるべく一般的な形で考えることで、いくつも
の種類の制約を「特殊ケース」とみなすことができる。同時に、
制約・コストの変換方法が見える
・ 解の1対1対応ができればベストだが、必要な解と、他の問題の
1部の解を、1対多で対応させられればそれで十分。
本質的に必要なものとそれを何が特徴付けているのか、を見極
める目が重要
集合被覆問題
・ 数量制約で排他条件を表現
セットカバー問題
・ 集合 E 上で定義された m 個の部分集合 S1,…,Sm ⊆ E の中
から n 個を選び、それらの和集合が E になるような選び方
ができるかどうかを答える問題
S1: 1,2,4
S2: 1,4,6
・ 難しそう???
S3: 2,3
S4: 3,6
S5: 1,5,6
・ 何個でも選べるのなら簡単
・ 任意の組合せが可能なので、ネットワーク的な構造はない
 選択・制約が伝搬することはない??
・ 変数を1つ固定した問題はセットカバーになるので、
分枝限定法はうまく動く
 うまい限定操作があるか???
他的条件の欠落
・ ある部分集合 Si を使う/使わない、の選択が複数の箇所に
影響を及ぼすか?
 Si が含む(カバーする)要素 e に対して影響するので、複
数の影響先がある
・ 要素 e に対して、 e をどの Si に入れるか自由に設定できる
 制約が作れる
・ うまくいきそうだが、排他的な条件をどうするか?
 SATを帰着しようとすると、x、¬x を同時に選んではいけ
ない、という条件が入れられない
同時に選べない条件を表すガジェットを作ればよさそう
わかるところを
・ SATを帰着するとして、まずわかるところを帰着してみよう
入力: 変数 x1,…,xn、節 C1,…,Cm、節はリテラル(xi,¬xi)の集合
目的: 各 i についてリテラル xiか¬xi のどちらかを選び、どの節
にも選んだリテラルのうちどれか1つは含まれるようにすること
・ 節 C1,…, Cmがカバーしたい要素だと思い、各リテラルを選ぶ
べき部分集合だとみなす
 つまり、 xi、¬xi は C1,…, Cm の部分集合
x1: C1
¬x1: C2
x2: C1,C2
C1
C2
¬x3: C1
(x1∨x2∨¬x3) ∧ (¬x1∨x2∨x4)
x4: C2
足りないものは
・ 節 C1,…, Cmがカバーする集合E だとみなし、各リテラルxi、¬xi
を C1,…, Cm の部分集合
・ SATの充足解 (xi、¬xi の組合せ)を持ってくると、それは C1,…,
Cm をカバーした、セットカバーになっている
・ セットカバーを持ってくると、それは充足解になっているとは限ら
ない  xi、¬xi を両方含む/含まないことがあるから
・ どうしましょうか???
C1
C2
(x1∨x2∨¬x3) ∧ (¬x1∨x2∨x4)
x1: C1
¬x1: C2
x2: C1,C2
¬x3: C1
x4: C2
大きさの条件
・ xi、¬xi のどちらか一方は必ず含むこと、とするのは簡単
 新たに Xi という要素を E に加え、xi、¬xi にのみ、Xi を加える
(xi、¬xi のどちらかは使わないと、Xiがカバーできない)
・ どちらか一方だけ、の条件はどうしましょうか
・ セットカバーには大きさの条件があるが、これはまだ未使用
 大きさを使って、xi、¬xi の排他条件をうまく表現しよう
・ 割当てが使うリテラルは必ず n 個。セット
カバーにも大きさが n という制約を加える
n個
 各 xi、¬xi のうち1つしか使えない
x1:
C 1, X 1
¬x1: C2, X1
x2:
C1,C2, X2
¬x2:
X2
帰着のまとめ
入力(SAT): 変数 x1,…,xn とそのリテラルからなる節 C1,…,Cm
出力(セットカバー): 台集合 E = { C1,…,Cm , X1,…,Xn}、部分集
合族 x1∪X1,¬x1∪X1, …,¬xn∪Xn 、大きさ n
・ 節 Cj がリテラル xj を含む  Si は ej を含む、とする
・ 入力SATの充足解は、セットカバーの解になっている
(大きさが n で、全てのCi , X1j をカバーしている)
・ 出力セットカバーの解は SATの充足解になっている
(各 xi,¬xiのどちらか1つのみを含み、全ての節を満たす)
無事、SATをセットカバーに帰着できた
格言
排他的選択は、必須選択の数で抑えよ
他の分野の格言
・ 四桂あって詰まぬことなし (将棋)
・ 一間飛びに悪手なし (囲碁)
・ 壁を作るな、相手に壁を作らせろ(オセロ)
・ そのテーブルにカモが居なけりゃお前がカモ (ポーカー)
・ かわいい子には旅をさせよ (子育て?)
・ 23  1,2,3,4,5,7 か 1,2,3,4,6,7 (カックロ)
・ 3 3 3  |3|3|3| (スリザーリンク)
・ NP完全の証明にも、格言があってもいいんじゃないかなあ
頂点被覆問題
・ 2変数の制約を3変数に
頂点被覆(vertex cover)問題
・ 与えられたグラフ G=(V,E) に対して、大きさ k の頂点集合S
で、任意の辺が S のいずれかの頂点に接続しているような
ものが存在するかどうかを答える問題
・ 難しそう???
・ セットカバーと条件がそっくり
・ しかし、カバーされるものが枝なので、1つの制約に対して、
影響できる選択が2つしかない
・ この違いは、問題の難しさに関わっているのだろうか???
まずは基本的なところだけ
・ リテラルを頂点に、節を枝に対応させれば、SATが帰着できそう
入力: 変数 x1,…,xn、節 C1,…,Cm、節はリテラル(xi,¬xi)の集合
目的: 各 i についてリテラル xiか¬xi のどちらかを選び、どの節に
も選んだリテラルのうちどれか1つは含まれるようにすること
・ 節 C1,…, Cmがカバーしたい枝だと思い、各リテラルを選ぶべき
頂点だとみなす
 リテラル xi が節 Cj に含まれるとき、
x1: C1
頂点 xi は枝 Cj に接続
¬x : C
1
・ でも、これだと 2SAT しか解けない...
なんとかならないかなあ
2
x2: C1,C2
¬x3: C1
x4: C2
戦略のイメージ
・ 節を枝で表現するのは難しい。変わりになんか、部分グラフで節
に対応するものを作ろう (ガジェットといいます)
 部分グラフに隣接する頂点のうち1つは選ばなければいけない
ようにする
選択肢
選択肢
選択肢
丸の中には何を入れたらいいでしょうか?
試行錯誤
・ 頂点を1つ入れる
 選択による変化がないので、選択の必要性がない
・ 各枝に頂点をつける
 選んだ数によって、内部で必要になる頂点の数が変わる
選択肢
選択肢
選択肢
選択肢を選んだ場合とそうでない場合で、内部の必要
数が変化するようにすると良さそうだ
影響元の増加
・ 内部に枝を張り、外部との接続枝のうち、1つだけカバーできな
いようにすればいいだろう
 内部を三角形にすると、内部は2頂点でカバーできるが、外部
への枝のうち、1つだけカバーできない
・ 3つの選択肢の
うちどれも選ばないと、
外部への枝のカバー
に青丸を3つが必要
選択肢
選択肢
選択肢
・ うまく選択肢を選ぶとどの
ガジェットも青丸を2つしか使わない
 頂点を選ぶ個数と組合わせると、割当てと同じ状況にできる
ガジェットを使った変換
・ 各選択肢頂点 vi、¬vi をリテラル xi、¬xi に対応させる
・ 各節を Cj を各ガジェット j に対応させる
・ 節 Cj がリテラル xj を含む  頂点 vi はガジェット jj の頂点に
隣接、とする
・ xi と ¬xi の排他条件を入れるため、vi、¬vi の間に枝を張る
(どちらか1つは選ばなければならない)
xi
¬xi
選択肢
・ 使える頂点の数を n + 2×ガジェット数 とする
(頂点被覆なら、全ての節を満たす)
Cj
選択肢
選択肢
数量制約を排他制約に
xi
¬xi
選択肢
・ 使える頂点の数を n + 2×ガジェット数
としたので、各ガジェット内でちょうど2個
使い、n 個の選択肢を選ぶ、つまり各 vi、¬vi
についてどちらかを選ぶことが必須となる
選択肢
選択肢
・ 大きさ n + 2×ガジェット数 の頂点被覆  充足可能解、となった
3SAT問題は頂点被覆問題に変換可能
セットカバーを帰着
・ セットカバーを帰着するのであれば、排他的な条件はいらない
・ しかし、各ガジェットに隣接する頂点の数が3だけではだめ
・ ガジェットの隣接頂点数が3でない場合、ガジェットの中身は三角形で
なく、クリークにする
 クリーク内の枝を被覆するためには、
クリークの中から1つ以外を選ぶ必要がある
選択肢
・ 三角形の場合と同じく、
隣接する選択肢が1つ選ばれている
 ガジェット内の頂点は(隣接数-1)選べばよい
選択肢
選択肢
クリーク
選択肢
・ (隣接数-1)の総和+k 個の頂点被覆がある
 大きさ k のセットカバーが存在
選択肢
選択肢
帰着のまとめ
・ 帰着する問題は SAT
入力: 変数 x1,…,xn、節 C1,…,Cm、節はリテラル(xi,¬xi)の集合
・ 以下のグラフを作成する
頂点集合: リテラル xi,¬xi の集合と、節 Ci と Ci に含まれるリテ
ラル xj の組 (Ci, xj) の集合
枝集合: 任意の Ci を共有する頂点対 (Ck, xi) と (Ci, xj) の間に
枝を張る。任意のリテラル xj と xj を含む節頂点 (Ci, xj) の間に
枝を張る
・ 作ったグラフ に G=(V,E) に大きさ
|V| - (n+m) の頂点被覆が存在
 入力した SAT に充足可能解がある
Ci
x4
Ci
x1
Ci
¬x3
格言
制約の変数数は、ガジェットを作って増減させよ
独立集合問題
・ 排他制約の効果的な利用
独立集合問題
独立集合:
グラフ G の頂点部分集合で、任意の頂点間に枝のないもの
・ 与えられたグラフが大きさ k の独立集合を持つかどうかを判定
する問題が、k-独立集合問題
・ 排他制約の親分のような問題
(排他制約のみからなる問題)
・ どうやってNP困難性を
証明しようか?
・ SATを帰着してみよう
排他条件を使った選択肢
・ SATの、「リテラル xiか¬xi のどちらしか選べない」という条件は
比較的簡単に実現できる
 xi に対応する頂点と ¬xi に対応する頂点を作り、両者の間
に枝を張る
+ これらの頂点から n 個選ばせるようにすると、 xi と ¬xi のど
ちらかを必ず選ぶことになる
・ 各節が充足されるという
条件はどうしようか
xi
¬xi
・ 各節に頂点を対応させて、その節のリテラルどれかが選ばれて
いれば、節の頂点が選べる、としたいが、排他条件でこういう
セッティングをどうやって作ろうか?
節の表現
・ 単純に各節に頂点を対応させて、その節に含まれるリテラルと
辺でつなげてみる
x4
Ci
・ 節が充足されている(リテラルを
どれか選んでいる)と、Ci は選べない
x1
¬x3
・ 節が充足されていない(リテラルを
どれも選んでいない)と、Ci は選んでも選ばなくてもいい
・ やりたいことと逆だ
 条件が逆ならば、個数の制限をつけるだけで帰着ができる
選択肢の逆転
・ 選択肢を逆にする、逆転の発想をしてみよう
 割当てとして選択するリテラルの否定を、独立集合の頂点と
して選ぶ。つまり、各リテラルの否定を選ぶ
・ 節が充足されている(リテラルの
どれか選ばれていない)と、Ci は選べない
・ 節が充足されていない(リテラルを
全て選んでいる)と、Ci は選べない
x4
Ci
x1
¬x3
・ 今度は、どちらの状況でも節が選べなくなった
・ もう一工夫して、リテラルどれかが選ばれてなければ節が選べ
る、としたい
節の変形
・ リテラルが1つ選ばれていないときに節の頂点を選べるようにし
たいのだから、各リテラルに対して頂点を用意しよう
・ 節に対応する頂点が複数になるので、それらのうちから1つだ
けしか選べないようにしよう
 これは、独立集合の状況では簡単
x4
Ci
節に対応する頂点たちをクリークにして
Ci
x1
しまえばよい
Ci
¬x3
・ リテラルどれかが選ばれていなければ、節を選ぶことができる
帰着のまとめ
・ 帰着する問題は SAT
入力: 変数 x1,…,xn、節 C1,…,Cm、節はリテラル(xi,¬xi)の集合
・ 以下のグラフを作成する
頂点集合: リテラル xi,¬xi の集合と、節 Ci と Ci に含まれるリテ
ラル xj の組 (Ci, xj) の集合
枝集合: 任意の Ci を共有する頂点対 (Ck, xi) と (Ci, xj) の間に
枝を張る。任意のリテラル xj と xj を含む節頂点 (Ci, xj) の間に
枝を張る
・ 作ったグラフに大きさ n+m の独立
集合がある  入力した SAT に
充足可能解がある
(頂点被覆で作ったグラフと同じ。。。)
Ci
x4
Ci
x1
Ci
¬x3
他の帰着
・ 各節からリテラルを1つだけ選ぶ、という考え方もある
 相補的なリテラルは選べないよう、枝を張っておく
入力: 変数 x1,…,xn、節 C1,…,Cm、節はリテラル(xi,¬xi)の集合
・ 以下のグラフを作成する
頂点集合: 節 Ci と Ci に含まれるリテラル xj の組 (Ci, xj) の集合
枝集合: x = ¬y 、あるいは、C = C' が成り立つ (C, x) と (C', y)
の間に枝を張る
¬x1
x4
・ 作ったグラフに大きさ m の独立
集合がある  入力した SAT に
充足可能解がある
x1
¬x3
¬x1
x3
格言
都合の良い状況に選択肢を与えて排他条件をつけよ
セットカバーの帰着
・ リテラル x と ¬x を同時に使わない、というところは、あまり帰着
の上では必須ではない感じがする
 セットカバーを帰着してみよう
入力: 部分集合族 S1,…,Sm ⊆ E={1,…,n}
・ 以下のグラフを作成する
頂点集合: 部分集合 Si の要素 e に対して頂点 (Si,e) を用意
枝集合: S = S' が成り立つ (S, e) と (S', e') の間に枝を張る
要素
・ 作ったグラフに大きさ m+n-k の
独立集合がある
 入力したセットカバーに
大きさ k の解がある
S1
S2
S3
サブセットサム問題
・ 数を桁に分解して、多数の制約を表現
・ ガジェットで数の差異を吸収
サブセットサム問題
・ 与えられた n 個の数 a1,…,an の中からいくつかを選び、合計
がちょうど b にできるかどうかを答える問題
・ 難しそう???
1, 4, 13, 15, 2, 8, b=32
・ 「ちょうど b 」ではなく、「b 以上/以下」なら簡単
・ 任意の組合せが可能なので、ネットワーク的な構造はない
 選択・制約が伝搬することはない??
・ 変数を1つ固定した問題はサブセットサムになるので、
分枝限定法はうまく動く
 うまい限定操作があるか???
難しさはどこにある?
・ 制約は1つしかない!
 複数の制約がある難しさはなさそう?
 しかし、数をぴたりと調整する難しさがある
・ 合計が b 以上/ b 以下なら簡単
・ 1 とか 2 とか、小さい数ばかりなら簡単
(DPで解ける。整数のみなら、ですが。調整しやすいという意
味でも簡単そう)
 大きな数を使っている問題が難しいのだろう
・ SATなどの問題との違いは、数の調整と、複数の制約がある、
というところだろう
帰着の鍵
- 制約を複数作れるか?
- ある数を解に入れる/入れない、の選択が、複数の場所に影
響を及ぼすようにできるか?
- それぞれの場所は、特定の数からしか影響を受けないようにで
きるか?
が、帰着の鍵です
・ 1つの制約である合計の b を、複数の制約に分解できないか?
・ 10進数足し算を計算するときのように、いくつもの桁にわければ
いいんじゃない?
桁の分解を使う
・ 各数を「桁ごと」に分解して考えると、ある数を解に含める、と
いう動作は、各桁の解に影響を及ぼす
 各選択が、複数の制約に影響をおよぼせるようになった
・ 問題を作る際、数の各桁は自由に設定できるので、各選択
(数を含めること)がどこに影響するかをデザインできる
(各ai の、影響をおよぼしたい桁だけ非ゼロにすればよい)
・ 足し算の結果桁あふれが起きると困るので、桁は大きめ、例
えば 100n2 進数のようにすればいいでしょう
ai = 1 0 1 0 0 0 2 0 0 0 1
aj = 0 1 1 0 0 2 1 0 0 0 0
b=11122210111
3-SAT の帰着
・ 先の難しさを使って、3-SATを帰着しよう
入力: 変数 x1,…,xn、節 C1,…,Cm、節はリテラル(xi,¬xi)の集合
・ まず、十分大きなM進数を考え、十分大きな桁数を考える。それ
ぞれの桁がそれぞれの制約に対応
・ 各数を選ぶことは、リテラル x か ¬x を選ぶことに対応
・ 各変数に対して桁を1つ用意。 x、¬x に対応する数だけ、その
桁を 1 にする。この桁の合計を 1 にして、片方しか選べない制
約を表現
x、¬x 片方制約
ai =
・・・・・・
00000100000
xi、¬xi に対応する桁
リテラルの表現
・ 同様に、各節に対して桁を1つ用意。 節に含まれるリテラルに対
応する数だけ、その桁を 1 にする
 選んだ数の合計の、その桁の数が非ゼロならば、その節は
充足されている
・ しかし、充足できた  合計がちょうどある数になる、
とは設定できない
数の違いを吸収するガジェットを作ろう!
節充足制約
ai = ・・・
001101001000 ・・・・・・
xiが含まれる節
合計の差異の吸収
・ 節に対応する桁の合計は、
「充足されている」  「その桁の合計が 1 か 2 か 3」
・ この違いを吸収するガジェットのために桁を一つ用意
-節の桁と調整の桁が 1 であるもの (fi) と
- 節の桁が 0 で調整の桁が 1 であるもの (gi)
という数のガジェットを複数個準備し、
b の調整の桁を 2 、節の桁を 3 にする
差異吸収用
節充足制約
fi = 00100000000
gi = 00100000000
00100000000
00000000000
・・・・
・・・・
b=
33333333333
・・・・
22222222222
ガジェットの働き
・ b の差異吸収の桁が2 なので、fi 、gi をちょうど2個組合わせて選ぶ
必要がある
・ i 番目のリテラルの桁の合計が 1 か 2 か 3 のどれかである
 fi 、gi をうまく選び、その桁の合計を 3 にできる
差異吸収用
節充足制約
fi = 00100000000
gi = 00100000000
00100000000
00000000000
・・・・
・・・・
b=
33333333333
・・・・
22222222222
差異吸収ガジェットにより、合計が 1,2,3 のどれかであることと
合計がちょうど何かになることを結びつけられた
格言
差異吸収用
節充足制約
fi = 00100000000
gi = 00100000000
00100000000
00000000000
・・・・
・・・・
b = 22222222222
33333333333
・・・・
数は桁に分けて制約(スイッチ)にせよ
合計の差異は人工変数で吸収せよ
サブセットサムの亜種
・ 少々の問題変更は、難しさに影響するか?
サブセットサム亜種(1)
・ 与えられた n 個の数 a1,…,an の中からちょうどn/2個を選び、
合計がちょうど b にできるかどうかを答える問題
・ 難しそう???
1, 4, 13, 15, 2, 8, b=32
・ ちょうどn/2個を選ばなければならないので、先の帰着は使え
ない
・ この違いは、果たして問題の本質的な難しさに影響するのだろ
うか?
亜種(1)の帰着
・ サブセットサムを、この亜種に帰着できるか調べよう
・ 選ぶ個数が自由な問題を、選ぶ個数固定の問題に帰着したい
 簡単なアイディアは、選択しても意味のないダミー選択肢を準
備すること。規定された個数に足りない分だけ、ダミーを選ぶ
・ 与えられたサブセットサム a1,…,an, b に、ダミー a'1=0, …,
a'n=0 を選択肢として加える
・ ちょうど n 個選んでください、と言われたら、 a1,…,an の中から
好きなだけ選び、不足分だけダミーを加える
 サブセットサムの解に対して、ちょうど同じ合計を持つ、亜種
の解が対応 (逆向きの対応もある)
サブセットサムは亜種(1)に帰着できる
逆向きの帰着
・ 次は亜種をサブセットサムに帰着してみよう
・ 選ぶ個数固定の問題を選ぶ個数が自由な問題に帰着したい
 今度は、どう選んでもいいが、解になるように選ぶと自動的に
半分ずつになるような仕掛けを作りたい
・ 今度は、SATを帰着するときに使った桁を分けるアイディアが
使えそうだ
(b に合わせるための桁と、個数を半分ちょうどに合わせる桁)
ai =
個数調整桁 + ai
大きな数を足し込む
・ 個数調整の桁ように、大きな数を準備しよう
十分大きな M >Σai を用意
・ a'i = M + ai 、b' =
M×n/2 + b に設定
・ 新たに作った問題の解 A' ⊆ {a'1, …, a'n} の和がちょうど b'
 対応する解 A ⊆ {a1, …, an} の大きさが n/2 で和が b
 桁あふれが起きないから
亜種(1)はサブセットサムに帰着できる
サブセットサム亜種(2)
・ 与えられた n 個の数 a1,…,an の中からいくつかを選び、合計
がちょうど (Σai) / 2 にできるかどうかを答える問題
・ 難しそう???
2, 4, 13, 15, 1, 9, b=22
・ 全く同じ大きさに分けなければいけないので、先の帰着は使え
ない
・ この違いは、果たして問題の本質的な難しさに影響するのだろ
うか?
亜種(2)の帰着
・ サブセットサムを、この亜種に帰着できるか調べよう
・ 目標値が自由な問題を、目標が決まってる問題に帰着したい
 前回と同じ発想でいけば、ダミー選択肢を準備して目標を変化さ
せればいいだろう
・ 与えられたサブセットサム a1,…,an, b に対して、
ダミー an+1= (Σai) +b と an+2 = (Σai)×2 -b を加える
 (Σai) /2 は (Σai)×2 になる
・ 同じ和になるように分けるには、an+1 と an+2 は異なるグループに入
る必要がある。そのため、残りを b と Σai - b に分けることになる
サブセットサムは亜種(2)に帰着できる
格言
固定制約にはダミーで対応せよ
サブセットサムの応用
・ サブセットサムに帰着する証明
サブセットサムの利用
・ サブセットサムの難しさは、数をぴったりと合わせるところ
 数合わせ的な要因を持っていたり、合計がある程度以上で最小、
というような要因があると、帰着できる
・ こういった要因を持つ問題をいくつか、調べてみよう
ナップサック問題
ナップサック問題:
重さ wi、価値 ci を持つ荷物 1,…,n を組合せ、重さの合計が b を超
えないようなものの中で価値合計最大のものを見つける
・ ちょうどを見つける、という状況ではないが、合計の制限と、合計
を最大にしたいものがある
・ この2つを組合わせればよい
サブセットサム {a1,…,an}, b に対し、価値と重さを ci = wi = aiとする
価値合計が b になる実行可能解があれば、サブセットサムの解
がある
サブセットサムはナップサックに帰着できる
1次元ラベリング問題
1次元ラベリング問題:
長さ l の直線上に点が、位置 {p1,…,pn} にある。点 i に隣接する
ように、長さ wi を持つ線分(ラベル)を pi を含むよう、重ならず
におく。目的関数は、置いたラベルの価値 c1 の合計が b 以上
にできるような置き方を見つける問題
・ サブセットサムが簡単に帰着できそうだが、ラベルがその点を
含むようにしなければならないところがやっかい
位置ずれの吸収
・ 基本戦略は、長さ wi を組合わせるサブセットサムを作ること
・ まず、他の選択肢の選択によらず、各選択肢が選べるようにし
たい。そのため、長さ wi を Z 増やし、他の選択がどのようにな
っても pi におけるようにする
・ wi を使わないときと使ったときの差が大きくなるので、 wi を使
わなかったときに対応する選択(長さ Z )を用意する。両者は
ほぼ同じ位置に置く
1次元ラベリング問題
・ この選択ガジェットを、長さ Z ごとに配置
全体の長さ l は、b+nZ に設定
・ 長さ合計が b+nZ になるラベルの選び方がある
 合計が b になる ai 組合せがある
サブセットサムは1次元ラベリング問題に帰着できる
格言
「ちょうど」は「これ以下で最大」に
同型性と埋め込み
・ 埋め込む問題を排他制約に
同型性判定と埋め込み判定
・ 2つのグラフが同型であるかを判定するのが同型性判定問題
(隣接関係を保持した頂点の1対1対応があるかどうか)
・ 2つのグラフの片方が片方の部分グラフになっているかどうか
判定するのが埋め込み判定問題
・ 埋め込み判定はNP完全だが、
グラフ同型性はNP完全か多項式か
わかっていない
・ 片方がもう片方の部分グラフに、もう片方も片方の部分グラフに
なっていたら同型なので、少なくとも同型性のほうが易しい
両者の難しさを帰着で調べよう
埋め込み判定のNP完全性
・ グラフ埋め込み判定問題は、例え埋め込むグラフが木であって
もNP完全
・ 異なる頂点を同じ頂点に埋め込んではいけない、という部分が
排他的なので、独立集合問題を帰着しよう
・ 戦略は、
- 埋め込む部分グラフの先っぽを、グラフの頂点に必ず対応さ
せなければならないようにグラフを変形、
- 隣接する頂点に、同時に先っぽを埋め込むことはできないよう
にする
というようにする
戦略のイメージ
・ 独立集合を求めるグラフを変形し、埋め込むグラフを別に作成。
独立集合のグラフの頂点に対応する部分グラフに、埋め込む
グラフの先っぽの部分グラフが埋め込まれる
埋め込むグラフ
独立集合を求めるグラフを
変形したもの
頂点の変換
・ 元のグラフの頂点を何に変形するか
・ 何も変形しないと、先っぽはどこにでも対応できる
・ 次数を大きくすれば良さそう。次数の大きな頂点は、次数の大き
な頂点にしか対応させられない
 埋め込むグラフの先っぽと、対象グラフの頂点を、次数の大きな
スターにしよう (頂点がジェット)
・ 他に、根っこに
対応する頂点を、
対象グラフに付け加える
頂点の排他性
・ このままだと、どの先っぽをどの頂点ガジェットに割当てても埋
め込める
・ 隣接する頂点ガジェットには同時に先っぽを割当てられないよう、
スターの葉の1つを隣接する頂点が共有するようにする
・ 埋め込みグラフの先っぽのスターも、頂点がジェットも、葉っぱ
(+共有されている葉っぱ)にちょうど n 枚隣接するようにする
・ 1つの先っぽを頂点
ガジェットに埋め込むと、
隣接する頂点を全部使う
 隣接する頂点ガジェット
両方に先っぽは埋め込めない
埋め込むグラフで個数を指定
・ ここで、埋め込むグラフの先っぽの数を k とする
・ もし先っぽ k 個全部を埋め込められたら、その埋め込んだ頂点
ガジェットの集合は、元のグラフに大きさ k の独立集合になる
・ 元のグラフに大きさ k の独立集合があるなら、その頂点がジェ
ットに先っぽを埋め込むと、埋め込むグラフを変形したグラフに
埋め込むことができる
・ 独立集合問題をグラフ
埋め込み判定問題に
帰着できた
格言
埋め込みは排他制約である
実はもっと簡単な帰着が...
・ 実はもっと簡単な帰着があります
・ ハミルトンパス、ハミルトンサイクルが簡単に帰着できる
 長さ n-1 のパス、長さ n のサイクルが埋め込めるかどうか判
定すれば解ける
・ でも、ここでは帰着の技術を見たかったので。。。
派生する帰着
・ 2つのグラフが与えられたとき、2つのグラフに含まれるもっとも
大きなグラフを求めよ
 グラフ A がもう片方のグラフ B に埋め込めるとき、解のグラフ
の大きさは A の大きさと等しくなるので、グラフ埋め込み判定
問題が帰着できる
同型性の帰着
グラフクラスと同型性
・ グラフクラスを制限すると、グラフ同型性判定は容易になる
- 木、サイクル、インターバルグラフ・・・
・ 他のグラフクラスではどうか?
・ 一般のグラフ同型性判定問題を、そのクラスのグラフの同型性
判定問題に帰着して、問題のクラスを調べる
2部グラフ
・ グラフが2つの頂点集合に分割でき、両者がともに独立集合と
なっているとき、そのグラフを2部グラフという
・ グラフ同型性判定を2部グラフ
の同型性判定に帰着する
・ グラフの各枝の中点に頂点を追加する
・ 変形したグラフは2部グラフになっている
・ 2つのグラフが同型  変形したグラフも同型
スプリットグラフ
・ グラフが2つの頂点集合に分割でき、片方がクリーク、もう片
方が独立集合となっているとき、そのグラフをスプリットグラフ
という
・ グラフ同型性判定をスプリットグラフの
同型性判定に帰着する
・ グラフの各枝の中点に頂点を
追加し、追加した頂点間全てに
枝を張る
・ 変形したグラフはスプリットグラフになっている
・ 2つのグラフが同型  変形したグラフも同型
グラフクラスと同型性
・ グラフクラスの包含関係を表した図で、同型性が多項式である
ものと、一般のグラフの同型性と本質的に変わらないものを
図示して見る
perfect
chordal
unit disk
r-partite
strongly
chordal
circular arc
interval
planar
bipartite
split
tree
co-graph
proper interval
partial k-tree
series-parallel
permutation
unit length
circular arc
planar
bipartite
threshold
ハミルトンサイクル
・ スイッチの工夫
ハミルトンサイクル
ハミルトンサイクル問題:
与えられたグラフ G=(V,E) が、全ての頂点を含むシンプルサイク
ルを部分グラフとして含むかどうか判定する問題
・ 全ての頂点が次数2、という制約だけなら簡単そう
 サイクルに分解できるかどうか?
・ 連結性の条件が手ごわそうだ
帰着の難しさ
・ SATなどの問題を帰着しようとすると、選ぶ/選ばない、という
選択肢を作る必要がある
 「サイクルが通った 選んだ」、という対応をつけたいが、ハミ
ルトンサイクルでは全ての頂点を通らなければならない
・ 通る枝の選択肢、部分グラフの通り方を局所的に指定できると
良い
・ とりあえずできることは必ず使う枝を指定すること
(枝の間に頂点を置く)
スイッチガジェット
・ 使用必須枝、を使うと、部分的にスイッチのようになるガジェ
ットが作れる
・ 図の部分グラフ、縦線3本は必ず
通らなければならない
・ すると、この部分グラフの
通り方は、2通りしかない
頂点被覆を帰着
・ スイッチがジェットを使うと、2つのうちは
どちらかを選ぶこと、という条件が設定できる
 頂点被覆がフィットしそうだ
・ 帰着する頂点被覆のグラフに対して、頂点に対サブグラフを、
枝にガジェットを対応させ、隣接関係に従ってつなげる
 被覆として選ぶ頂点だけを通るようにしたい
・ しかし、ハミルトンサイクルは
全ての部分グラフを通過しな
ければならない。。。
空ガジェット!?
・ 頂点ガジェットが頂点を持つと、そこを通らなければならない
 ならば、頂点ガジェットは頂点を持たないようにしよう
・ スイッチガジェットの枝を直接つないで、ループのようなもの
を作る
 スイッチガジェット以外の枝は必要ない
・ 各頂点に接続する枝のガジェットを
全てをこのようなループでつなぐと、
頂点被覆を帰着するための
グラフができる?
頂点ガジェットの衝突
・ 現在、頂点ガジェットは、通り抜けようとすると全ての隣接す
るスイッチガジェットを通り抜けなければいけない
 元のグラフで隣接する頂点を同時に選べない!
・ 好きな個数だけ、通るスイッチガジェットを選べるようにできれ
ばよい
 スイッチガジェット間に
ショートカットを作ろう
・ ショートカットを通って、好きな
スイッチガジェットだけを
選んで通れるようになった
頂点の個数制限
・ スイッチガジェットと頂点ガジェットによって、「選んだ頂点に接
続する枝をカバーする」という状況を、パスが通過する/しない
という選択で表現できた
・ 次は、通れる頂点ガジェットの個数を制限しよう
・ k 回、頂点ガジェットを選択できて、各選択では、任意の頂点が
ジェットを一回選択できる、という状況を実現したい
・ (必ず通らなければいけない)
入り口を作って、そこから各頂点ガジェット
に分岐し、入り口2(仮想的な出口)
に収束させる (実際は、入り口と
ガジェットは複数本の枝で接続)
・・・
k 個の入り口/出口を連結
・ (必ず通らなければいけない)入り口を作って、そこから各頂点
ガジェットに分岐し、入り口2(仮想的な出口)に収束させる
(実際は、入り口とガジェットは複数本の枝で接続)
・ 頂点被覆で指定された個数 k だけ入り口と出口を作り、各ガジ
ェットと各入り口・出口をつなぐ
 k 個の頂点ガジェットしか通れなくなる
・ あとは、入り口・出口の端っこを
クリークにしてしまう
 k 個の頂点ガジェットで全ての
スイッチがカバーできれば、(k 個の
頂点ガジェットを通る)ハミルトンサイクルが存在
・・・
最後の落とし穴
・ 今、頂点ガジェットはいくつもの入り口/出口につながっている
ので、入り口から入り、他の入り口へ出て行くようなルートがあ
り得る
 このようなパスでも、入り口から他の入り口に行く間、通過でき
る頂点ガジェットは1つだけ(入り口ガジェットには必ず使う枝
がついていて、強制的に脱出させられ、折り返して他の頂点ガ
ジェットに行けないことに注意)
 このようなパスも、入り口/出口を
2 個消費するので、なんにしても頂点
ガジェットを通るパスは k 個以上作れない
・ よって、破綻はしていない
・・・
格言
頂点被覆問題をハミルトンサイクル問題に帰着できる
ハミルトン**はスイッチで制約、空ガジェットで選択肢を表現
次数を3にする
・ ハミルトンサイクル問題を言い換えると、グラフ G の全ての頂
点を含み、全ての頂点の次数が2であるような連結な部分グラ
フはあるか、となる
・ この次数「2」を変えるとどうなるか?
・ グラフ G の全ての頂点を含み、
全ての頂点の次数が3であるような
連結な部分グラフはあるか
ハミルトンサイクルの帰着
・ ハミルトンサイクルを帰着するのが自然だろう
・ 次数「2」のグラフを見つける問題を、次数「3」のグラフを見つけ
る問題に、どうやって変換しようか
・ ハミルトンサイクルを見つけるグラフの各点に余計なものをつけ
て、そこで次数「1」を消費するようにしよう。その際、連結性を
一切変えないようにしよう
ガジェット
・ 右の部分グラフ(ガジェット)は、
各頂点の次数が3なので、これを
グラフの各頂点にひっつける
次数を使用して減じる
・ ハミルトンサイクルを求めるグラフの各頂点にガジェットを添付
・ 次数3の連結グラフを作るには、ガジェットの各頂点に接続する
枝は全て選択する必要がある
・ 次数3の連結グラフを求めるには、もとのグラフの各頂点が、元
のグラフの枝2つに接続する必要があり、そしてその枝が連結
になる必要がある
 つまりハミルトンサイクルを
見つけなければいけない
グラフ
平面的な問題
・ 平面的なNP完全問題を帰着
平面性の不自由さ
・ 今まで見てきた帰着は、枝と頂点、要素と部分集合などを自在
に組合せることができた
・ しかし、問題のグラフのクラスが限定されると、このようにうまく
はいかなくなる。
 木、コーダルグラフ、平面グラフ、k-tree…
・ 木は木で、木でも難しい問題には木という制約が気にならない
ような困難性がある。
・ そういう意味では、平面グラフやコーダルグラフあたりがちょうど
難しい
頂点被覆という道具
・ 平面的なグラフを入力とする問題のNP困難性を示すには、や
はり平面的なグラフを入力とする問題を帰着するのが楽
・ 帰着する問題としては、例えば、頂点被覆がある
 頂点被覆は、たとえ入力するグラフが平面的であり、かつグ
ラフの頂点の次数が全て3でもNP完全
・ いくつかの平面グラフ上の問題に、頂点被覆を帰着して見よう
独立集合へ帰着
・ 平面次数3頂点被覆
与えられた平面的で全ての頂点の次数が 3 であるグラフが、大き
さ k の頂点被覆をもつかどうか答える問題
・ 独立集合問題に帰着する
 独立集合は小さいほど作るのが楽、頂点被覆は大きいものほ
ど作るのが楽なので、独立集合として選ばない頂点が頂点被
覆の頂点になるようにする
・ 枝の両方の端点が独立集合に入っているとき、枝にペナルティ
ーをかければいいので、枝の中点に頂点を置いて、独立集合
に枝の頂点が含められないようにする
枝の中間に頂点を
・ 枝の中間に頂点を1つ入れる
・ 両方の端点が独立集合に入っていないときのみ、真ん中の頂
点を独立集合に入れられる
 これではだめ
・ 枝の中間に頂点を2つ入れる
・ 両方の端点のうち片方が独立集合に入っていないと、真ん中の
頂点のうち1つを独立集合に入れられる
帰着のまとめ
・ 頂点被覆のグラフに対して、各枝の中間に頂点を2つ挿入
(これにより平面性がなくなることはない)
・ 作ったグラフの独立集合は、枝に挿入した頂点のどちらかを取
れる。最大 m 個。これに追加して、もともとの頂点を n-k 個選
べれば、その頂点集合の補集合が頂点被覆になる
・ 逆に頂点被覆の補集合に枝の中間の頂点を適切に加えると、
大きさ m+n-k の独立集合が得られる
ユニットディスクグラフの変形
ユニットディスクグラフ
各頂点が平面上に置かれた半径1の円盤に対応し、頂点間に枝
がある対応する円盤が重なりを持つ、となっているグラフ
(平面上の円盤のインターセクショングラフ)
・ ユニットディスクグラフでの頂点被覆問題がNP完全であることを、
平面次数3頂点被覆問題を帰着して示す
枝の引き伸ばし
・ 平面グラフは必ずユニットディスクグラフになるわけではない
 入力グラフの変形が必要
・ 幸い、頂点被覆は枝の間に偶数個の頂点を入れても、問題の
構造は変化しない (2個のうち1つは選択する必要があり、1
つだけですめば被覆になっている)
 平面グラフの枝を引き伸ばして、ユニットディスクでエミュレート
しよう
グラフの変換
① 平面グラフを平面に埋め込む
② 各頂点を円盤で置き換える
③ 各枝を、くさりのように連ねた円盤で置き換える
変換したグラフに大きさ (追加した円盤数/2)+k の頂点被覆
がある  もとのグラフに大きさ k の頂点被覆がある
「次数3」の便利さ
・ 頂点被覆の問題グラフの「次数が3」という条件は、平面グラフ
では非常に便利
 グリッドグラフのように縦横にしか枝が伸びていないグラフや
ユニットディスクグラフのような、図形の重なり方のモデルに帰
着しようとするとき、次数が大きいと破綻してしまう
・ もうひとつ、例として以下問題の帰着を考えて見よう
問題: 平面上の点を、大きさが一定の + 型のピース k 個で覆う
ことができるか? (仮に十字カバーとよぶ)
頂点被覆の帰着
・ 十字カバー問題に、平面次数3頂点被覆問題を帰着しよう
 両方とも被覆の問題なので比較的楽そう
・ 十字を頂点に、点を枝に対応させよう
① グラフを平面に埋め込む
③ 枝を、縦横に少しずつ(長さ l 程度)ずらした点列で置き換える
ただし、点列の始まりと終わりは、端点の中心に十字を置いたと
きの、十字の端がくる場所にする。また、点列は奇数個にする
④ 十字の縦横の長さを l に設定する
頂点被覆の帰着
・ 枝がジェットの片方の端点がカバーされている
 枝内の頂点は (頂点数-1/2) 個の十字でカバーできる
・ 枝ガジェットのどちらの端点もカバーされていない
 枝内の頂点のカバーに (頂点数+1/2) 個の十字が必要
・ (枝がジェットの頂点数-枝数)/2 + k 個の十字架バーがあ
る  もとのグラフに大きさ k の頂点被覆がある
格言
平面的な帰着では、枝をグラフ(ガジェット)で置き換えよ
列挙の帰着
・ ほぼ等価な変換が必要
列挙と数え上げ
・ 列挙(enumeration, generation)は、与えられた問題の解を全て出
力する問題
・ 数え上げ(counting)は、与えられた問題の解の数を計算する問
題
・ ちょっと違う。しかし、出力の大きさは指数的に違う
・ 列挙や数え上げの問題の間にも帰着の関係がある
・ NP完全に相当する、#P完全という問題のクラスがある
・ #P完全は、本質的に、数え上げが多項式時間で行えないと思
われているクラス
列挙での帰着の難しさ
・ 最適化・充足可能性の問題に比べると、一般的に列挙や数え上
げのほうが帰着は難しい
・ 理由は、基本的に問題の等価性を言う必要があるから
 列挙では、最適解の存在が確認できるだけではだめで、全ての
解を見つけなければならない。見つけそこない/余計なものの
出力を避けるためには、帰着した問題とされた問題の解集合が
本質的に一致している必要がある。
 数え上げでも同じように、最適解の存在が確認できるだけでは
だめで、全ての解に関する情報が必要。問題間の解の集合の
関連を示す必要がある
実問題での帰着
・ 一般的に列挙や数え上げのほうが帰着は難しい
・ それでも、役に立つ例は多い
 問題の帰着をすることで、既存のツールが使用可能になる
・ 頻出集合列挙問題で、データマイニングでの実例を見てみよう
頻出パターンの列挙
・ データベースの中に多く現れるパターンを全て見つける問題を
頻出パターン列挙(あるいは発見、マイニング)問題という
データベース: トランザクション、ツリー、グラフ、多次元ベクトル
パターン: 部分集合、木、パス・サイクル、グラフ、図形
データベース
実験1 実験2 実験3 実験4
●
▲
▲
●
▲
●
●
▲
●
●
●
▲
●
▲
●
●
●
▲
●
●
▲
▲
▲
▲
実験結果
頻出する
パターンを抽出
ATGCGCCGTA
TAGCGGGTGG
TTCGCGTTAG
GGATATAAAT
GCGCCAAATA
ATAATGTATTA
TTGAAGGGCG
ACAGTCTCTCA
ATAAGCGGCT
ゲノム情報
・ 実験1● ,実験3 ▲
・ 実験2● ,実験4●
・ 実験2●, 実験3 ▲, 実験4●
・ 実験2▲ ,実験3 ▲
.
.
.
・ ATGCAT
・ CCCGGGTAA
・ GGCGTTA
・ ATAAGGG
.
.
.
トランザクションデータベース
トランザクションデータベース:
各トランザクション T がアイテム集合 E の部分集合
になっているようなデータベース、つまり、∀T ∈D, T ⊆ E
1,2,5,6,7,9
集合 P に対して:
2,3,4,5
P の出現: P を含むD のトランザクション
D = 1,2,7,8,9
P の出現集合 Occ(P): P の出現の集合
1,7,9
P の頻出度 frq( P): P の出現集合の大きさ
2,7,9
2
{1,2}の出現集合
= { {1,2,5,6,7,9},
{1,2,7,8,9} }
{2,7,9}の出現集合
= { {1,2,5,6,7,9},
{1,2,7,8,9},
{2,7,9} }
頻出集合
・ 頻出集合: D の定数σ個以上のトランザクションに含まれる集合
(頻出度がσ以上の集合)( σを最小サポートとよぶ)
例) データベース D の3つ以上のトランザクションに含まれる集合
1,2,5,6,7,9
2,3,4,5
D = 1,2,7,8,9
1,7,9
2,7,9
2
3つ以上に含まれるもの
{1} {2} {7} {9}
{1,7} {1,9}
{2,7} {2,9} {7,9}
{1,7,9} {2,7,9}
頻出集合列挙は、与えられたトランザクションデータベース
と最小サポートσに対して、頻出集合を全て見つける問題
頻出集合の単調性
・ 工夫をするためには、何か問題の特徴を
つかまなくてはいけない
111…1
・ 使えそうなのが、「頻出集合の部分集合は
必ず頻出」、というもの(単調性という)
 つまり、ハッセ図(包含関係を
図示したもの)の上では、
頻出集合が存在する
エリアはつながっている
頻出
000…0
1,2,3,4
1,2,3 1,2,4
1,2
1,3
1
空集合から出発して、山登り的に(重複を出
さないように)探索 (共通の基本アイディア)
1,3,4
1,4
2,3,4
2,3
2,4
3,4
2
3
4
φ
頻出集合の問題点
・ 面白い頻出集合を見つけようとすると、σを小さくする必要がある
 大量の頻出集合が出てくる
・ 情報を失わずに、頻出集合的な、数の少ないものを
見つけるようにモデルを変えたい
111…1
1. 極大頻出集合:
他の頻出集合に含まれない頻出集合
2. 飽和集合:
出現集合が等しいものの中で極大なもの
000…0
極大頻出集合と飽和集合の例
・ 頻出集合を出現集合で分類
1,2,5,6,7,9
2,3,4,5
D= 1,2,7,8,9
1,7,9
2,7,9
2
3つ以上に含まれるもの
{1}
{2}
{7}
{1,7}
{1,9}
{2,7}
{2,9}
{1,7,9}
{9}
{7,9}
{2,7,9}
頻出飽和集合
極大頻出集合
出現集合の共通部分が
飽和集合になる
2部グラフによる表現
・ アイテム、トランザクションを頂点とし、包含関係を枝とする
A: 1,2,5,6,7,9
B: 2,3,4,5
D= C: 1,2,7,8,9
D: 1,7,9
E: 2,7,9
F: 2
1 2 3 4 5 6 7 8 9 P
A
B
C
D
E
F Occ(P)
・ アイテム集合と、それらを含むトランザクションの集合
 2部グラフの2部クリーク
・ アイテム集合とその出現集合
 トランザクション側が極大な2部クリーク
・ 飽和集合とその出現集合  極大2部クリーク
・ トランザクション集合の列挙へも(構造パターンにも適用可)
必須アイテムの指定
・ 特定のアイテム e を含む頻出集合だけ列挙したい
例) 1 を含む頻出集合だけ見つけたい
・ 当然、アルゴリズムの改造は簡単 ({1} から出発すればいい)
3つ以上に含まれるもの
2,5,6,7,9
1,2,5,6,7,9
{1} {2} {7} {9}
2,3,4,5
{1,7} {1,9}
2,7,8,9
1,2,7,8,9
{2,7} {2,9} {7,9}
7,9
1,7,9
{1,7,9} {2,7,9}
2,7,9
2
・ 入力を 1 を含むトランザクションに限定、各トランザクションか
ら 1 を取る、とすると、普通の頻出集合列挙に帰着できる
(2部グラフで考えるとすぐに思いつく)
数え上げの帰着
・ 数え上げも、列挙と同じように解集合間に何らかの対応が必要
・ しかし、数え上げの場合、1対1対応が無くとも、解集合の大きさだ
け一致していればよい
・ あるいは、解集合の大きさに規則性が有ればいい。例え指数倍
の開きがあっても大丈夫
・ 列挙が帰着できれば、同時に数え上げも帰着できている、ような
もの
・ この優位性を使った帰着はできないか?
2部完全マッチングの数え上げ
・ 与えられた2部グラフの完全マッチングの数を数える問題は、
#P完全であることが知られている
・ そこで、この問題を2部マッチング(完全とは限らない)の数え
上げ問題に帰着してみよう
・ しかし、マッチングの数を数えて完全マッチングの数を数える、
なんてことができるだろうか???
(1対1対応するグラフを作る?)
数え上げの優位性
・ 数え上げでは「数がわかればいい」
 元の問題の解がわからずとも、計算できればよい
・ いくつかのグラフの計算結果を組合わせたらどうだろう
 例えば、グラフAとグラフBがあって、完全マッチングでないマ
ッチングの数は同じだが、完全マッチングの数だけ倍になってい
る、という状況が作れれば、完全マッチングの数は計算できる
・ 単純にこのようなことは
できないだろうが、例えば
各大きさのマッチングの個数が
ある定数倍ずつ異なる、という
ようなことはできる
グラフの変更
・ 各頂点にひげをつけよう
・ すると、ひげの取り方で、それぞれのマッチング M におまけ
マッチングが作れる
・ M のおまけマッチングの数は、M がカバーしていない頂点の
数に依存するので、M の大きさに依存
 2の (n/2 - |M|) 乗個のおまけマッチングが作れる
・ それぞれの大きさのマッチング
が一定量変化するようにグラフを
変更できた
いくつものひげグラフ
・ マッチングの数を一定量変化させることには成功したが、これ
では不十分
 個数が変わるのは完全マッチングだけではないから
・ おまけマッチングの個数の2の●●乗の「2」は、ひげが一本
であるところから来ている
・ ひげの本数を k 本に変えると、おまけマッチングの個数は
k+1 の (n/2 - |M|) 乗個になる
・ いくつものグラフができれば、
連立方程式を立てて数を計算できる
連立方程式
・ G が持つ大きさ j のマッチングの個数を Mj、ひげを k 本つけ
たグラフのマッチングの総数を mk とする
これがわからない
・ mk は以下の式で表せる
mk = Σ(k+1)n/2 - i Mi
これは計算できる
・ こういう式がいくつもある
 Mi に関する連立1次方程式
になっている
・ (k+1)n/2 – i が作る係数行列数が
独立ならば、全ての Mi が一意に決まる
1次独立性
・ 係数行列は、
20, 21, 23,…, 2n
30, 31, 33,…, 3n
・・・
n0, n1, n3,…, nn
・ このような行列はファンデルモンド行列と呼ばれて、常に1次
独立であることが知られている
・ よって、必ず全ての Mi が一意に決まり、完全マッチングの個
数を数えることができた
格言
列挙の帰着では厳密に等価な問題を探せ
数え上げるターゲットの数を比例増分させてあぶり出せ
ソートへの帰着
・ 変換にほとんど手間がかけられない
凸包構成問題
・ 平面上にある n 点を包む極小な凸領域を考える
(ただし、へこみはつくらない)こういうものを凸包という
・凸包の辺を求める問題を凸包構成問題という
凸包の難しさ
・ 凸包の計算を使って n 個の数値のソートができる
 O(n log n) 時間はかかる
-a1,…,an をソートしたい
-点集合 (a1, a12), (a2, a22),…, (an, an2) の凸包を求める
-ソートした順番に (a1, a12), (a2, a22),…, (an, an2) に枝が張られる
線分交差列挙問題
線分交差列挙問題:
与えられた n 本の線分に対し、交わるものの組を全て見つけよ
・ 単純に総当たりで比較して O(n2) 時間、平面走査法を使って
O(n log n) 時間で解ける
同一要素判定問題の帰着
・ 線分交差列挙問題には、同一要素判定問題が帰着できる
・ 同一要素判定問題を解くには、少なくとも n log n 時間かかるこ
とが知られている
 線分交差列挙問題を解くには少なくとも n log n 時間かかる
同一要素判定問題:
入力した数 a1,…, an の中に、同じ値のものがあるか
各 ai に対して、 x 座標が ai である
場所に縦線を置く(わずかに垂直
から異なる角度ずらす)
・ 交点がある  同一要素がある
a1
a4 a3
a2
a5
平面全張木
平面全張木問題:
平面上の与えられた n 点を結ぶ全張木で枝の長さの和が最小
になるものを見つけよ
・ O(n2) 本の枝があるので、通常の全張木アルゴリズムを使うと
O(n2) 時間で解ける
・ もう少し速く、O(n log n) 時間で解ける
ソーティングの帰着
・ 平面全張木問題には、ソーティング帰着できる
・ ソーティングには、少なくとも n log n 時間かかる
 平面全張木問題を解くには少なくとも n log n 時間かかる
・ 入力した数 a1,…, an の各 ai に対して、 x 座標が ai 、y 座標が
0である場所に点を置く
・ 全張木の枝は、点を x 座標の小さい順でつなげたものになる
a1
a4 a3
a2
a5
線形計画法の帰着
・ 追加変数を使った制約式の変換
LPへの帰着
・ 線形計画を使って現実問題を定式化するときは、なにやら算
数の文章問題を解いているような気分になる
 制約条件や目的関数の意味を考えることが多いから
・ こういった問題は帰着としては扱いにくい
・ しかし、関数や条件を線形制約の組合せに変換するというこ
とは可能
 こういう問題の帰着を見てみよう
max や min を使った LP
問題: 次の数理計画問題を、線形計画問題に帰着せよ
最小化:
制約条件:
max xi
∑ ai xi ≦ b
xi ≧ 0
・ 新しい変数 t を導入する
最小化:
制約条件:
t
t ≧ xi
∑ ai xi ≦ b
xi ≧ 0
証明
証明: 実行可能な xi に対して
制約条件より t ≧ max xi は明らか。
ここで、 t > max xi であるとすると、
t > t' ≧ max xi となる t' が存在する
t' と xi の組は実行可能解なので、t は最適解でない。
対偶を取ると、「 t が最適解ならば、 t ≦ max xi 」
よって、2つの問題の最適解は同じ目的関数値を持つ
q.e.d
では問題。最小化 min xi とした問題は、線形計画になるでし
ょうか、ならないでしょうか
絶対値の帰着
・ 次は絶対値:
最小化:
制約条件:
| ∑ ci xi |
∑ ai xi ≦ b
xi ≧ 0
・ max を使った問題に直してみる
最小化:
制約条件:
 ということは、
最小化:
制約条件:
max { -∑ ci xi , ∑ ci xi }
∑ ai xi ≦ b
xi ≧ 0
t
t ≧ -∑ ci xi
t ≧ ∑ ci xi
ai xi ≦ b
xi ≧ 0
絶対値:証明
証明:
∑ ci xi ≧ 0 のとき
| ∑ ci xi | = ∑ ci xi 、 ∑ ci xi ≧ - ∑ ci xi
より | ∑ ci xi | = max { -∑ ci xi , ∑ ci xi }
∑ ci xi ≦ 0 のとき
| ∑ ci xi | = -∑ ci xi 、 ∑ ci xi ≦ - ∑ ci xi
より | ∑ ci xi | = max { -∑ ci xi , ∑ ci xi }
よって両問題の目的関数値は等しい
問題: 最大化:
| ∑ ci xi |
だとどうなるでしょうか?
続いて...
問題: 以下の問題を線形計画問題に直しなさい
最小化:
制約条件:
Π xici
Π xiai ≦ b
xi ≧ 1
軽く練習問題4-1
・ 全部、log をとってみる
最小化:
制約条件:
log Π xici
Π log xiai ≦ log b
log xi ≧ log 1
最小化:
∑ log ci log xi
制約条件: ∑ log ci log xi ≦ log b
log xi ≧ 0
yi = log xi とおくと
最小化:
∑ log ci yi
制約条件: ∑ log ci yi ≦ log b
yi ≧ 0
実行可能性の判定
問題: 次の線形計画が実行可能かどうか判定する問題を、
実行可能線形計画の最適解を見つける問題に帰着せよ
最小化:
制約条件:
max xi
∑ ai xi ≦ b
xi ≧ 0
・ 新しい変数 t を導入する
最小化:
制約条件:
t
∑ ai xi ≦ b+t
xi ≧ 0
輸送問題
・ 工場 1,2,…,n
・ 小売店 1,2,…,m
・ 工場の生産量
s1 , s2 ,…, sn
・ 小売店の需要量
t1 , t2 ,…, tm
・ 工場 i から小売店 j
への輸送コスト cij
@10円
500個
1000個
1800個
2000個
800個
1500個
工場から顧客へ商品を送るとき、最小コストで運ぶには
どこからどこにどれだけ運べばいいかを求める問題
1500個
最小費用流問題
・ 輸送問題に、中継地点と、各ルートの輸送量の上限を付けた問題
≦30
≦20
100個
どのように品物を運ぶとコストが最小になるか?
70個
最小費用流問題:定式化 (2)
最小化
制約条件
Σi=1,…,n Σj=1,…,n cij × xij
(Σj=1,…,m xji )-(Σ j=1,…,m xij) = bi
0 ≦ xij ≦ uij
・ この問題も線形計画問題
・ 輸送問題は、最小費用流問題の特殊ケース
・ 実は、最小費用流問題も、輸送問題の特殊ケースになっている
最小費用流問題の変形
・ 最小費用流問題の各枝を、輸送問題の(1頂点+2枝)に変
換
最小費用流
bi
vi
cij, uij
輸送問題
bj
vj
b'ij = uij
b'i = bi - uij
0
vi
cij
vj
vij
b'j = bj
・ vi 、vj は、複数個作らない(共有する)
この変形を、全ての枝について行う
最小費用流問題の変形 (2)
・ vi から vj に y 流れる
 bi が bi - y に減り、 bj が bj + y に増える。コストは cij y
・ vij から vi , vj に uij - y, y ずつ流れる
 bi が bi - y に減り、 bj が bj + y に増える。コストは cij y
※ 0 ≦ y ≦ uij
bi-y
y
vi
bj+y
vj
b'ij = uij
uij-y
vij
y
b'i = bi - uij
vi
vj
b'j = bj
両者は等価:
この変形を、全ての枝について行えばよい
格言集
排他的選択は、必須選択の数で抑えよ (セットカバー)
制約の変数数は、ガジェットを作って増減させよ (頂点被覆)
都合の良い状況に選択肢を与えて排他条件をつけよ (独立集合)
数は桁に分けて制約(スイッチ)にせよ (サブセットサム)
合計の差異は人工変数で吸収せよ (サブセットサム)
固定制約にはダミーで対応せよ (サブセットサム亜種)
「ちょうど」は「これ以下で最大」に (サブセットサムの帰着)
ハミルトン**はスイッチで制約、空ガジェットで選択肢を表現
平面的な帰着では、枝をグラフ(ガジェット)で置き換えよ
列挙の帰着では厳密に等価な問題を探せ
数え上げるターゲットの数を比例増分させてあぶり出せ
心得
一.
自分の得意なルートを作れ
一.
一.
問題は構造から見よ
論文は証明してから読め
演習問題1-1
問題: 以下の問題を線形計画問題に直しなさい
最小化:
制約条件:
max xi + max yi
∑ ai yi ≦ b
∑ ai xi ≦ b
xi ≧ 0
最小化:
制約条件:
∑ ( ci xi + ei yi )
max ai xi + max di yi ≦ b
∑ ai xi ≦ f
∑ di xi ≦ f
xi , yi ≧ 0
演習問題1-2
問題: 以下の問題を線形計画問題に直しなさい
最小化:
制約条件:
| ∑ xi | + | ∑ yi |
∑ ai yi ≦ b
∑ ai xi ≦ b
最小化:
制約条件:
∑ ( ci xi + ei yi )
| ∑ xi | + | ∑ y i | ≦ b
∑ ai xi ≦ f
∑ di xi ≦ f
最小化:
制約条件:
∑ ci2 xi2
∑ ai2 xi2 ≦ b2
xi ≧ 0
演習問題2-1
・ サブセットサムの亜種 (2) をサブセットサムに帰着せよ
亜種(2):「与えられた n 個の数 a1,…,an の中からいくつかを選び、
合計がちょうど (Σai) / 2 にできるかどうかを答えよ」
・ 頂点被覆問題は、例えグラフの各頂点の次数が高々3でもNP完
全であることを示せ
・ 頂点被覆問題は、例えグラフの各頂点の次数が全て3でもNP完
全であることを示せ
・ 頂点被覆問題に、「隣接する頂点は同時に選んではいけない」と
いう条件をつけた問題がNP完全となることを示せ
演習問題2-2
・ 「m 個の選択肢の中からちょうど k 個選ぶ」という制約を実現す
る、独立集合のガジェットを作れ。具体的には、あるグラフで、そ
のグラフの大きさ h の任意の独立集合は、グラフの特定の頂点
部分集合 U の中のちょうど k 個の頂点を含み、かつそのグラフ
は大きさ h 以上の独立集合を持たないようなグラフを作れ
・ 上記の問題を、セットカバーについて解け。つまり、特定の部分
集合のうちちょうど k 個を必ず選ぶ必要があるように、部分集
合と、解の大きさ h を設計せよ
演習問題2-3
・サブセットサムを独立集合に帰着する問題を考える。しかし、整
数をグラフで扱うのは大変なので、まずは簡単な問題、サブセッ
トサムの入力は、10進数で、各桁が 0 か 1 であり、サブセットサ
ムの入力する数が a1,a2 の2つしかないものを考える。この問題
を独立集合に帰着せよ
・ 上記の問題を、n+1 進数で各桁が 0 か 1 であり、サブセットサム
が入力する数が a1,…, an の n 個である場合を考え、合計 b の
各桁も 0 か 1 である問題を、独立集合問題に帰着せよ
・ 上記の問題で b が任意の数をとれる場合を考えよ
・ 上記3つの問題をセットカバーで考えよ
演習問題2-4
・ 与えられた n 頂点(偶数)を持つグラフが、大きさ n/2 の独立集
合を持つかどうかを判定する問題に、独立集合問題を帰着せよ
・ 上記の演習問題に「グラフが連結であること」という条件をつけて
解答せよ
・ セットカバー問題を独立集合問題に帰着する方法を考えよ
・ 独立集合問題をサブセットサム問題に帰着する方法を考えよ
演習問題3-1
・ 集合被覆問題を支配集合問題に帰着せよ
「グラフ G=(V,E) と数 k に対して、大きさ k の頂点集合 S で、Gの
どの頂点も S に含まれるか、あるいは S の点に隣接するような
ものが存在するか?」
ヒント: 普通に帰着すると、集合被覆でカバーされるべき要素を、
選択肢の頂点として選んで良くなってしまう。これを回避するた
め、確実に、部分集合に対応する頂点のみを、強制的に選ばせ
るガジェットを作ればよい
演習問題3-2
・ 最小スターナーツリー問題がNP完全であることを示せ
「グラフ G=(V,E) と頂点集合 S と数 k に対して、枝数が k で S を
全て含む G の部分木を求めよ」
(図の緑色の枝が作る木は、赤い頂点の集合 S を含む部分木)
ヒント: 一定の個数でカバーする、という問題だと考える。何かしら
のカバーの問題だと思って、枝数が限定されている状況と、カバ
ーするものが限定されている状況を一致させればよい
・ 頂点集合 S が、木の葉になること、
という条件をつけた場合はどうなるか
演習問題3-3
・ 最小コーダル補完問題がNP完全であることを示せ
最小コーダル補完問題:
グラフ G を部分グラフとして含む枝数 k のコーダルグラフがあ
るか?
ヒント: 長さ4のサイクルをスイッチとして利用
(どちらかの対角線を入れなければならない)
二者択一なので、頂点被覆を帰着
演習問題3-4
・ 最小極大マッチング問題がNP完全であることを示せ
最小極大マッチング問題:
2部グラフ G に対して、端点を共有しない枝部分集合をマッチング
と呼び、他のマッチングに真に含まれないマッチングを極大マッ
チングという。問題は、大きさ k の極大マッチングがあるか判定
ヒント: 極大である  任意のマッチングでない枝は、マッチング枝
に隣接する、なので、これをセットカバー的な要因だと見なす。カバ
ーすべき枝を設定し、隣接する枝を
どれか選ぶという状況を作る。1つの
枝が2つの頂点にしか隣接できず、多
くの枝の影響を受けられない点は、
ガジェットを作って解決する
演習問題3-5
・ クリークカバー問題がNP完全であることを示せ
クリークカバー問題:
グラフ G の k 個のクリークの集合で、全ての頂点をいずれかのク
リークに含むものがあるかどうかを判定する問題
ヒント: まず、セットカバー的な問題であることは明らか。しかし、単純に
「要素=頂点」「部分集合=クリーク」とすると破綻。なぜならAB、BC、
ACというクリークがあると、自動的にABCがクリークになってしまうから。
これを回避するため、各頂点を単独のクリーク
がカバーするようにし、部分集合に対応する
クリークを選択すると、その部分集合に
含まれる頂点をカバーする単独クリークが
まとめて使えるようにするガジェットを作る
演習問題3-6
・ グラフ G とその頂点部分集合 S に対して、 S の頂点を含まな
い極大独立集合があるかどうかを判定する問題がNP完全で
あることを示せ
ヒント: S の頂点を含まない極大独立集合であるためには、S の
どの頂点に対しても、隣接する頂点が極大独立集合に含ま
れていなければならない。これは、ある意味、セットカバー、
あるいはSAT的な制約である。あとは、独立集合であるため
の条件と、SATのリテラルの排他条件、
S
あるいはセットカバーの使える
部分集合が k 個である、という
条件の対応付けをすればよい
演習問題3-7
・ 最小フィードバック頂点集合問題がNP完全であることを示せ
最小フィードバック頂点集合問題:
有向グラフ G の k 個の頂点の集合 S で、 G のどの有向サイクル
も S の頂点を1つは含むようなものが存在するか?
ヒント: 明らかにセットカバー的な要因を持つ。カバーされるべき
要素それぞれに対応する有向サイクルを作り、その頂点のどれか
を抜く問題設定にする。部分集合を
選ぶ  いくつかの頂点をまとめて抜
く、とする必要があるため、長さ2の有向
サイクルを枝としたスターを作り、真ん中
を選ぶか、周り全てを選ぶか、とする。
演習問題3-8
・ 有向グラフ G と頂点 s, t と有向枝 e に対して、 s から t への
有向枝 e を通る単純な有向パス(同じ頂点を2度通らないパ
ス)が存在するか判定する問題が NP 完全であることを示せ
ヒント: 同じ頂点を2度通ることはできない、というところが排他
制約。そこで、s から e までにルート(往き道)がリテラルの選
択、 e から t へのルート(帰り道)が節の実行可能性の制約、
という形でSATを帰着。
往き道で、各変数について、TRUE
FALSEの選択をし、選択をした頂点を
通らないようにする。帰り道では、各節
s
e
を通って帰り、各節の中では、その節が
t
含むリテラルのどれかを通過しなければ
ならないようにする
演習問題3-9
・ グラフ分割問題がNP完全であることを示せ
「グラフ G と数 k に対して、V を同じ大きさに分割し、2つのグルー
プの頂点を結ぶ枝の数が k 本以下になるものがあるか答えよ」
ヒント:排他条件を入れるのが難しい。排他条件を実現するため、
選択に対応する大きなクリークをたくさん作り、これらを密につな
ぎ、2つのものを同時に入れると損が出るようにする
(得するようにするには、クリーク間に枝を
張ればいい。損するようにするには、
クリーク間以外に枝を張ればいい)
あとは、選択してない頂点と節の
間に枝をはって、節のリテラルを選ぶことを
表現。節とリテラル間のカットの大きさを吸収するガジェットを利用
演習問題3-10
・ 2部グラフの完全マッチングの数え上げ問題を、有向グラフのs-t
ハミルトンパスの数え上げ問題に(多項式時間で)帰着せよ
・ 有向グラフのs-tハミルトンパスの数え上げ問題を、(長さがどうで
もよい)シンプルなs-tパスの数え上げ問題に(多項式時間で)帰
着せよ
ヒント: 1つ目は、単なるグラフの変換。2つ目は、長さ k のパスが
f(k) 個に増えるよう、枝をガジェットで置き換える
s
t
演習問題4-1
・ 頂点彩色問題がNP完全であることを示せ
頂点彩色:
グラフ G の各頂点に k 種類の色のどれかを塗り、隣接する頂点
が同じ色にならないようできるか?
演習問題4-2
・ 最小インターバルグラフ補完問題がNP完全であることを示せ
最小インターバルグラフ補完問題:
グラフ G を部分グラフとして含む枝数 k のインターバルグラフ
があるか?
演習問題4-3
・ グラフの木の数を数え上げる問題が#P完全であることを示せ
・ グラフの森の数を数え上げる問題が#P 完全であることを示せ
・ グラフのパスの数を数え上げる問題が#P 完全であることを示せ
・ グラフの極小カットの数を数え上げる問題が#P 完全であることを
示せ
(極小カットとは、頂点部分集合 S で、カット
枝集合が S のカット枝集合の部分集合
になるような部分集合を持たないものを
いう。 S のカット枝とは、 S の頂点と
S 以外の頂点を結ぶ枝のことである )
演習問題X
・ 最スライドの中で、「○○ガジェット」が「○○がジェット」になっ
ていたところは全部でいくつあったでしょうか