章 多項式時間計算可能性の分析

第

6

章 多項式時間計算可能性の分析 第

6

章 多項式時間計算可能性の分析

6.1. 多項式時間還元可能性

定義6.1:

AとBを任意の集合とする．

(1) 関数h: AÆB: 多項式時間還元(polynomial-time reduction) (a) h

はΣ

^∗

からΣ

^∗

への全域的関数

(b)

(c) h

は多項式時間計算可能．

(2) AからBへの多項式時間還元が存在するとき，

AはBへ多項式時間還元可能という(polynomial time reducible).

このとき，次のように書く：

] ) ( [

* x A hx B

x∈Σ ∈ ↔ ∈

P

A≤mB

1/14

Chapter 6. Analysis on Polynomial-Time Computability

Chapter 6. Analysis on Polynomial-Time Computability

6.1. Polynomial-time Reducibility

Def.6.1:

Let Aand Bbe arbitrary sets.

(1) function h: AÆB: polynomial-time reduction (a) his a total function from Σ^∗ onto Σ^∗ (b)

(c) his polynomial-time computable．

(2) When there is a polynomial-time reduction from Ato B，

we sayAis polynomial-time reducible to B.

Then，we denote by

] ) ( [

* x A h x B

x∈Σ ∈ ↔ ∈

P

A≤mB

1/14

6.2. 多項式時間還元可能性に基づく完全性 6.2.1. 完全性の定義とその基本的性質

定義6.2: 計算量クラスCに対し，集合Aが次の条件を満たすとき，

それを（ の下で）C-完全という．

(a) L C[L A]

(b) A C

補注：条件(a)を満たす集合はC-困難．

P

≤m

∀ ∈ ≤^P_m

∈

7/14

例6.5. クラスNPの完全集合の例

3SAT, SAT, ExSAT, DHAM, KNAP, BIN, VCなど

クラスEXPの完全集合

EVAL-IN-E, HALT-IN-Eなど

6.2.Completeness based on Polynomial-time Reducibility 6.2.1. Definition of Completeness and its Basic Properties

Def.6.2:For a class C，if a set Asatisfies the following conditions, then it is called C-complete(under )

(a) L C[L A]

(b) A C

Note：Sets satisfying the condition (a) are called C-hard．

P

≤m

∀ ∈ ≤^P_m

∈

7/14

Ex.6.5.Examples of NP-complete sets

3SAT, SAT, ExSAT, DHAM, KNAP, BIN, VC, etc EXP-complete sets

EVAL-IN-E, HALT-IN-E, etc.

定理6.3. 任意のC-困難集合（含：C-完全集合）Aに対し，

(1) A PÆC

⊆

P

対偶は

C P ÆA P

(2) A NPÆC

⊆

NP

対偶は

C NP ÆA NP

(3) A co-NP ÆC

⊆

co-NP

対偶は

C co-NP ÆA co-NP

(4) A EXPÆC

⊆

EXP

対偶は

C EXP ÆA EXP

∈

∈

∈

∈

∉

∉ ∉

∉

⊄

⊄⊄

⊄

証明：

(1) Bを任意のC集合とすると，AはC-困難だから，

A

B≤^P_m

一方，

A Pの仮定より，B P

（定理

6.1

）

(2), (3), (4)も同様

∈ ∈

9/14

Theorem 6.3.For any C-hard (or C-complete) set A，

(1) A PÆC

⊆

P CP: C P ÆA P

(2) A NPÆC

⊆

NP CP: C NP ÆA NP

(3) A co-NP ÆC

⊆

co-NP CP: C co-NP ÆA co-NP (4) A EXPÆC

⊆

EXP CP: C EXP ÆA EXP

∈

∈

∈∈

∉∉

∉∉

⊄

⊄⊄

⊄

Proof： CP: contraposition

(1) LetBbe any C-set. Then, since Ais C-hard, A

B≤_m^P and by the assumption A Pwe haveB P

（Th. 6.1）

(2), (3), (4) are similar.

∈ ∈

9/14

例6.6. 定理6.3の意味（クラスNP)

AをNP-完全集合とする．

定理6.3(1)の対偶より，

NP PÎA P

定理6.3(3)の対偶と定理5.9(1)の対偶より，

A co-NP

つまり，NP- 完全集合はP NPである限り，

多項式時間では認識できない．

∉

≠ ∉

≠

10/14

定理5.9.

(1) NP

⊆

co-NPÆNP= co-NP

定理6.3. 任意のC-困難集合（含：C-完全集合）Aに対し，

(1) A PÆC

⊆

P

対偶は

C P ÆA P

(2) A NPÆC

⊆

NP

対偶は

C NP ÆA NP

(3) A co-NP ÆC

⊆

co-NP

対偶は

C co-NP ÆA co-NP

(4) A EXPÆC

⊆

EXP

対偶は

C EXP ÆA EXP

∈

∈

∈

∈

∉

∉ ∉

∉

⊄

⊄⊄

⊄

Ex.6.6:Meaning of Theorem 6.3（class NP) Let Abe NP-complete set．

By the contraposition of Theorem 6.3(1) we have NP PÎA P

By the contraposition of Theorem 6.3(3) and that of Theorem 5.9(1)，

A co-NP

That is，NP-complete sets are NP-sets that cannot be recognized in polynomial time unless P= NP.

∉

≠ ∉

10/14

Theorem 5.9.

(1) NP

⊆

co-NPÆNP= co-NP Theorem 6.3.For any C-hard (or C-complete) set A，

(1) A PÆC

⊆

P CP: C P ÆA P

(2) A NPÆC

⊆

NP CP: C NP ÆA NP

(3) A co-NP ÆC

⊆

co-NP CP: C co-NP ÆA co-NP (4) A EXPÆC

⊆

EXP CP: C EXP ÆA EXP

∈

∈

∈∈

∉∉

∉∉

⊄⊄

⊄⊄

NP-完全集合はP NPである限り，NP co-NPには入らない NP集合である．

≠ ∩

NP

P

co-NP

NP完全 co-NP完全

11/14

NP-compete sets are NP-sets that do not belong to NP^∩co-NPunless P= NP.

NP

P

co-NP

NP-complete co-NP-complete

11/14

例6.7. 定理6.3の意味（クラスEXP)

DをEXP-完全集合とする．

定理6.3(1)の対偶（C P

ÆA P,

ここではEXP P

ÆD P) P EXPÆEXP P ( P

⊆

EXP) ÆD P

定理6.3(2)の対偶（C NP

ÆA NP,

ここではEXP

NP ÆD NP) NP EXP ÆEXP NP ( NP

⊆

EXP) ÆD NP

定理6.3(3)の対偶（C

co-NP ÆA co-NP,

ここではEXP

co-NP ÆD co-NP)

co-NP EXPÆEXP co-NP ÆD co-NP

ところが定理5.7から であるから，D

P.

EXP-完全集合は多項式時間では計算不可能．

⊄ ⊄

⊄

⊄ ⊄

⊄

∉ ∉

∉ ∉

∉ ∉

∉

∉ ∉

≠

≠

≠

⊄ ⊄

⊄ ^∴ ∉

∴

12/14

y P EXP

Ex. 6.7.Meaning of Theorem 6.3（class EXP) Let Dbe an EXP-complete set．

Contraposition of Theorem 6.3(1)

（C P

ÆA P, where EXP P ÆD P) P EXP ÆEXP P( P

⊆

EXP) ÆD P Contraposition of Theorem 6.3(2)（C NPÆA NP,

Here, EXP NP ÆD NP) NP EXP ÆEXP NP ( NP

⊆

EXP) ÆD NP Contraposition of Theorem 6.3(3)（C co-NP ÆA co-NP,

here, EXP co-NP ÆD co-NP)

co-NP EXPÆEXP co-NP ÆD co-NP

But，by Theorem 5.7，since we know ，we have D P.

EXP-complete sets are not computable in polynomial time．

⊄ ⊄

⊄

⊄ ⊄

⊄

∉ ∉

∉ ∉

∉ ∉

∉ ∉

∉

≠

≠

≠

⊄

⊄

∉

∴ ⊄

∴

12/14

y P EXP

定理6.4.

A: 任意のC-完全集合

すべての集合Bに対し，

(1) A BÆBはC-困難．

(2) A B B CÆBはC-完全．

P

≤m P

≤m ∧ ∈

証明：

定義6.2より，

定理6.2より，

したがって，

すなわち，BはC-困難．

[ ]

[ ]

P m

P P P

m m m

P m

L L A

L A A B L B

L L B

∀ ∈ ≤

≤ ∧ ≤ → ≤

∀ ∈ ≤ C C

13/14

Theorem 6.4.A: any C-complete set For any set Bwe have (1) A BÆBis C-hard.

(2) A B B CÆBis C-complete．

P

≤m P

≤m ∧ ∈ Proof：

By Def. 6.2 By Theorem 6.2，

Therefore，

That is，Bis C-hard．

13/14

[ ]

[ ]

P m

P P P

m m m

P m

L L A

L A A B L B

L L B

∀ ∈ ≤

≤ ∧ ≤ → ≤

∀ ∈ ≤ C C

EXPC {L: LはEXP-完全}

NPC {L: LはNP-完全}

とすると，次の定理が成り立つ．

≡≡

定理6.5.

(1) EXPC P= φ (2) EXP– (EXPC^∩ ∪P) φ≠

EXP EXPC

P

定理6.6: P

NPを仮定すると

(1) NPC P= φ (2) NP– (NPC P) φ

∩

∪ ≠

≠

NP

NPC

P

NP∩co-NP

}

14/14

EXPC {L: Lis EXP-complete}

NPC {L:Lis NP-complete}

Then, we have the following theorems．

≡≡

Theorem 6.5.

(1) EXPC P = φ (2) EXP– (EXPC^∩ ∪P) φ≠

EXP EXPC

P Theorem 6.6: Assuming P NP

(1) NPC P= φ (2) NP– (NPC P) φ

∩ ∪ ≠

≠

NP

NPC

P

NP∩co-NP

}

14/14

6.2.2. 完全性の証明

(NP)完全性の証明方法

(I) 定義通りに[すべてのL]について示す

(II) すでに完全であることがわかっている問題を利用する (I)の例: 定理6.7, 定理6.9(≒Cookの定理(SATでTMを模倣))

(II)の例: 例6.4(3SAT DHAM), 定理6.10, … DHAMは一般のグラフ上でNP完全

DHAMは平面グラフに限定してもNP完全 DHAMは「頂点の次数＝3」に限定してもNP完全 DHAMは2部グラフに限定してもNP完全…

1/11

P

≤m

基本的には…

1. 多項式時間で動く標準プログラムを考えて 2. プログラムの動作を命題論理式で模倣する

→とても大変(手間がかかる)

3SATなどは、形式

が一様なので扱い やすい

6.2.2. Proof for completeness

Two ways to prove (NP-)completeness (I) show ‘for all L’ according to definition (II) use some known complete problems Ex for (I) : Theorem 6.7,

Theorem 6.9(≒Cook’s Theorem; simulate TM by SAT)

Ex for (II): Example 6.4(3SAT DHAM), Theorem 6.10, … DHAM is NP-complete for general graphs

DHAM is NP-complete even for planar graphs

DHAM is NP-complete even for graphs with max degree=3 DHAM is NP-complete even for bipartite graphs …

1/11

P

≤m

Basically…

1. For any program in standard form, 2. simulate it by SAT formulae

→pretty complicated and tedious

Easy to manipulate

since, e.g., 3SAT has a uniform structure.

定理6.10: 以下にあげる集合はすべてNP-完全

(1) 3SAT, SAT (ExSATからの還元）

(2) DHAM, VC (3SATからの還元）

(3) KNAP, BIN (3SATからの還元とKNAP BIN)≤^P_m

2/11

(II)NP完全性がわかっている問題からの多項式時間還元:

1. 3SAT VC

2. DHAM 頂点の次数が高々5に制限されたDHAM≤^P_m

P

≤m

Vertex Cover: すべての辺の、少なくとも一方の頂点を含む集合 Hamiltonian cycle: すべての頂点を一度ずつ通る閉路

おまけ: DHAMは次数高々3でもNP完全。

高々2だと多項式時間で計算可能。

Theorem 6.10 The following sets are all NP-complete:

(1) 3SAT, SAT (reduction from ExSAT）

(2) DHAM, VC (reduction from 3SAT）

(3) KNAP, BIN (reduction from 3SAT and KNAP BIN)≤^Pm

(II) Polynomial time reductions from NP-complete problems:

1. 3SAT VC

2. DHAM DHAM with vertices of degree ≦5≤^P_m

P

≤m

2/11

Vertex Cover: a vertex set that contains at least one endpoint for each edge

Hamiltonian cycle: a cycle that visits each vertex exactly once Note : DHAM remains NP-complete even if max degree 3.

But it is polynomial time solvable if max degree 2.

定理6.10(2) : VC は

NP

完全問題

P

≤m

3/11

[証明] VC ∈NP

なので、3SAT VC であることを示せばよい。

論理式

F(x₁,x₂,…,x_n) が与えられたとする。

Fから以下の条件を満たすグラフと自然数の組<G, k>が

多項式時間で構成できることを示す：

Fを1にする割当が存在する⇔Gがサイズkの頂点被覆を持つ

Gの構成(Fはn変数m項とする):

1. Fの各変数x_i

に対し、頂点

x_i⁺,x_i^-

と、辺(x

_i⁺,x_i^-)を加える 2. Fの各項C_j=(l_i1

∨l

_i2

∨l

_i3)に対し、頂点l_i1, l_i2, l_i3

と辺(l

_i1,l_i2),

(l_i2,l_i3), (l_i3,l_i1)を加える

3.

項C

_j

のリテラル

l_i1

が

x_i

のときは辺(l

_i1,x_i⁺) を、￢x_i

のときは辺

(l_i1,x_i^-) を加える。

4. k= n+2m

Theorem 6.10(2) : VC is NP-complete

3/11

[Proof] Since VC ∈NP, we show 3SAT VC.

For given formula F(x₁,x₂,…,x_n), we construct a pair <G,k>

of a graph and an integer in polynomial time.

There is an assignment that makesF()=1

⇔G has a vertex cover of size

k

Construction ofG (F hasn variables and m clauses):

1. add vertices x_i⁺,x_i^-and the edge (x_i⁺,x_i^-) for each variable x_iin F 2. For each clauseC_j=(l_i1

∨l

_i2

∨l

_i3) in F, add vertices l_i1, l_i2, l_i3and

three edges (l_i1,l_i2), (l_i2,l_i3), (l_i3,l_i1)

3. add the edge (l_i1,x_i⁺) if the literal l_i1is x_i, or add (l_i1,x_i^-) if it is ￢x_i for each clause C_j

4. let k= n+2m

P

≤m

Fを1にする割当が存在する⇔Gがサイズkの頂点被覆を持つ

Gの構成(Fはn変数m項とする):

1. Fの各変数x_i

に対し、頂点

x_i⁺,x_i^-

と、辺(x

_i⁺,x_i^-)を加える 2. Fの各項C_j=(l_i1

∨l

_i2

∨l

_i3)に対し、頂点l_i1, l_i2, l_i3

と辺(l

_i1,l_i2),

(l_i2,l_i3), (l_i3,l_i1)を加える

3.

項C

_j

のリテラル

l_i1

が

x_i

のときは辺(l

_i1,x_i⁺) を、￢x_i

のときは 辺(l

_i1,x_i^-) を加える。

4. k= n+2m

例:

F(x₁,x₂,x₃,x₄) = (x₁

∨x

₂

∨x

₃)∧(￢x₁

∨x

₃

∨x

₄)∧(x₁

∨￢x

₃

∨x

₄) x₁⁺ x₁^- x₂⁺ x₂^- x₃⁺ x₃^- x₄⁺ x₄^-

x₁ x₂ x₃

￢x

₁ x₃ x₄

x₁

￢x

₃ x₄

G k = 4+2×3=10

4/11

Ex: F(x₁,x₂,x₃,x₄) = (x₁

∨x

₂

∨x

₃)∧(￢x₁

∨x

₃

∨x

₄)∧(x₁

∨￢x

₃

∨x

₄) x₁⁺ x₁^- x₂⁺ x₂^- x₃⁺ x₃^- x₄⁺ x₄^-

x₁ x₂ x₃

￢x

₁ x₃ x₄

x₁

￢x

₃ x₄

G k = 4+2×3=10

4/11 There is an assignment that makesF()=1

⇔G has a vertex cover of size

k

Construction ofG (F hasn variables and m clauses):

1. add vertices x_i⁺,x_i^-and the edge (x_i⁺,x_i^-) for each variable x_iin F 2. For each clauseC_j=(l_i1

∨l

_i2

∨l

_i3) in F, add vertices l_i1, l_i2, l_i3and

three edges (l_i1,l_i2), (l_i2,l_i3), (l_i3,l_i1)

3. add the edge (l_i1,x_i⁺) if the literal l_i1is x_i, or add (l_i1,x_i^-) if it is ￢x_i for each clause C_j

4. let k= n+2m

Fを1にする割当が存在する⇔Gがサイズkの頂点被覆を持つ

Gの構成は、与えられたF

から

F

のサイズに対する多項式時間

で可能 。したがって以下を示せばよい:

例:

F(x₁,x₂,x₃,x₄) = (x₁

∨x

₂

∨x

₃)∧(￢x₁

∨x

₃

∨x

₄)∧(x₁

∨￢x

₃

∨x

₄) x₁⁺ x₁^- x₂⁺ x₂^- x₃⁺ x₃^- x₄⁺ x₄^-

x₁ x₂ x₃

￢x

₁ x₃ x₄

x₁

￢x

₃ x₄

G k = 4+2×3=10

Gの構成から任意の頂点被覆Sは x_i⁺,x_i^-

のどちらかを含む

C_j

の3頂点中、最低2つ含む よって

|S| ≧n+2m= k

である。

観察:

5/11

It is easy to see that the construction of Gfrom F can be done in polynomial time of the size of F. Hence, we show that…

Ex: F(x₁,x₂,x₃,x₄) = (x₁

∨x

₂

∨x

₃)∧(￢x₁

∨x

₃

∨x

₄)∧(x₁

∨￢x

₃

∨x

₄) x₁⁺ x₁^- x₂⁺ x₂^- x₃⁺ x₃^- x₄⁺ x₄^-

x₁ x₂ x₃

￢x

₁ x₃ x₄

x₁

￢x

₃ x₄

G k = 4+2×3=10

From the construction of G, any vertex cover S should contain

at least one ofx_i⁺or x_i^- at least 2 of 3 vertices in C_j Hence we have |S| ≧n+2m= k.

Observation:

5/11

There is an assignment that makesF()=1

⇔G has a vertex cover of size

k

￢x

₁

Fを1にする割当が存在する⇒Gがサイズkの頂点被覆を持つ

例:

F(x₁,x₂,x₃,x₄) = (x₁

∨x

₂

∨x

₃)∧(￢x₁

∨x

₃

∨x

₄)∧(x₁

∨￢x

₃

∨x

₄) x₁⁺ x₁^- x₂⁺ x₂^- x₃⁺ x₃^- x₄⁺ x₄^-

x₁ x₂ x₃

￢x

₁ x₃ x₄

x₁

￢x

₃ x₄

G k = 4+2×3=10

1. それぞれの変数x_i

が

x_i=1ならx_i⁺

をSに入れる

x_i=0ならx_i^-

をSに入れる

2. それぞれの項C_j=(l_i1,l_i2,l_i3) は充足されているので、

最低1つのリテラル(l

_i1)については変数との間の辺(l_i1,x_i1)

は

x_i1

によって被覆されている。したがって、それ以外の 二つのリテラル(l

_i2,l_i3)をS

に入れる。

観察 より、Sはサイズkの頂点被覆になる。

⇒

6/11

Ex: F(x₁,x₂,x₃,x₄) = (x₁

∨x

₂

∨x

₃)∧(￢x₁

∨x

₃

∨x

₄)∧(x₁

∨￢x

₃

∨x

₄) x₁⁺ x₁^- x₂⁺ x₂^- x₃⁺ x₃^- x₄⁺ x₄^-

x₁ x₂ x₃

￢x

₁ x₃ x₄

x₁

￢x

₃ x₄

G k = 4+2×3=10

1. Put x_i⁺if x_i=1 into Sfor each x_i.

2. Since each clause C_j=(l_i1,l_i2,l_i3) is satisfied, at least one literal, say l_i1, the edge (l_i1,x_i1) is covered by the variable x_i1. Therefore, put the remaining literals (l_i2,l_i3) into S.

Observation, Sis a vertex cover of size k.

⇒

If there is an assignment that makesF()=1, 6/11 G has a vertex cover of sizek

x_i^-if x_i=0

From the

Gがサイズkの頂点被覆を持つ⇒Fを1にする割当が存在する

例:

F(x₁,x₂,x₃,x₄) = (x₁

∨x

₂

∨x

₃)∧(￢x₁

∨x

₃

∨x

₄)∧(x₁

∨￢x

₃

∨x

₄) x₁⁺ x₁^- x₂⁺ x₂^- x₃⁺ x₃^- x₄⁺ x₄^-

x₁ x₂ x₃

￢x

₁ x₃ x₄

x₁

￢x

₃ x₄

G k = 4+2×3=10

1.

2. さらに各変数x_i

についてはx

_i⁺

かx

_i^-

の一方しか、

各項C

_j

についてはちょうど2つの頂点しかSに含むことができない。

観察 より、被覆Sは項から2m個、変数からn個の頂点を含む。

⇒

x_i⁺

がSに含まれるなら

x_i=1

x_i^-

がSに含まれるなら

x_i=0

という割当はFを充足する。

3. よって各項C_j

はSに含まれないリテラルl

_i

を含むが、

これに付随する辺は他方が被覆されていなければならない。

QED.

7/11

Ex: F(x₁,x₂,x₃,x₄) = (x₁

∨x

₂

∨x

₃)∧(￢x₁

∨x

₃

∨x

₄)∧(x₁

∨￢x

₃

∨x

₄) x₁⁺ x₁^- x₂⁺ x₂^- x₃⁺ x₃^- x₄⁺ x₄^-

x₁ x₂ x₃

￢x

₁ x₃ x₄

x₁

￢x

₃ x₄

G k = 4+2×3=10

1. From Observation,

⇒

x_i=1 if x_i⁺in S

x_i=0 if x_i^-in S The following assignment satisfies F:

QED.

7/11 If G has a vertex cover of sizek, there is an assignment s.t.F()=1

a cover Scontains 2mvertices from the clauses, and nvertices from the variables.

3. Hence each clause C_jcontains exactly one literal l_iwhich is not in S, and hence incident edge should be covered by a variable vertex.

2. Thus the cover Scontains exactly one of x_i⁺and x_i^-and exactly two literals of a clause C_j.

￢x

₁

充足できない例:

F(x₁,x₂,x₃) = (x₁

∨x

₁

∨x

₁)∧(￢x₁

∨￢x

₂

∨￢x

₂)∧(x₂

∨x

₃

∨x

₃)

∧(￢x

₁

∨x

₂

∨￢x

₃)

x₁⁺ x₁^- x₂⁺ x₂^- x₃⁺ x₃^-

x₁

x₁ x₁

￢x

₁

￢x

₂

￢x

₂

x₂ x₃ x₃ G

k = 3+2×4=11 8/11

￢

x₁ x₂

￢x

₃

充足できないFでは、どのリテラルも頂点でカバーされていない 項が必ず存在する。この項のリテラルは3つとも

Vertex Cover に

入れざるを得ない。よって

Vertex Cover

のサイズは

k+1

以上になる。

Unsatisfiable example:

F(x₁,x₂,x₃) = (x₁

∨x

₁

∨x

₁)∧(￢x₁

∨￢x

₂

∨￢x

₂)∧(x₂

∨x

₃

∨x

₃)

∧(￢x

₁

∨x

₂

∨￢x

₃)

x₁⁺ x₁^- x₂⁺ x₂^- x₃⁺ x₃^-

x₁

x₁ x₁

￢x

₁

￢x

₂

￢x

₂

x₂ x₃ x₃ G

k = 3+2×4=11 8/11

￢

x₁ x₂

￢x

₃

When Fis unsatisfiable, it contains at least one clause such that each literal is not covered by a vertex. So, Vertex Cover should contain three literals in the clause. Hence any vertex cover has size at least k+1.

定理: 次数高々5の有向グラフ上の

DHAM はNP

完全問題

P

≤m

[証明] (上記の問題をDHAM_≦5

と略記する)

DHAM_≦5

がNPに属するのは、DHAMがNPに 属することから自明。したがって完全性を示せばよい。

DHAM DHAM_≦5

を示す。

次数: 頂点に付 随する辺の本数

v

v

アイデア:

次数14の頂点v(左)の

(入ってくる辺集合)と (出ていく辺集合)を右図

の`gadget’で置き換える 左図でvを1度だけ通る 閉路と右図でvを1度だ け通る閉路は対応する。

v

v

9/11

Theorem: DHAM on a directed graph with max. degree=5 (abb. DHAM_≦5) is NP-complete

P

≤m

[Proof]

Since DHAM ∈NP, DHAM_≦5

∈NP.

We DHAM DHAM_≦5.

degree: the number of edges incident to a vertex

v

v Idea:

Replace the set of “arcs to v”

and the set of “arcs from v”

by a right ‘gadget’.

A Hamiltonian cycle through v on the original graph corresponds to the Hamiltonian cycle through v on the resultant graph.

v

v

9/11

定理: 次数高々5の有向グラフ上の

DHAM はNP

完全問題

v d_i

個

d_o

個 アイデア:

[証明(概要)]

与えられたグラフGの次数が6以上のそれぞれの頂点に入る辺と 出る辺を上記の

gadget で置き換える。

v d_i

個

2 di

⎡ ⎤⎢ ⎥

⎢ ⎥個 1 2 2

di

⎡⎡ ⎤⎤

⎢⎢ ⎥⎢ ⎥⎥

⎢ ⎥個

2個

高さ: O(log

d_i)

個数: O(d

_i)

1.

元のグラフGがn頂点m辺であったなら、gadget で置き換えた あとのグラフG’は

O(n+m)頂点O(m)辺となる。したがって上

記の還元はGの大きさの多項式時間で可能。

2.

またG’のすべての頂点は次数はたかだか5である。

3. Gがハミルトン閉路をもつ⇔G’がハミルトン閉路を持つ QED.

10/11

ポイント:

•各閉路は上から下

•各頂点は次数≦5 v

d_i

d_o Idea:

[Proof (sketch)]

For each vertex vof degree≧6, replace the edges around v by the gadget.

v d_i

2 di

⎡ ⎤⎢ ⎥

⎢ ⎥ 1 2 2

di

⎡⎡ ⎤⎤

⎢⎢ ⎥⎢ ⎥⎥

⎢ ⎥

2

height: O(logd_i) number: O(d_i)

1. If the original graph Ghas nvertices with medges, the resultant graph G’contains O(n+m) vertices with O(m) edges.

Hence the reduction can be done in polynomial time of n& m.

2. Each vertex in G’has degree at most 5.

3. Ghas a Hamiltonian cycle ⇔G’has a Hamiltonian cycle. QED.

10/11 Theorem: DHAM on a directed graph with max. degree=5

(abb. DHAM_≦5) is NP-complete

Points:

•Up to down via cycle

•Each vertex has deg≦5

11/11

おまけ(Addition)

•Ryuhei Uehara, Shigeki Iwata:

Generalized Hi-Q is NP-complete,

The Transactions of the IEICE, E73, p.270-273, 1990.

•Peisen Zhang, Huitao Sheng, Ryuhei Uehara:

A Double Classification Tree Search Algorithm for Index SNP Selection, BMC Bioinformatics, 5:89, 2004.

•Sachio Teramoto, Erik D. Demaine, Ryuhei Uehara:

Voronoi Game on Graphs and Its Complexity,

2^ndIEEE Symp. on Computational Intelligence and Games, p.265-271, 2006.

•Ryuhei Uehara, Sachio Teramoto:

Computational Complexity of a Pop-up Book, 4^thInternational Conference on Origami in Science, Mathematics, and Education, 2006.

•Ryuhei Uehara:

Simple Geometrical Intersection Graphs, 3^rdWorkshop on Algorithms and Computation,

Lecture Notes in Computer Science, Vol. 4921, p.25-33, 2008.

多くの自然な問題は

•多項式時間で解けるか

•NP困難か

のどちらかである場合が多い(?)

残りの予定 (Schedule)

• 4/24 (Thu):

–

レポートの回収(report submission)

• 4/24 Office Hour:

–

レポートの解答と解説(Answers and comments

for the report)

• 4/28: 休講(Canceled)

• 5/1: 中間試験(Mid term exam) – 4題40点満点

–

持ち込み不可

(No text, No notes, …)