Treewidth of regular graphs

(1)

正則グラフの木幅について

Treewidth of regular graphs

数学専攻安部照章

Nobuaki ABE

1

^はじめに

グラフを対象としたアルゴリズムにおいて一度にすべてのグラフを対象として考えると

,

アルゴリズムによって必要な計算時間量の面で難しいことが多く

,

一般的には扱うグラフを制限する必要がある

.

そうした要素の

1

つとして

Robertson, Seymour

によって定義された

pathwidth

及び

treewidth

を用いてグラフを制限することにより良い結果が得られている

.

しかし

,

任意のグラフについてその

pathwidth, treewidth

を求めることもまた難しい問題であり

,

研究が行われている

.

本論文では代表的なグラフの分類の

1

つである正則グラフにおける

treewidth

について

, Fomin, Hoie [1]

によって得られた

3

正則グラフに対する結果をもとに

4

正則グラフの場合に拡張する方法について述べる

.

2 Graph

本論文の中で扱うグラフ及び

pathwidth, treewidth

の定義を述べる

.

定義

2.1.

グラフ

G

は

,

頂点の集合

V (G)

と

, V (G)

の

2

頂点を結ぶ辺の集合

E(G)

と

, G

上の各辺に対し

,

それらが結ぶ

2

頂点の組を与える

incidence function ψ

_G の組

G = ((V (G), E(G)), ψ

_G

)

と定義される

.

ただし

, incidence function

について明記する必要がない場合にはグラフ

G = (V (G), E(G))

と表す

.

次に

,

この論文で使用するグラフに関する用語を定義する

.

頂点と辺が結ばれているときそれらは互いに

, incident

しているという

.

辺に

incident

している頂点を

,

その辺の端点という

.

異なる頂点が同じ辺に

incident

しているとき

,

それらは隣接しているという

.

異なる辺が同じ頂点に

incident

しているとき

,

それらは隣接しているという

.

ある頂点

v

に隣接している頂点全体の集合を

N (v)

で表す

. 1

つの頂点に

incident

している辺の数をその頂点の次数といい

,

グラフ

G

における頂点の最大の次数を

G

の次数という

.

同じ頂点を結ぶ辺をループといい

,

同じ

2

頂点間を結ぶ異なる辺を多重辺という

.

グラフがループと多重辺を含まないとき単純であるといい

,

そのようなグラフを単純グラフという

.

任意の

2

頂点を結ぶ重複の無い頂点と辺の交互列を

path

といい

.

始点と終点が一致する

path

をサイクルという

.

任意の

2

頂点が

path

で結べるとき

,

そのグラフは連結であるという

.

サイクルを含まないグラフを

forest

といい

,

連結である

forest

を

tree

という

. | V (G) | , | E(G) |

が共に有限であるグラフを有限グラフという

. V

^′

⊆ V (G)

に対し

, V

^′の頂点を両端点にもつ

G

のすべての辺を辺集合にもつグラフを

V

^′によって誘導される

G

の誘導部分グラフといい

, G[V

^′

]

と表す

.

以後グラフ

G

は

,

有限かつ単純であるとする

.

次の定義は

Robertson, Seymour

による

.

1

(2)

定義

2.2. (Robertson, Seymour [3] )

G

の

path decomposition

とは

,

以下を満たす

V (G)

の部分集合の列

X

1

, · · · , X

rのことである

.

• ∪

(X

i

: i ∈ { 1, 2, . . . , r } ) = V (G).

•

^任意の

G

の辺に対し

,

その両端点を同時に含む

X

i

(1 ≤ i ≤ r)

が存在する

.

• 1 ≤ i ≤ j ≤ k ≤ r

であるとき

, X

i

∩ X

k

⊆ X

jが成り立つ

.

定義

2.3. (Robertson, Seymour [3] ) path decomposition

の

width

を

, max

1≤i≤r

( | X

_i

| − 1)

と定義し

,

G

の

pathwidth

を

, G

のもつすべての

path decomposition

の

width

の最小値と定義する

.

treewidth

は

pathwidth

と同じ様に定義され

, pathwidth

を拡張したものとなっている

.

定義

2.4. (Robertson, Seymour [4] )

G

の

tree decomposition

とは

,

以下の条件を満たす

V (G)

の部分集合の列

(X

i

: i ∈ I)

と

V (T ) = I

である

tree T

の組である

.

• ∪

(X

i

: i ∈ I) = V (G).

• G

の任意の辺に対し

,

両端点を同時に含む

X

i

(i ∈ I)

が存在する

.

• i, j, k ∈ I

に対し

, j

が

T

上

i, k

を結ぶ

path

上に存在するならば

, X

i

∩ X

k

⊆ X

j が成り立つ

.

定義

2.5. (Robertson, Seymour [4] ) tree decomposition

の

width

を

, max

i∈I

( | X

_i

| − 1)

と定義し

,

グラフ

G

の

treewidth

を

, G

のもつすべての

tree decomposition

の

width

の最小値と定義する

.

本論文では

, G

の

treewidth

を

tw(G), pathwidth

を

pw(G)

で表すこととする

.

これらの定義から次を導くことができる

.

定理

2.6.

任意のグラフ

G

に対して

, pw(G) ≥ tw(G)

が成り立つ

.

3

正則グラフの

treewidth

正則グラフに対して

treewidth

を与えるために

, Fomin, Hoie [1]

で得られた

3

正則グラフでの結果を拡張することを考える

.

定義

3.1.

全ての頂点の次数が等しいグラフを

,

正則グラフといい

,

次数

k

の正則グラフを

k

正則グラフという

.

グラフの次数と

pathwidth

に関して得られた結果が次の定理である

.

定理

3.2. (Fomin, Hoie [1])

G

を

3

正則グラフとする

.

任意の

ε > 0

に対し

,

整数

n

εが存在し

,

次を満たす

.

| V (G) | > n

εならば

, pw(G) ≤ (

¹₆

+ ε) | V (G) | .

この定理により

, 3

正則グラフの

pathwidth

および

treewidth

はその頂点数を用いて評価できるようになった

.

この定理の証明に使われた

path decomposition

の構成方法を利用して

,

ある仮定の下

4

正則グラフに対する証明を与える

.

2

(3)

考える命題は以下の通り

,

命題

3.3. G

を

| V (G) | = n

である次数が高々

4

のグラフとする

.

任意の空でない

X ⊆ V (G)

に対し

, X

を

tree

の

1

つの頂点として含む

tree decomposition

が存在し

,

その

width

が

n

の多項式で与えられるならば

,

任意の

4

正則グラフに対して

,

その

treewidth

が

n

の多項式で与えられる

.

加えて

,

次の定理を利用する

.

定理

3.4. (Monien, Preis [2])

G

を

4 .

任意の

ε > 0

に対し

,

整数

n

εが存在し

,

次を満たす

.

| V (G) | > n

εならば

,

エッジカットの数が高々

(

₂

5

+ ε )

| V (G) |

^であり

, || V

1

| − | V

2

|| ≤ 1

であるカット

(V

1

, V

2

)

が存在する

.

仮定によって得られた

tree decomposition

の

width

が

W (n)

であるとして

,

証明の概要を説明する

. tree decomposition

の構成法は以下の通り

.

ε > 0, G

を

| V (G) | = n

である

4 .

定理

3.4.

より

,

エッジカットの数が高々

(

₂

5

+ ε ) n

であるようなカット

(V

₁

, V

₂

)

をとる

. ∂(V

₁

)

で

V

₂の頂点と隣接している

V

₁の頂点の集合を

, ∂(V

₂

)

で

V

₁の頂点と隣接している

V

2の頂点の集合を表すとする

.

ここで

, i = 1, 2

に対して

, | ∂(V

i

) | ≤ (

²₅

+ ε)n

である

.

仮定を

, G[V

1

]

に対し

, X = ∂(V

1

)

として

, G[V

2

]

に対し

, X = ∂(V

2

)

として適応すると

, G[V

1

]

と

G[V

2

]

の

tree decomposition T

1

, T

2がそれぞれ得られる

. width

はともに高々

W ( ⌈

_n

2

⌉ )

である

.

ここで

, G[∂(V

1

) ∪ ∂(V

2

)]

の

path decomposition P = (X

1

, X

2

, . . . , X

r

)

で

X

1

= ∂(V

1

), X

r

= ∂(V

2

)

となるようなものが得られれば

, T

1

, T

2

, P

を用いて

G

の

tree decomposition

を構成することができる

.

P = (X

1

, X

2

, . . . , X

r

)

を以下のように構成する

.

X

1

= ∂(V

1

)

とする

.

奇数の

j ≥ 1

に対して

, v ∈ X

j

\ ∂(V

2

)

を選び

, X

j+1

= X

j

∪ (N (v) ∩ ∂(V

2

))

とし

, X

_j+2

= X

_j+1

\ { v }

^とする

.

繰り返しにより

, j

が奇数のとき

X

_jから

∂(V

₁

)

の頂点が除かれ

, j

が偶数のとき

X

_jに

, ∂(V

₂

)

の頂点が追加され

,

最終的に

X

_r

= ∂(V

₂

)

となったときに完成する

.

この構成法により

P

は

path decompositon

になることがわかる

.

最後に

, P

の

width

を評価する

.

D

m

(m = 1, 2, 3, 4)

を

∂(V

2

)

に

m

個隣接する点を持つ

∂(V

1

)

の点とする

.

このとき

,

| X

1

| = | ∂(V

1

) | = | D

1

| + | D

2

| + | D

3

| + | D

4

|

3

(4)

であり

,

| D

₁

| + 2 · | D

₂

| + 3 · | D

₃

| + 4 · | D

₄

| ≤ ( 2

5 + ε )

n

である

.

よって

,

| X

₁

| ≤ ( 2

5 + ε )

n − | D

₂

| − 2 · | D

₃

| − 3 · | D

₄

|

である

.

ここで

,

各

j

に対し

D

^′₂

= X

_j

∩ D

₂

, D

₃^′

= X

_j

∩ D

₃

, D

₄^′

= X

_j

∩ D

₄ とする

.

このとき

, j ≥ 3

に対して

, X

_j には

D

_ℓの頂点が選ばれた時には

ℓ

個

(1 ≤ ℓ ≤ 4)

の頂点が追加され

,

次には

1

つ取り除かれるという操作が繰り返されることから

,

| X

_j

| ≤ | X

₁

| + | D

₂

\ D

₂^′

| + 2 · | D

₃

\ D

₃^′

| + 3 · | D

₄

\ D

₄^′

| + 1

≤ ( 2

5 + ε )

n − ( | D

₂

| − | D

₂

\ D

^′₂

| ) − 2 · ( | D

₃

| − | D

₃

\ D

₃^′

| ) − 3 · ( | D

₄

| − | D

₄

\ D

^′₄

| ) + 1

≤ ( 2

5 + ε )

n + 1

よって

, P

の

width

は高々

(

₂

5

+ ε )

n

であることが示された

.

以上により

, T

1

, T

2

, P

を組み合わせることで構成される

G

全体の

tree decomposition

の

width

は高々

max { (

₂

5

+ ε )

n, W(

ⁿ₂

) }

^{であることが示された}

.

4

今後の課題

命題における

tree decomposition

を求めること自体は自明なものを含めれば難しいものではなく

,

問題となるのはその

width

を

n

の式で与えるというところになる

.

そのために

,

次数による制限だけでなく他の条件に結び付けて関係式を求めていく必要があり

,

今回は証明に至らなかった

.

加えて

,

この証明法において

,

カットによる分割を作る際のエッジカットの数が評価式の上限の

1

つになっているが

, 4

正則で得られている結果が頂点数

n

に対して

(

₂

5

+ ε )

n

であることから

,

これ以上の次数における結果を予想すると ⁿ₂ を超えることが考えられる

.

このとき

,

分割したグラフの

tree decomposition

を考えずとも

2

分割した頂点集合をそのまま用いて

treewidth

は高々エッジカットの数という結果が得られる

.

この方法ではそれ以上に

width

を小さくすることができないため

,

より高い次数に対して証明をする際には根本的に別の方法を考える必要があるだろう

.

参考文献

[1] Fedor V. Fomin, Kjartan Hoie, Pathwidth of cubic graphs and exact algorithms, Infomation Proceccing Letters 97 (2006) 191-196.

[2] B. Monien, R. Preis, Upper bounds on the bisection width of 3- and 4-regular graphs, in: Proc. 26th Internat. Symp. on Mathematical Foundations of Computer Science (MFCS 2001), in: Lecture Notes in Comput. Sci., vol. 2136, Springer, Berlin, 2001, pp. 524-536.

[3] N. Robertson, P. D. Seymour, Graph minors. I. Excluding a forest, Journal of Combinational.Theory Series B 35 (1983), 39-61.

[4] N. Robertson, P. D. Seymour, Graph minors. II. Algorithmic Aspects of Tree-width, Journal of Algorithms 7, (1986), 309-322.

4