多項式個の極小セパレータを持つグラフクラスについて (理論計算機科学

多項式個の極小セパレータを持つグラフクラスについて
On graph classes with polynomial number of minimal separators
長澤亮介 (Ryosuke Nagasawa) ∗
加藤達也 (Tatsuya Kato) ∗
木野徹 (Toru Kino) ∗
山崎浩一 (Koichi Yamazaki)∗ †
2 諸定義
1 はじめに
本稿では, 多項式個の極小セパレータを持つグラ
G をグラフとする. このとき V (G), E(G) でそれ
フクラスについて研究を行う. そのようなグラフク
ぞれ G の頂点集合, 辺集合を表す. (G の) 頂点 v と
ラスに対しては, 木幅や最小充填問題などのいくつ
隣接する頂点の集合を NG (v) または単に N(v) と表
かの問題が多項式時間で解けることもあり, 古くか
す. 部分集合 U ⊆ V (G) に対して, U より誘導され
ら研究されている.
る G の部分グラフを G[U] と表す.
よく知られた結果として, 置換グラフからなるグ
S を G の頂点部分集合とする. 隣接していない 2
ラフクラスは多項式個の極小セパレータを持つこと
頂点 a と b に対して, S が a, b-セパレータであると
が知られている [1]. この結果はさらに拡張されて
は, S を取り除いた時に a と b が異なるコンポーネ
おり, 次元がバウンドされた台形グラフからなるグ
ントに属するときをいう. もし S の真部分集合に a,
ラフクラス [2] や弱コーダルグラフからなるグラフ
b-セパレータが存在しないならば, S は極小 a, b-セ
クラス [3] が多項式個の極小セパレータを持つこと
パレータと呼ばれる. S が極小セパレータとは, 隣接
が知られている.
していないある 2 頂点 a と b が存在し, S が極小 a,
b-セパレータであるときをいう. |sep(G)| で, G の極
置換グラフに対する結果の別の拡張としては, 置
換グラフを真に含む, AT-free ∩ co-AT-free グラフ
小セパレータ全体からなる集合を表す.
からなるグラフクラスも, 多項式個の極小セパレー
S をグラフ G の極小セパレータとする. G\S に
タを持つことが知られている [5]. さらにこの結果
おけるコンポーネントの集合を CG (S) と表す. コン
は拡張され, グラフ自身とその補グラフの asteroidal
ポーネント C ∈CG (S) が (S に対して) フルコンポー
number がともにバウンドされているグラフからな
ネントであるとは, S ⊆ N(C) を満たすときをいう.
極小セパレータとフルコンポーネントの関係とし
るグラフクラスもやはり多項式個の極小セパレータ
を持つことが知られている [5].
て次の定理が知られている.
本稿では, 文献 [5] で使われている技法を基に, グ
定理 1. [4] S が G の極小セパレータである必要十
ラフクラスが多項式個の極小セパレータを持つため
分条件は, CG (S) が少なくとも 2 つの (S に対する)
の必要または十分な構造が何であるかを研究する.
フルコンポーネントを持つことである.
得られた結果としては, 先ず強 X-type と弱 X-type
P = {p1 , . . . , pk } ⊂ V (G) とする. P が U ⊂ V (G)
という構造を定義し, それらを用いて必要および十
を配偶者被覆するとは, 次を満たすときをいう:
分条件を与える.
• U ⊆ N(P) かつ
• 以下を満たす {u1 , . . . , uk } ⊆ U が存在する:
∗
群馬大学 (Gunma University)
† 本研究は JSPS 科研費 24500007 の助成を受けたもので
す。
– {{pi , ui }|1 ≤ i ≤ k} ∈ E(G) かつ
1
SX2 = (A2 , B2 , Γ2 , ∆2 ) が存在する:
– {{pi , u j }|i ̸= j} ̸∈ E(G).
P において, ui を pi の (また pi を ui の) 配偶者と呼
• SX1 ̸= SX2 かつ
ぶ. U ⊆ N(P) を満たす極小な P は, U を配偶者被覆
• SX1 も SX2 も G の強 X-type かつ
することに注意.
• qsxord(SX1 ) ̸= qsxord(SX2 ).
u1 U
P 1 p1
G の強 X-type の集合を Xs (G) と表し,
max qsxord(SX) を G の強 X-type オーダーと
u8
p2
SX∈Xs (G)
呼び, sxord (G) と表す.
u2
p3
u5
p4
u4
P 2 p5
A
u3
p6
u7
p7
u6
図 1 配偶者被覆
B
β1
β2
β3
β4
β5
Γ
γ1
γ2
γ3
γ4
γ5
図 1 では, P = {p1 , p2 , p3 , p4 } が U = {u1 , . . . , u8 }
を配偶者被覆しており, p1 , p2 , p3 , p4 の配偶者
はそれぞれ u1 , u2 , u3 , u4 ととれる.
Δ
また, P =
{p5 , p6 , p7 } が U = {u1 , . . . , u8 } を配偶者被覆して
図2
おり, p5 , p6 , p7 の配偶者はそれぞれ u5 , u6 , u7 と取
オーダーが 5 の強 X-type.
れる.
2.1
グラフ G のある誘導部分グラフ G′ = G[U] が (G
強 X-type と弱 X-type
4 つ組み SX = (A, B, Γ , ∆ ) がグラフ G の強 X-
において) 弱 X-type（図 3 参照）であるとは, 強
type（図 2 参照）であるとは, 以下を満たすように
X-type での C1 と C2 を満たすように U を A, B,
V (G) を A, B, Γ , および ∆ の 4 つに分割できるとき
および Γ の 3 つに分割できるときをいう. 強オー
ダーと同様に, |B|(= |Γ |) を G′ の弱オーダーと呼
をいう:
び, lwxordG (G′ ) と表す. また, G において弱 X-type
C1. ある自然数 k が存在し, B = {β1 , β2 , . . . , βk },
である (G の) 誘導部分グラフの集合を Xw (G) と
Γ = {γ1 , γ2 , . . . , γk } と表せ, 以下を満たす:
表し,
• {{βi , γi }|1 ≤ i ≤ k} ⊆ E(G) かつ
max lwxordG (G′ ), を G の弱 X-type オー
G′ ∈Xw (G)
ダーと呼び, wxord (G) と表す.
• {{βi , γ j }|i ̸= j} ∩ E(G) = 0.
/
C2. ある部分集合 A′ ⊆ A が存在し, B の任意の部分
3 結果
集合 B′ に対し G[(A′ ∪ B)\B′ ] が連結となる.
3.1
C3. ある部分集合 ∆ ′ ⊆ ∆ が存在し, Γ の任意の部
Good なグラフクラス
グラフクラス G が Good であるとは, 任意のグラ
分集合 Γ ′ に対し G[(∆ ′ ∪ Γ )\Γ ′ ] が連結となる.
フ G ∈ G に対し wxord(G) ≤ c を満たすある定数 c
C4. N(A) ∩ (Γ ∪ ∆ ) = 0/ かつ N(∆ ) ∩ (A ∪ B) = 0/ で
が存在するときをいう.
ある.
G が多項式個の極小セパレータを持つとは, ある
上記の k を SX の強オーダーと呼び, qsxord (SX)
多項式 P と定数 n0 が存在し, |V (G)| ≥ n0 なる任意
と表す. 一般に, 以下を満たす SX1 = (A1 , B1 , Γ1 , ∆1 ),
の G に対して |sep(G)| ≤ P(|V (G)|) が成り立つと
2
意すると, S′ に属する任意の 2 頂点 x, y ∈ S′ に対し,
A
{x, x′ } ∈ E(G), {y, y′ } ∈ E(G) なる頂点 x′ , y′ ∈ C1 が
存在する (x′ = y′ であるかもしれない). C1 の連結性
B
β1
β2
β3
β4
より, x′ と y′ を結すぶ C1 内のパスが存在するので,
β5
x と y は {x, y} ∪C1 で連結である. 従って弱 X-type
での条件 C2 を満たす.
Γ
γ1
γ2
γ3
γ4
結局, (A, B, Γ ) はオーダー ℓ > k の弱 X-type とな
γ5
り矛盾. 従って任意の極小セパレータ S に対して極
小な配偶者被覆のサイズは高々 k である.
図 3 オーダーが 5 の弱 X-type.
G
きをいう.
C1=A
補題 3.1. C を S に対するフルコンポーネントと
する. このとき S に対して配偶者被覆するような
N1
N ⊆ C が少なくともひとつ存在する.
証明. C は S に対するフルコンポーネントより, S ⊆
S
N(C) を満たす. よって S ⊆ N(N) を満たす極小の
S'=B β
1
β2
β3
γ2
γ3
N ⊆ C を考えることができ, そのような N は S を配
偶者被覆する.
N2=Γ γ
1
補題 3.2. グラフ G が wxord(G) ≤ k を満たすなら,
C2
G の任意の極小セパレータ S に対して, S の配偶者
被覆のサイズは高々 k である.
証明. S を G の任意の極小セパレータとし C1 , C2
を G\S のフルコンポーネントとする. N1 ⊆ C1 ,
図 4 補題 3.2 での A, A′ , B, Γ の取り方.
N2 ⊆ C2 を S を配偶者被覆する頂点集合とする (補
題 3.1 より N1 , N2 が存在する). 一般性を失うこと
以下の補題 3.3, 3.4 から定理 2 が成り立つ.
なく |N2 | ≥ |N1 | と仮定できる. ここで N2 のサイズ
を ℓ で表し, |N2 | = ℓ > k を仮定し, N2 = {γ1 , . . . , γℓ }
と表す. また各頂点 γi の配偶者を βi で表し,
S′
補題 3.3. グラフ G の任意の極小セパレータ S に対
し, N(N1 ) ∩ N(N2 ) = S なる S の配偶者被覆のペア
=
{β1 , . . . , βℓ }(⊆ S) と表す.
ここで, A および
A′
として C1 を, B として
N1 , N2 が存在する.
S′
を,
証明. S が極小セパレータより, G\S のフルコンポー
Γ として N2 を取ることにする. このように取るこ
ネント C1 , C2 が存在する. C1 , C2 が S のフルコン
とで, (A, B, Γ ) が弱 X-type での条件 C1,C2 を満た
ポーネントより, S の配偶者被覆のペア N1 ⊆ C1 ,
すことを以下に示す.
N2 ⊆ C2 が存在する. このとき, N(C1 ) ∩ N(C2 ) =
N2 は S′ を配偶者被覆しているため, 条件 C1 を満
S, N1 ⊆ C1 , N2 ⊆ C2 , S ⊆ N(N1 ), S ⊆ N(N2 ) より,
たすことは明らか. C1 は S に対してフルコンポーネ
N(N1 ) ∩ N(N2 ) = S が成り立つ.
ントであるため, C1 = A が S に対するフルコンポー
ネントであることより, 任意の v ∈ S に対し v と隣接
極小セパレータ S に対して, 補題 3.3 のような S
しかつ C1 に属する頂点が存在する. このことに注
の配偶者被覆のペア (N1 , N2 ) を S を特定する配偶
3
者被覆ペアと呼び, max{|N1 |, |N2 |} をそのペアのサ
3.2
Bad なグラフクラス
グラフクラス G が Bad であるとは, 以下を満た
イズと呼ぶ.
すある定数 c が存在するときをいう: ∀n0 , ∃G ∈ G
次の補題と本質的に同じ結果が文献 [5] で示され
s.t. [|V (G)| ≥ n0 ∧ sxord(G) ≥
ている.
|V (G)|
c ].
G が指数個
の極小セパレータを持つとは, ある指数関数 f が存
補題 3.4. G を以下を満たすグラフの集合とする. す
在し, 与えられた任意の n0 に対し, G ∈ G が存在し,
なわち, ある定数 k が存在し, 任意の G ∈ G に対す
|V (G)| ≥ n0 かつ |sep(G)| ≥ f (|V (G)|) であるとき
る任意の極小セパレータ S に対して, S を特定する
をいう.
サイズが高々 k の配偶者被覆ペアが存在する. この
補題 3.5. (A, B, Γ , ∆ ) を G の強 X-type とする. この
とき, G は多項式個のセパレータを持つ.
とき任意の B′ ⊂ B に対して, B′ ∪ B′ は G の極小セ
証明. 任意の G ∈ G に対し, G の極小セパレータの
パレータである. ここで, B′ は Γ \N(B′ ) を表す.
個数が O(|V (G)|2k ) であることを示す.
高々 k 頂点から成る G の頂点部分集合の族を UG
証明. 最初に B′ ∪ B′ が G のセパレータであること
で表す, すなわち UG = {U | U ⊆ V (G), |U| ≤ k}. UG
を示す. x ∈ A ∪ (B\B′ ), y ∈ ∆ ∪ (Γ \B′ ) とし, x, y に
の要素のペアから成る集合 {(U1 ,U2 ) | U1 ,U2 ∈ UG }
関する場合分けにより, A ∪ (B\B′ ) と ∆ ∪ (Γ \B′ ) の
を PG で表す. ここで |PG | が O(|V (G)|2k ) である
間に辺は存在しないことがいえる. また, A ∪ (B\B′ ),
ことに注意.
∆ ∪ (Γ \B′ ), B′ ∪ B′ 以外の G の頂点は存在しない.
したがって B′ ∪ B′ は G のセパレータである.
定理の仮定より, 任意の G ∈ G の任意の極小セ
強 X-type の定義から, 以下を満たす A′ ⊆ A, ∆ ′ ⊆
パレータ S に対して, S のサイズが高々 k である
∆ が存在する:
配偶者被覆のペア N1 , N2 を割り当てることができ
る. このときペア (N1 , N2 ) は PG に属する. した
• ∀B′ ⊂ B, G[A′ ∪ B′ ](よって G[A′ ∪ (B\B′ )]) が
がって, 次を満たす sep(G) から PG への写像 fG が
連結,
存在する, すなわち G の極小セパレータ S に対し,
• ∀B′ ⊂ Γ , G[∆ ′ ∪ B′ ] (よって G[∆ ′ ∪ (Γ \Γ ′ )]) が
fG (S) ∈ PG は S を特定する (サイズが高々 k であ
連結.
る) 配偶者被覆のペア.
fG は単射である. 何故ならば, S ̸= S′ なる S, S′ ∈
したがって G[V (G)\(B′ ∪ B′ )] に A′ ∪ (B\B′ ) を含
sep(G) に対し fG (S) = fG (S′ ) = (N1 , N2 ) とすると,
む連結成分が存在し, 同様に ∆ ′ ∪ (Γ \B′ ) を含む連
S = N(N1 ) ∩ N(N2 ) = S′ となり矛盾. fG が単射であ
結成分も存在する. それらをそれぞれ CA′ ∪(B\B′ ) ,
ることから |sep(G)| が
C∆ ′ ∪(Γ \B′ ) と表す. ここまでで, B′ ∪ B′ が CA′ ∪(B\B′ )
O(|V (G)|2k )
であることが
いえた.
と C∆ ′ ∪(Γ \B′ ) をセパレートすることがいえた.
次に B′ ∪ B′ が極小であることを示す. 定理 1 よ
定理 2. G が Good ならば G は多項式個のセパレー
タを持つ.
り, コンポーネント CA′ ∪(B\B′ ) と C∆ ′ ∪(Γ \B′ ) が B′ ∪ B′
証明. G が Good より, ∃c s.t. ∀G ∈ G , wxord(G) ≤ c
こでは, (B′ ∪ B′ ) ⊆ N(A′ ∪ (B\B′ )) であることをい
が成り立つ. したがって補題 3.2 より, 任意の G ∈ G
うために, B′ ⊆ N(A′ ∪ (B\B′ )) および B′ ⊆ N(A′ ∪
の任意の極小セパレータ S に対して, S を特定する
(B\B′ )) の 2 つを示す. (N(∆ ′ ∪ (Γ \B′ ) に関しては
サイズが高々 c の配偶者被覆が存在する. よって補
同様に証明できるので省略).
に対してフルコンポーネントであることを示す. こ
B′ に属する頂点に CA′ ∪(B\B′ ) と隣接していないあ
題 3.4 の条件が成立し, G が多項式個のセパレータ
る頂点 x が存在したと仮定する. ここで y を B\B′ の
を持つことがいえる.
任意の頂点とし (B′ ⊂ B より, B\B′ ̸= 0),
/ B′′ を x の
B 内の隣接頂点の集合 N(x) ∩ B とする. このとき,
4
y ̸∈ N(x) より x, y ̸∈ B′′ に注意すると, x, y ∈ (B\B′′ ).
参考文献
よって x, y ∈ A′ ∪ (B\B′′ ). 一方, x は G[A′ ∪ (B\B′′ )]
で孤立点となり, 連結性に矛盾.
B′
[1] H. L. Bodlaender, T Kloks, and D Kratsch.
B\B′
の頂点と隣
Treewidth and pathwidth of permutation graphs.
B′ ∪ B′
は極小セパ
SIAM Journal on Discrete Mathematics, Vol. 8,
の各頂点は配偶者関係より
接している. よって定理 1 より,
レータである.
No. 4, pp. 606–616, 1995.
[2] H. L. Bodlaender, T. Kloks, D. Kratsch, and
H. M¨uller. Treewidth and minimum fill-in on dtrapezoid graphs. Journal of Graph Algorithms
and Applications, Vol. 2, No. 5, pp. 1–23, 1998.
A
[3] V. Bouchitt´e and I. Todinca. Treewidth and min-
A'
imum fill-in: Grouping the minimal separators.
A'∪(B \ B')　B''
B
y
SIAM Journal on Computing, Vol. 31, No. 1, pp.
212–232, 2001.
x B'
[4] M.C. Golumbic. Algorithmic Graph Theory and
Perfect Graphs. Elsevier, 1980.
Γ
B'
[5] E. G. K¨ohler.
triples. Ph.D. dissertation, Technischen Univer-
Δ'∪(Γ \ B')　sit¨at Berlin, 1999.
Δ'
Δ
図5
セパレートされる A ∪ (B\B′ ) と ∆ ∪ (Γ \B′ )
定理 3. G が Bad ならば, G は指数個の極小セパ
レータを持つ.
証明. G が Bad であることからある定数 c が存在
し, 任意の n0 に対して |V (G)| ≥ n0 となり, かつ
sxord(G) ≥
|V (G)|
c
Graphs without asteroidal
であるような G ∈ G が存在する.
したがって, sxord(G) ≥
|V (G)|
c
を満たす G の強 X-
type (A, B, Γ , ∆ ) が存在する.
本定理を証明するには, |sep(G)| ≥ 2sxord(G) − 2 で
あることを示せれば十分である. 任意の B′ ⊂ B に対
して Γ \N(B′ ) を B′ と表す. 補題 3.5 より, G におい
て B′ ∪ B′ は極小セパレータである. B′ のとり方は
2sxord(G) − 2 通りあり, ∀B′1 , B′2 ⊂ B に対して B′1 ̸= B′2
ならば B′1 ∪ B′ 1 ̸= B′2 ∪ B′ 2 であるから, 極小セパ
レータとして取り得る組み合わせは 2sxord(G) − 2 通
りとなる. 従って |sep(G)| ≥ 2sxord(G) − 2 であるこ
とが言え, G の極小セパレータの個数が指数関数
2sxord(G) − 2 以上であることが示せた.
5

Download Report