1

NP 完全問題に対するアルゴリズムについて学ぶØ 最小頂点被覆問題に対する 2 近似アルゴリズム
Ø NP 完全問題に対する厳密アルゴリズムと FPT
Ø 頂点被覆問題に対する FPT アルゴリズム

23

入力：無向グラフ G と正の整数 k
問：G には大きさ k の頂点被覆が存在するか？

頂点被覆
任意の辺に対して、少なくとも一方の端点が属する頂点集合

k=4 の例4入力：無向グラフ G
出力：最小頂点被覆 U

G5

多項式時間近似アルゴリズム
Ø 2 近似 [Gavril, Yannakakis]

Ø 2 − 1/Θlog 𝑉

[Karakostas 04]

近似困難性Ø P=NP でないかぎり，1.3606 近似多項式時間アルゴリズムは存在しない [Dinur and Safra 2005]
Ø Unique Games Conjecture が成り立つならば，2-ε近似多項式時間アルゴリズムは存在しない [Knot and Regev 2003]6マッチングØ グラフの辺集合で、集合内の各辺が互いに頂点を共有しないもの。

7極大マッチング
Ø マッチングの中で、これ以上は新しい辺をマッチングに加えることができないもの。

極大マッチング

極大マッチングでない
8

最大マッチングØ 極大マッチングの中で、マッチングに含まれる辺の数が最大のもの。

最大マッチング
9極大マッチングを使った 2 近似アルゴリズム
1．グラフ G の極大マッチング M を求める
2．M の各辺の両端の頂点を頂点被覆 Uʼ として選択する
3．Uʼ を出力する

10

1．グラフ G の極大マッチングMを求める
Ø 辺を 1 つ 1 つ見ていき、両端点がまだ M に含まれていなければ、M に入れる。そうでなければ、M に入れない。

11

2．M の各辺の両端の頂点を頂点被覆 Uʼ として選択する
3．Uʼ を出力する

12

アルゴリズム：グラフ G の頂点数 n，辺の数 m
1.

グラフ G の極大マッチング M を求める → O(m)2.

M の各辺の両端の頂点を頂点被覆 Uʼ として選択する→ O(n)

3.

Uʼ を出力する → O(n)計算時間は、O(n+m)

13最小頂点被覆 U、アルゴリズムの出力 Uʼ、極大マッチング Mの間には、次の関係が成り立つ
1．|U|

|Uʼ|

2．|M|

|U|

3．|Uʼ| = 2|M|
2、3より、 |Uʼ| = 2|M|

2|U| となる

アルゴリズムが出力する解のコスト
近似率：の最悪値
最適解のコスト14

15

やっぱり厳密解が欲しい
Ø 指数時間はかけたくないØ 解が正確に求まる保証はほしい
頂点被覆問題の単純な厳密アルゴリズム：O(nkｍ) = O(nk+2)
Ø 全てのサイズ k の頂点集合 (=O(nk)) について，頂点被覆となっているかを確認する（集合1つあたり O(ｍ) )k が定数なら多項式時間ではあるが…
Ø n=10000、k=10 なら 1000012 =1048 ！

16

k が 10 のときくらい、もう少し高速にできないのか？
Ø もっと言うと，k がある程度小さい間は n が大きくなっても、できるだけ問題を解きたい → O(n0.5k) に改良する？？

今は、O(nf(k)) の形になっている
n が増えると、f(k) の影響を大きく受けてしまう計算時間において、n と k が関係していることが影響。

17

FPT（Fixed Parameterized Tractable：固定パラメータ容易）Ø 入力サイズを n、あるパラメータを k とすると、O(f(k) nO(1)) 時間アルゴリズムで解ける問題の集合

FPT アルゴリズムは多項式時間アルゴリズム？
Ø k が n の関数に依存することもあるので、そうではない。
ü O(2kn) は FPT だが、k=n のときは O(n2n)18

FPT アルゴリズムは何が嬉しい？
Ø 厳密解が得られる
Ø k と n の関数が独立しているので、k が増えても、n への影響がある程度抑えられる！（ n に対しては多項式時間）
ü O(2kn) で n=10000、k=10 なら 210 10000107※ O(nk+2) では約 1048
Ø k が小さいときには十分高速なアルゴリズム
ü 入力サイズが大きくても動作する可能性がある

19

NP 完全問題は全て FPT アルゴリズムが存在する？
未解決（たぶんない）

NP 完全問題の中でも難しさの階層があるはず．
• FPT アルゴリズムをもつ問題• FPT アルゴリズムをもたなさそうな問題（ W 階層）• W[1] 困難、W[2] 困難、...

20

FPT アルゴリズム
Ø O(2kn) 時間：単純な Branch and BoundØ O(k22k+n2)：Kernelization
Ø O(1.2738k+kn) [Chen, Kanji and Xia 2006]

困難性Ø ETH ( Exponential Time Hypothesis )下では，2o(k)nO(1) 時間アルゴリズムは存在しない（cf : O(2 kn) 時間など）
ü ETH：3SATを解くには、2cn (c>0) 時間必要という仮説
ü 3SAT の最速決定性アルゴリズムは O(1.328n) [Liu 2018]
21

22

入力：無向グラフ G と正の整数 k
問：G には大きさ k の頂点被覆が存在するか？

頂点被覆：
任意の辺に対して、少なくとも一方の端点が属する頂点集合

k=4 の例23

O(2kn) 時間アルゴリズム
G - v： G から頂点 v につながる辺をすべて取り除いたグラフ
O(2kn) 時間アルゴリズム BS(G, k)：G の頂点数 n1．G に辺がない → 0 を返す
2．k=0 → n+1 を返す
3．G の辺 (u, v) を適当に 1 本選ぶ・min(BS(G-u, k-1), BS(G-v, k-1))+1 を返す．
BS(G, k) の値が k 以下であれば Yes、それ以外は No を出力
244k=4k=33

3k=22・・・・・・・・・k=111k=0700025

T(n, k)：頂点数 n のグラフ G に対するサイズ k の頂点被覆を求める前述のアルゴリズムの計算時間

3．G の辺 e = (u, v) を適当に 1 本選ぶ・min( BS(G-u, k-1), BS(G-v, k-1) ) + 1 を返すを考えると、T(n, k) = 2T(n, k-1) + O(n) ：辺の削除に O(n)より、T(n, k) = O(2kn)26ざっくり言うと、「解くために本質的に難しい箇所」
Ø Kernel を解けば（ほぼ）解になっている

カーネル

27

カーネルに「還元」する．
入力（x, k）：元のインスタンス
出力（xʼ, kʼ）：カーネル化後のインスタンス制約Ø |xʼ| = f(k)Ø kʼ = g(k)
Ø |x| + k の多項式時間で還元

FPT アルゴリズムをもつカーネル化可能[Cai, Chen, Downey, and Fellows 1997]28

O(k22k+n2) 時間アルゴリズム：1 がカーネル化
1．次数が k より大きい頂点 v がある間、次の操作を続ける．
Ø v を頂点被覆 U の集合に加え、その頂点と頂点につながる辺をすべて取り除く
2．1 を終えた後のグラフを Gʼ, U に加えた頂点の数を a とする
アルゴリズム BS(Gʼ, k-a) を動作させる
3．2 の出力が k-a 以下であれば Yes、それ以外は No を出力．

29

次数が k より大きい頂点を全て取り除いたグラフを Gʼ とする．
Gʼ の頂点集合を Vʼ、頂点被覆を Uʼ とする
このとき、Vʼ-Uʼ 内の頂点間には辺はない
もし、あるとすると Uʼ は頂点被覆になっていない
Uʼ

Vʼ-Uʼ
頂点間に辺はない

30

Uʼ の各頂点は最大でも Vʼ-Uʼ 内の k 個の頂点とつながっている
ので、|Vʼ-Uʼ|k|Uʼ| となる。

よって、|Vʼ| = |Uʼ|+|Vʼ-Uʼ|Uʼ(k+1)|Uʼ|k(k+1)Vʼ-Uʼ

31

カーネル化は O(n2) で終わり、下記を満たす。
Ø |Vʼ|
Ø kʼ

k(k+1)
kアルゴリズム BS(n, k) は計算時間が O(2kn) より、BS( k(k+1), k )の計算時間は O( 2kk(k+1) )=O( k22k )となる。

アルゴリズム全体の計算時間は、O( k22k+n2 )となる。

32

（最小）頂点被覆問題のアルゴリズム
Ø 2 近似アルゴリズム

NP 完全問題と FPT
Ø NP 完全問題の FPT アルゴリズム
ü 解のサイズが小さいときは高速にみつけることが可能．
Ø カーネルと FPT

他にも色んなアルゴリズム技法があるので、興味のある人は調べてみるとよい。

33