近準完全有向グラフに対するパス幅の FPT アルゴリズム
橘内謙太
明治大学大学院
理工学研究科基礎理工学専攻情報科学系
計算理論研究室
2015 年 2 月 14 日
概要
有向グラフ G は，その各頂点 u が「辺 (u, v) も辺 (v, u) も存在しないような頂点 v ̸= u の個数
は高々 h である」という性質を満たすとき，h 準完全であるという．0 準完全な有向グラフは準完
全有向グラフとして知られ，トーナメントはその特別な場合である．準完全有向グラフに対して
は，Pilipczuk によって FPT アルゴリズムが考案されている．
本研究では n 頂点の h 準完全有向グラフ G と正整数 k が与えられたとき，G のパス幅が k 以下
であるかを判定する (h + 2k + 1)2k nO(1) 時間のアルゴリズムを考案した．この結果は，Pilipczuk
の準完全有向グラフに対する結果よりも k に対する依存度が小さく，かつより一般的である．この
結果を導くために，一般の有向グラフに対する玉木の XP アルゴリズムを変形し，「U を入次数が
k 以下であるような任意の頂点集合とするとき，U ∪ {v} の入次数が k 以下であるような頂点 v の
個数は高々 b である」という性質を満たす有向グラフに対してその実行時間が b2k nO(1) であるこ
とを示す．
準完全グラフに対しての Pilipczuk のアルゴリズムと我々のアルゴリズムの比較実験の結果，
Pilipczuk のアルゴリズムよりも，我々のアルゴリズムのほうがより高速に動作することが確認で
きた．
本稿では，Pilipczuk の準完全有向グラフに対する FPT アルゴリズムの概要の説明および実装
実験，我々が考案した h 準完全有向グラフに対する FPT アルゴリズムの詳細な説明および実装実
験，加えてこの二つのアルゴリズムに対する比較実験について記述する．
1
目次
第1章
はじめに
3
第2章
諸定義
5
第3章
準完全グラフのパス幅を求める FPT アルゴリズム
7
3.1
諸定義 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
3.2
障害 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
3.3
補題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
3.4
アルゴリズム . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
第4章
h 準完全グラフのパス幅を求める FPT アルゴリズム
12
4.1
諸定義 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
4.2
補題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
4.3
アルゴリズム . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
4.4
正しさの証明 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
4.5
実行時間の解析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
4.6
実装上の工夫 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
実装，実験
23
5.1
実験で使用するテストデータについて . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
5.2
[実験 1]3 章のアルゴリズムの実装実験 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
5.3
[実験 2]4 章のアルゴリズムの実装実験 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
5.4
[実験 3]3 章のアルゴリズムと 4 章のアルゴリズムの比較実験
48
第5章
第6章
. . . . . . . . . . . . . . . . .
むすびに
52
6.1
まとめ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
6.2
課題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
謝辞
53
参考文献
54
付録 A
実験データ (一部抜粋)
55
2
第1章
はじめに
無向グラフのパス幅（pathwidth）[2, 12] の概念は，Robertson と Seymour によるグラフマイナー理論 [12]
の中で，重要な役割を果たすだけでなく，グラフアルゴリズムの世界でも重要なグラフパラメータとして認識
されている．例えば，グラフのパス幅（さらに一般的には，グラフの木幅）が定数であるとき，多くの NP 困
難なグラフ上の問題は多項式時間で解くことができることが知られている [1, 2]．しかしながら，パス幅を決
定する問題は NP 完全であることが知られている [7]．
このような背景の中で，パラメータ化計算量理論の世界でもパス幅決定アルゴリズムの研究は行われてい
る．ある問題が固定パラメータ容易（fixed parameter tractable）であるとは，その問題のインスタンス I と
パラメータ k が与えられたとき，その問題を解く f (k)|I|O(1) 時間アルゴリズムが存在することである．ここ
で，f は計算可能関数であり，|I| はインスタンスのサイズであるとする．また，そのような実行時間のアル
ゴリズムを固定パラメータアルゴリズム（fixed parameter algorithm）と呼ぶ．グラフのパス幅がパラメータ
以下であることを判定する問題は，パス幅がマイナー操作に関して単調であるため，固定パラメータ容易であ
る [13, 14]．Bodlaender と Kloks は，その問題に対してグラフのサイズに対して線形時間で動作する固定パ
ラメータアルゴリズムを与えた [2, 3]．
その一方で，有向グラフのパス幅を求めるアルゴリズムの研究も行われている．有向グラフのパス幅の概
念は以下の理由により，無向グラフのパス幅の概念を一般化していると言える．無向グラフ G の各無向辺
{u, v} を，２つの有向辺 (u, v), (v, u) に置き換えて得られる有向グラフを G′ とするとき，G のパス幅と G′
のパス幅は一致する [9]*1 ．これにより，有向グラフのパス幅を決定する問題も同様に NP 完全であることが
わかる．有向グラフのパス幅は，その無向基礎グラフ（辺の向きを無視し，多重辺を取り除いてできる無向グ
ラフ）のパス幅とは一般的には一致しないことに注意する．特に，有向無閉路グラフのパス幅は 0 であるのに
対し，その無向基礎グラフの（無向グラフの）パス幅は任意に大きくなる．
無向グラフのパス幅が，あるパラメータ以下であるかを判定する問題が固定パラメータ容易であるのに対
し，有向グラフでの同様の問題が固定パラメータ容易であるかは未解決問題である．その一方で，nO(k) 時間
アルゴリズムが知られている [15, 10]．ここで，n は入力されるグラフの頂点数，k はパラメータとする．
無向グラフに対するグラフマイナー理論と類似の成功を得ることの可能な有向グラフのクラスの探求とい
う文脈のなかで，Formin，Kim，Pilipczuk，Seymour[8, 6] および Chudnovsky，Fradkin，Seymour[4, 5]
はトーナメントや準完全有向グラフ（semi-complete digraph）に対するパス幅やカット幅に対する固定パラ
メータアルゴリズムを与えた．準完全有向グラフとは，無向基礎グラフが完全グラフであるような有向グラフ
*1
ただし，無向グラフのパス幅の定義と有向グラフでの定義はわずかに異なる．
3
のことを言う．これらの幅パラメータは，グラフマイナー理論によって得られた結果を，それらのグラフクラ
スに適用するために重要な役割を果たしている．上述のアルゴリズムが構成的ではないのに対し，Pilipczuk
は構成的な固定パラメータアルゴリズムを与えた [11]．Pilipczuk のアルゴリズムは，n 頂点の準完全有向グ
ラフと整数 k が与えられたとき，そのグラフのパス幅が k 以下であるかを O(2O(k log k) n2 ) 時間で判定する．
我々は，この結果を次のように一般化する．
非負整数 h に対して，有向グラフ G = (V, E) が h 準完全であるとは，その無向基礎グラフの最小次数が
|V | − h − 1 以上であることを言う．0 準完全性は準完全性と一致し，準完全有向グラフは任意の h ≥ 0 に対
して h 準完全である．
定理 1. h 準完全有向グラフ G と正整数 k が与えられたとき，G のパス幅が k 以下であるかを判定する
(h + 2k + 1)2k nO(1) 時間アルゴリズムが存在する．つまり，h + k をパラメータとしたとき，この問題は固定
パラメータ容易である．
この結果は，次に定義する (k, b) 有界な有向グラフに対するより一般的な結果の帰結である．有向グラフ G
と頂点集合 U ⊆ V (G) に対して，U の G における入次数 d− G (U )（出次数 d+ G (U )）を，v ∈ V (G) \ U で v
から U に入る（U から v に出る）辺が存在するようなものの個数とする．正整数 k, b に対して G が (k, b) 有
界であるとは，d− (U ) ≤ k を満たすような各 U ⊆ V に対して，d− (U ∪ {v}) ≤ k を満たすような v ∈ V \ U
が高々 b 個であり，かつ d+ (U ) ≤ k を満たすような各 U ⊆ V に対して，d+ (U ∪ {v}) ≤ k を満たすような
v ∈ V \ U が高々 b 個であることを言う．
定理 2. 正整数 k と (k, b) 有界な有向グラフ G が与えられたとき，G のパス幅が k 以下であるかを判定する
b2k nO(1) 時間アルゴリズムが存在する．
h 準完全有向グラフは (k, h + 2k + 1) 有界であるので（補題 1 参照），定理 1 は定理 2 の直接の帰結である．
我々のアルゴリズムは，Nagamochi [10] による劣モジュラシステムにおける線形配置問題に対するアルゴ
リズムに基づいている．彼は，n 頂点有向グラフのパス幅が k 以下であるかを判定する問題に対して彼のアル
ゴリズムを適用した場合の計算時間が，n2k+O(1) であることを示した．(k, b) 有界な有向グラフに彼のアル
ゴリズムを適用すると，(k, b) 有界性のうち入次数に関する条件のみを活用することができて，計算時間の上
界を bk nk+O(1) に改良することができる．我々は，彼のアルゴリズムをパス幅計算に特化し，(k, b) 有界性に
おける入次数と出次数の両方の条件を活用できるようなアルゴリズムを設計することにより，上述の結果を
導く．
我々のアルゴリズムは Pilipczuk [11] の導入した分離鎖（separation chain）の（一般化した）概念を利用
し，h 準完全グラフの (k, h + 2k + 1) 有界性の証明に彼の用いた議論を用いるが，アルゴリズム自体は彼のア
ルゴリズムとは全く異なる原理に基づいている．実際，彼のアルゴリズムが準完全グラフの多くの性質に依存
し，準完全グラフに対してのみ動作可能であるのに対して，我々のアルゴリズムは，一般の有向グラフに対し
て動作する：(k, b) 有界性は実行時間の解析でのみ使用される．
本稿の構成を以下に記す．2 章では本稿全体で使用する定義と基礎的な事実を与える．3 章では，Pilipczuk
の考案したアルゴリズム [11] の簡単な説明を与える．4 章では我々が考案したアルゴリズムで用いる定義と基
礎的な事実を与え，また主定理のためのアルゴリズム，その正しさ，およびその実行時間の解析について述べ
る．4 章の内容は，学習院大学の小林靖明氏との共同研究である．5 章では，3 章，4 章で説明したアルゴリズ
ムについての実装実験，およびその結果の考察を与える．
4
第2章
諸定義
G = (V, E) を頂点集合が V ，辺集合が E であるような有向グラフとし，n = |V | とする．本稿での有向グラ
フは単純，つまり自己ループを含まず，任意の相違なる 2 頂点 u, v ∈ V において，有向辺 (u, v) は高々 1 つし
か E に含まれないとする（ただし (u, v), (v, u) ∈ E であることは許す）．U ⊆ V によって誘導される G の部
分グラフを G[U ] と表す．頂点 v ∈ V において，N − G (v) = {u ∈ V : (u, v) ∈ E} とし，d− G (v) = |N − G (v)|
とする．また，頂点集合 U ⊆ V において N − G (U ) =
∪
v∈U
N − G (v) \ U ，d− G (U ) = |N − G (U )| とする．さ
らに，U ∪ N − G (U ) を N − G [U ] で表す．辺の向きを逆に見ることにより，N + G および d+ G の記法を同様に
定義する．以降では，文脈から対象のグラフ G 明らかなときは，上の記法の添え字 G を省略する．
正整数 k, b において G が (k, b) 有界であるとは，d− (U ) ≤ k を満たす任意の U ⊆ V において，d− (U ∪
{v}) ≤ k を満たすような v ∈ V \ U が高々 b 個であり，かつ d+ (U ) ≤ k を満たす任意の U ⊆ V において，
d+ (U ∪ {v}) ≤ k を満たすような v ∈ V \ U が高々 b 個であることをいう．
Pilipczuk [11] は，準完全有向グラフにおいて入り次数が k 以下であるような頂点の個数が高々 2k + 1 で
あることを示した．次の補題はその観察を一般化している．
補題 1. 任意の h 準完全有向グラフ G = (V, E) は (k, h + 2k + 1) 有界である．
証明. b を G が (k, b) 有界となるような最小の整数とする．このとき，(k, b) 有界の定義より，
（１）d− (U ) ≤ k
を満たす U ⊆ V で，d− (U ∪ {v}) ≤ k を満たす v ∈ V \ U が b 個であるようなものが存在するか，または
（２）d+ (U ) ≤ k を満たす U ⊆ V で，d+ (U ∪ {v}) ≤ k を満たす v ∈ V \ U が b 個であるようなものが存在
する．
（１）の場合を考えるが，
（２）の場合も同様である．（１）を満たす U を固定し，d− (U ∪ {v}) ≤ k を
満たす v ∈ V \ U からなる集合を X とする．h 準完全の定義より，G[X] は少なくとも b(b − h − 1)/2 本の辺
を含むので，G[X] の平均入次数
∑
v∈X
d− (v)/b は (b − h − 1)/2 以上である．一方，どの v ∈ X に対しても
d− (U ∪ {v}) ≤ k であるから，この平均入次数は k 以下でなければならない．したがって，b − h − 1 ≤ 2k ，
すなわち b ≤ h + 2k + 1 を得る．
G = (V, E) を有向グラフとする．G のパス分解（path decomposition）とは，G の頂点集合の列 W =
(W1 , W2 , . . . , Wr ) で，
1.
∪
1≤i≤r
Wi = V ，
2. 各 (u, v) ∈ E において u ∈ Wi かつ v ∈ Wj を満たす i, j(1 ≤ i ≤ j ≤ r) が存在し，
3. 各 u ∈ V において，u ∈ Wi ∩ Wj ならば u ∈ Wk (i ≤ k ≤ j)
5
を満たすものである．パス分解 W の幅（width）とは，max1≤i≤r |Wi | − 1 のことであり，G のパス幅
（pathwidth）とは，G が幅 k のパス分解を持つような最小の k であると定義する．
パス分解 W = (W1 , W2 , . . . , Wr ) が好適である（nice）とは，W1 = Wp = ∅ であり，かつ任意の 1 ≤ i ≤ r−1
について
• Wi ⊂ Wi+1 かつ |Wi+1 | = |Wi | + 1
• Wi+1 ⊂ Wi かつ |Wi+1 | + 1 = |Wi |
のどちらかが成り立つことを言う．G のパス幅が w であれば，G は幅 w の好適なパス分解を持つことが良く
知られている．
6
第3章
準完全グラフのパス幅を求める FPT アルゴ
リズム
この章では Michal Pilipczuk の論文 [11] で提案されたアルゴリズムについて説明する．ここでは，アルゴ
リズムで利用するいくつかの定義と補題，アルゴリズムの流れのみ説明し，補題の証明などは割愛する．ま
た，彼の論文では，パス分解の定義の条件 2 が「各 (u, v) ∈ E において ，u ∈ Wi かつ v ∈ Wj を満たす
i, j(1 ≤ j ≤ i ≤ r) が存在」と我々の定義とは逆になっているが，本質的な違いがないことは以下の観察から
明らかである．
観察 1. 条件 2 が「各 (u, v) ∈ E において ，u ∈ Wi かつ v ∈ Wj を満たす i, j(1 ≤ j ≤ i ≤ r) が存在」であ
るような幅 k のパス分解を W = (W1 , W2 , . . . , Wr ) とすると，W ′ = (Wr , Wr−1 , . . . , W1 ) は条件 2 が「各
(u, v) ∈ E において ，u ∈ Wi かつ v ∈ Wj を満たす i, j(1 ≤ i ≤ j ≤ r) が存在」であるような幅 k のパス分
解である．
3.1 諸定義
ここでは，アルゴリズムで利用するいくつかの構造の定義を行う．G = (V, E) を有向グラフとする．
G = (V, E) の頂点集合の対 (A, B) が A ∪ B = V ，N − [A \ B] ⊆ A，かつ N + [B \ A] ⊆ B を満たすとき，
(A, B) を G の分離対（separation）と呼ぶ．分離対 (A, B) の位数を |A ∩ B| と定める．
分離対の列 ((A0 , B0 ), (A1 , B1 ), . . . , (Ar , Br )) が分離鎖 (Separation Chain) であるとは，(A0 , B0 ) = (∅, V )
かつ (Ar , Br ) = (V, ∅) かつ任意の i, j(i ≤ j) について Ai ⊆ Aj , Bj ⊆ Bi が成り立つことをいう．また，こ
のとき max0≤i≤r |Ai ∩ Bi | を分離鎖の 幅という．
[11] において，パス分解と分離鎖について次の補題が示されている．
補題 2 ([11]). パス分解と分離鎖について次のことが成り立つ．
• W = (W1 , W2 , . . . , Wr ) を幅が p であるパス分解であるとする．このとき任意の 0 ≤ i ≤ r について
∪
∪
(Ai , Bi ) = ( j≤i Wj , i<j Wj ) によって定義される ((A0 , B0 ), (A1 , B1 ), . . . , (Ar , Br )) は幅が p 以下
の分離鎖である．
• ((A0 , B0 ), (A1 , B1 ), . . . , (Ar , Br )) を幅が p である分離鎖であるとする．このとき，任意の 0 < i ≤ r
について Wi = Ai ∩ Bi−1 によって定義される W = (W1 , W2 , . . . , Wr ) は幅が max0≤i≤r |Ai ∩ Bi−1 |
7
のパス分解である．
G = (X, Y, E) を無向二部グラフ (X の任意の頂点間に辺がなく，Y の任意の頂点間に辺がないグラフ) と
する．また，頂点 v ∈ X ∪ Y に対して N (v) で v と隣接する頂点の集合を d(v) によって，|N (v)| を表すと
する．
G のバス選択子 Bl (G)(Blrev (G)) は v ∈ X(Y ) で，次のどちらかを満たすものすべての集合を表す．
• d(v) > l である．
• u ∈ N (v) で d(u) ≤ l であるものが少なくとも 1 つ存在する．
3.2 障害
ここでは，グラフのパス幅が k より大きくなることがわかる障害について述べる．次に示す構造がグラフに
存在した場合，その時点でアルゴリズムを停止し，パス幅が k より大きいことがいえる．
3.2.1 次数障害
T を準完全な有向グラフ，k ，l を整数とする．このとき，X ⊆ V (T ) が (k, l)-次数障害であるとは，|X| ≤ k
であり，かつ任意の v, w ∈ X について，|d+ (v) − d+ (w)| ≤ l が成り立つことをいう．
補題 3 ([11]). T を準完全な有向グラフとする．T が (5k + 2, k)-degree tangle であるような X を含むとき，
pw(T ) > k である．
3.2.2 マッチング障害
T を準完全な有向グラフ，k ，l を整数とする．このとき，X ∩ Y = ∅ であるような X, Y ⊆ V (T ) が (k, l)マッチング障害であるとは，|X| = |Y | = k であり，かつ X から Y へのマッチングが存在し，かつ任意の
v ∈ X, w ∈ Y に対して d+ (w) > d+ (v) + l が成り立つことをいう．
補題 4 ([11]). T を準完全な有向グラフとする．T が (k + 1, k)-matchin tangle であるような (X, Y ) を含む
とき，pw(T ) > k である．
3.3 補題
ここでは，アルゴリズムの説明に利用する補題について記述する．
T の 頂 点 v を d+ (v) に つ い て 昇 順 に 並 べ る ．並 べ た 頂 点 の 順 列 を (v1 , v2 , . . . , vn ) と す る ．
Hi = (Xi , Yi , Ei ) を Xi = {v1 , v2 , . . . , vi }，Yi = {vi , vi+1 , . . . , vn }，任 意 の x ∈ Xi , y ∈ Yi に 対
して，(x, y) ∈ E(T ) ならば，{x, y} ∈ E(Hi ) を満たすような無向二部グラフとする．
このとき，[11] において次の補題が示されている．
補題 5 ([11]). T を準完全な有向グラフ，m = 6k + 1 を整数とする．0 ≤ β ≤ n，α = max(0, β − (5k + 1))
rev
を満たすような任意の整数 (α, β) について，|Bm (Hα )| > m2 + m もしくは，|Bm
(Hβ )| > m2 + m を満た
8
すとき，pw(T ) > k である．
m = 6k + 1 とし，T の分離対 (A, B) について考える．α, β を 0 ≤ β ≤ n，α = max(0, β − (5k + 1)) を
満たすような整数とする．(A, B) が (α, β) に対して薄いとは，Yβ ⊆ B ⊆ Yα ∪ Bm (Hα ) かつ，Xα ⊆ A ⊆
rev
Xβ ∪ Bm
(Hβ ) を満たすことをいう．(A, B) が (α, β) に対して薄いような (α, β) が存在するとき，(A, B) を
単に薄いという．
分離鎖 C = ((A0 , B0 ), (A1 , B1 ), . . . , (Ar , Br )) について，(Ai , Bi )(0 ≤ i ≤ r) が全て薄いとき，分離鎖 C
は薄いという．
薄い分離鎖について，[11] の文脈より，以下の補題が得られる．
補題 6 ([11]). ((A0 , B0 ), (A1 , B1 ), . . . , (Ar , Br )) を幅が p である分離鎖とする．このとき，同じ幅で薄い分
離鎖が存在する．
この補題より，アルゴリズムでは薄い分離対のみを探索すればいいことがわかる．[11] の文脈より，位数が
k である薄い分離対を次のように特徴づけることができる．
補題 7 ([11]). 0 ≤ β ≤ n，α = max(0, β − (5k + 1)) を満たすような任意の整数 (α, β) について，
rev
|Bm (Hα )| > m2 + m もしくは，|Bm
(Hβ )| > m2 + m でないとき，薄い分離対 (A, B) は以下を満たす．
• v ∈ Xα \ Bm (Hα ) は A \ B に含まれる．
• v ∈ Xα ∪ Bm (Hα ) は A \ B ，A ∩ B のどれかに含まれる．
rev
• v ∈ Yβ \ Bm
(Hβ ) は B \ A に含まれる．
rev
• v ∈ Yβ ∩ Bm
(Hβ ) は B \ A，A ∩ B のどれかに含まれる．
• v ∈ Yα ∩ Xβ は A \ B ，B \ A，A ∩ B のどれかに含まれる．
このような薄い分離対は高々 2O(klogk) 個しか存在しない．
補題 7 によって，整数 β について特徴づけられる分離対の集合を Dβ とする．このとき，[11] の文脈より
以下の補題が得られる．
補題 8 ([11]). T を準完全な有向グラフ，(A, B)，(A′ , B ′ ) を A ⊆ A′ かつ B ′ ⊆ B であるような T の分離対
とする．このとき，(A, B) ∈ Dβ であるならば，(A′ , B ′ ) ∈ Dβ+j (−(6k + 2) ≤ j ≤ (6k + 2)) である．
3.4 アルゴリズム
T を準完全な有向グラフとし，T に対するアルゴリズムの流れについて説明する．アルゴリズムでは，T の
全ての分離対を探索することで，分離鎖 ((A0 , B0 ), (A1 , B1 ), . . . , (Ar , Br )) で，max1≤i≤r |Ai ∩ Bi−1 | − 1 ≤ k
であるようなものが存在するかを調べる．また，その過程で (5k + 2, k)-degree tangle，(k + 1, k)-matching
tangle を見つけたら，その時点でアルゴリズムを停止している．
定理 3 ([11]). T を準完全な有向グラフ，k を整数とする．ことのき，O(2O(k log k) |V (T )|2 ) 時間で pw(T ) ≤ k
であるかを判定するアルゴリズムが存在する．
T の頂点 v を d+ (v) について昇順に並べる．並べた頂点の順列を (v1 , v2 , . . . , vn ) とする．このとき，
9
d+ (vi+5k+1 ) > d+ (vi ) + k であるような頂点 vi が存在するとき，X = {vi , vi+1 , . . . , vi+5k+1 } は (5k + 2, k)degree tangle であるので，pw(T ) > k であるのでアルゴリズムを停止し，解を出力する．
rev
そうでないとして続ける．m = 6k + 1 として，全ての β(0 ≤ β ≤ n) に対して，Bm (Hα ) と Bm
(Hβ ) を求
rev
める．|Bm (Hα )| > m2 + m もしくは，|Bm
(Hβ )| > m2 + m を満たすとき，補題 5 より pw(T ) > k とし，ア
ルゴリズムを停止する．そうでないならば，補題 7 によって Dβ を求める．D =
′
′
∪
0≤β≤n
Dβ であるような D
′
を頂点集合として，A ⊆ A かつ B ⊆ B であり，B ∩ A ≤ k であるような分離対 (A, B)，(A′ , B ′ ) について，
(A, B) から (A′ , B ′ ) への辺をひいたグラフを考える．このグラフに (∅, V ) から (V, ∅) へのパスがあるかを調
べる．このグラフを構成する際には，補題 8 より，(A, B) ∈ Dβ ，(A′ , B ′ ) ∈ Dβ+j (−(6k + 2) ≤ j ≤ (6k + 2))
となるような任意の (A, B)，(A′ , B ′ ) について，A ⊆ A′ かつ B ′ ⊆ B ，|A′ ∩ B| ≤ k + 1 であるならば辺を
引けばよい．もし (∅, V ) から (V, ∅) へのパスがあったなら，そのパスは分離鎖であり，幅が高々 k であるよ
うなパス分解に対応しているので，pw(T ) ≤ k となる．また pw(T ) ≤ k であるならばそのようなパスが必ず
存在するので，見つからなかったときは，pw(T ) > k となる．
以下にアルゴリズムの疑似コードをのせる．
10
Algorithm 1 準完全グラフ T について，pw(T ) ≤ k かどうかを判定する．
1: T の頂点 v ∈ V (T ) を d+ (v) について昇順に並べ，これを (v1 , v2 , . . . , vn ) とする．
2:
3:
for i := 1 to i = n − (5k + 1) do
if d+ (vi+5k+1 ) ≤ d+ (vi ) + k then
pw(T ) > k としてアルゴリズムを停止する．
4:
5:
end if
6:
end for
7:
m := 6k + 1
8:
for ( doβ := 0 to β := n)
9:
Hα ，Hβ をつくる．
10:
rev
Bm (Hi )，Bm
(Hβ ) を求める．
11:
rev
if |Bm (Hα )| > m2 + m または |Bm
(Hβ )| > m2 + m then
pw(T ) > k としてアルゴリズムを停止する．
12:
13:
end if
14:
Dβ を求める．
15:
end for
16:
for β := 0 to β := n do
17:
for ∀(A, B) ∈ Dβ do
for i := max(0, β − (6k + 2)) to i := min(n, β + (6k + 2)) do
18:
for ∀(A′ , B ′ ) ∈ Di do
19:
if A ⊆ A′ かつ B ′ ⊆ B かつ |A′ ∩ B| ≤ k + 1 then
20:
(A, B) から (A′ , B ′ ) への辺をひく．
21:
end if
22:
end for
23:
end for
24:
25:
end for
26:
end for
27:
if (∅, V ) から (V, ∅) へのパスが存在する． then
28:
pw(T ) ≤ k としてアルゴリズムを停止する．
29:
30:
31:
else
pw(T ) > k としてアルゴリズムを停止する．
end if
11
第4章
h 準完全グラフのパス幅を求める FPT アル
ゴリズム
この章では，h 準完全グラフに対する FPT アルゴリズムについて記述する．ここで，以降の定義は，同じ
表記でもでも 3 章における定義とは違っているものがある．
4.1 諸定義
ここでは，アルゴリズムで利用するいくつかの定義を与える．G = (V, E) の頂点集合の対 (A, B) が
A ∪ B = V ，N − [A \ B] ⊆ A，かつ N + [B \ A] ⊆ B を満たすとき，(A, B) を G の分離対（separation）と
呼ぶ．分離対 (A, B) の位数を |A ∩ B| と定める．S, T ⊆ V について，分離対 (A, B) が，S ⊆ A \ B かつ
T ⊆ B \ A を満たしているとき，(A, B) を S–T 分離対という．また，(A, B) の位数が全ての S–T 分離対の
中で最小であるとき，(A, B) を最小 S–T 分離対という．
S–T 分離対 (A, B) が S 自明であるとは，A \ B = S であることを，T 自明であるとは B \ A = T である
ことを言う．S 自明または T 自明な S–T 分離対は自明であるという．非自明な最小 S-T 分離対が存在する
とき，対 (S, T ) は可約であるといい，そうでないとき対 (S, T ) は既約であるという．
分離対の列 ((A0 , B0 ), (A1 , B1 ), . . . , (Ar , Br )) が A0 ⊆ A1 ⊆ . . . ⊆ Ar ⊆ V ，Br ⊆ Br−1 ⊆ . . . ⊆ B0 ⊆ V
を満たすとき，この列を 分離鎖と呼びそれに属する分離対の最大位数 max0≤i≤r |Ai ∩ Bi | をその幅という．
C = ((A0 , B0 ), (A1 , B2 ), . . . , (Ar , Br )) を分離鎖とする．C が密であるとは，任意の隣り合う分離対
(Ai , Bi )，(Ai+1 , Bi+1 ) について，|Ai+1 \ Ai | ≤ 1 と |Bi \ Bi+1 | ≤ 1 の少なくとも一方が成り立つことをい
う．この定義は同一の分離対の繰り返しを許すことに注意する．S, T ⊆ V に対して，C が S–T 分離鎖であ
るとは，B0 = V \ S かつ，Ar = V \ T を満たしていることをいう．S–T 分離鎖を構成する分離対は，すべ
て S–T 分離対であることに注意する．
分 離 鎖 C = ((A0 , B0 ), (A1 , B1 , ), . . . , (Ar , Br )) と Ar ⊆ A′0 か つ B0′ ⊆ Br を 満 た す 分 離 鎖 C ′ =
((A′0 , B0′ ), (A′1 , B1′ , ), . . . , (A′s , Bs′ )) において，(C, C ′ ) で C の後ろに C ′ をつなげた分離鎖，つまり，
(C, C ′ ) = ((A0 , B0 ), . . . , (Ar , Br ), (A′0 , B0′ ), . . . , (A′s , Bs′ ))
と表す．3 つ以上の分離鎖に関しても同様に表記する．
Pilipczuk の論文 [11] で示されている補題 2 よりパス分解と分離鎖について以下の観察が得られる．
観察 2 ([11]). 以下のことが成り立つ．
12
• W = (W1 , W2 , . . . , Wr ) を幅 k 以下のパス分解とする．このとき，(Ai , Bi ) = (
∪
j≤i
Xj ,
∪
i<j
Xj ) で
あるような ((A1 , B1 ), (A2 , B2 ), . . . , (Ar , Br )) は幅 k 以下の ∅–∅ 分離鎖である．
• ((A1 , B1 ), (A2 , B2 ), . . . , (Ar , Br )) を幅 k 以下の ∅–∅ 分離鎖とする．このとき，Wi = Ai ∩ Bi−1 であ
るような W = (W1 , W2 , . . . , Wr ) は幅 max0<i≤r |Ai ∩ Bi−1 | − 1 のパス分解である．
補題 9. G のパス幅が k 以下であることの必要十分条件は，幅が k 以下の密な ∅–∅ 分離鎖が存在することで
ある．
証明. G のパス幅が k 以下であるとき，幅が k 以下の好適なパス分解 (X1 , X2 , . . . , Xp ) が存在する．このとき，
観察 2 より，1 ≤ i ≤ p に対して，(Ai , Bi ) = (
∪
j≤i
Xj ,
∪
j>i
Xj ) とおくと，((A1 , B1 ), (A2 , B2 ), . . . , (Ap , Bp ))
は幅 k 以下の密な ∅–∅ 分離鎖である. 他方，幅 k の密な ∅–∅ 分離鎖 ((A0 , B0 ), (A1 , B1 ), . . . , (Ar , Br )) が
与えらえれたとき，観察 2 より，1 ≤ i ≤ r に対して，Xi = Ai ∩ Bi−1 とおくと (X1 , X2 , . . . , Xr ) は，幅
が max0<i≤r |Ai ∩ Bi−1 | − 1 のパス分解である．密であることより，任意の隣り合う分離対 (Ai−1 , Bi−1 )，
(Ai , Bi ) について，|Ai \Ai−1 | ≤ 1 または，|Bi−1 \Bi | ≤ 1 を満たしている．前者を満たすとき，|Ai ∩Bi−1 | ≤
|Ai−1 ∩ Bi−1 | + 1 = k + 1 であり，後者を満たすとき，|Ai ∩ Bi−1 | ≤ |Ai ∩ Bi | + 1 = k + 1 であるので，
max0<i≤r |Ai ∩ Bi−1 | − 1 ≤ k となる．
4.2 補題
この節では，アルゴリズムの設計と正しさの証明に有用な補題と観察をいくつか与える．すべての補題にお
いて，有向グラフ G = (V, E) が暗黙に仮定されている．
S–T 分離鎖 C = ((A0 , B0 ), (A1 , B1 ), . . . , (Ar , Br )) が好適であるとは任意の 0 ≤ i < r について，
|Ai+1 \ Ai | ≤ 1 かつ |Bi \ Bi+1 | ≤ 1 であることをいう．この定義は密な分離鎖と同様に，同じ S–T 分離対
の繰り返しを許している．また，好適な S–T 分離鎖は明らかに密な S–T 分離鎖であるといえる．S–T 分離
鎖 C がタイトであるとは，A0 = N − [S] かつ Br = N + [T ] であることをいう．
補題 10. 幅 k 以下の密な S–T 分離鎖 ((A0 , B0 ), (A1 , B1 ), . . . , (Ar , Br )) が存在するとき，幅 k 以下のタイ
トでありかつ好適な S–T 分離鎖が存在する．
証明. S–T 分離鎖 C = ((A0 , B0 ), (A1 , B1 ), . . . , (Ar , Br )) において，δ(C) を
δ(C) = |A0 \ N − [S]| + |B0 \ N + [T ]|
∑
+
(max{0, |Ai+1 \ Ai | − 1} + max{0, |Bi \ Bi+1 | − 1})
0≤i<r
と定義する．ここで，C を幅 k 以下の S–T 分離鎖の中で δ(C) が最小であるものとする．もし，δ(C) = 0
であれば C はタイトであり，かつ好適であるので，証明を終了する．以下では δ(C) > 0 を仮定して矛盾を導
く．まず，v ∈ A0 \ N − [S] がある場合について考える．このとき，(A0 \ {v}, B0 ) を C の先頭に追加したも
のを C ′ とすると，C ′ は密な S–T 分離鎖である．また，(A0 \ {v}, B0 ) の位数は (A0 , B0 ) の位数よりも小さ
いので C ′ の幅は k 以下である．明らかに δ(C ′ ) = δ(C) − 1 であるので，δ(C) が最小であることに矛盾する．
同様にして，v ∈ Br \ N + [T ] である場合についても矛盾が導かれる．
最後に 0 ≤ i < r について，|Ai+1 \ Ai | ≥ 2 である場合を考える．ここで，v ∈ Ai+1 \ Ai について，
(Ai ∪ {u}, Bi ) は S–T 分離対であり，密である条件から，|Bi \ Bi+1 | ≤ 1 であるため，(Ai ∪ {v}, Bi ) の位数
13
は (Ai+1 , Bi+1 ) の位数以下である．よって，C の (Ai , Bi ) と (Ai+1 , Bi+1 ) の間に (Ai ∪ {v}, Bi ) を追加した
ものを C ′ とすると，C ′ は幅 k 以下の密な S–T 分離鎖である．ここで
δ(C ′ ) = δ(C) − max{0, |Ai+1 \ Ai | − 1} − max{0, |Bi \ Bi+1 | − 1}
+ max{0, |{v}| − 1} + max{0, |Bi \ Bi | − 1}
+ max{0, |Ai+1 \ (Ai ∪ {v})| − 1} + max{0, |Bi \ Bi+1 | − 1}
≤ δ(C) − max{0, |Ai+1 \ Ai | − 1]} + max{0, |Ai+1 \ (Ai ∪ {v})| − 1}
であり，|Ai+1 \ Ai | > 1 であることから
δ(C ′ ) ≤ δ(C) − 1
となる．よって δ(C) が最小であることに矛盾する．同様にして |Bi \ Bi+1 | ≥ 2 である場合についても矛盾
が導かれる．
V の部分集合 S, T ⊆ V について，幅 k 以下の密な S–T 分離鎖が存在するとき，(S, T ) は k 分離可能であ
るという．また，N − [S] ∩ T = ∅ （したがって，S ∩ N + [T ] = ∅），d− (S) ≤ k ，かつ d+ (T ) ≤ k であると
き，(S, T ) は弱 k 分離可能であるという．次の観察は自明であろう．
観察 3. (S, T ) が弱 k 分離可能であることは，(S, T ) が k 分離可能であるための必要条件である．
補題 11. 弱 k 分離可能な対 (S, T ) が |V \ (S ∪ T )| ≤ k + 1 を満たすとき，(S, T ) は k 分離可能である．
証明. 証明は背理法による．補題が成り立たないと仮定し，弱 k 分離可能な対 (S, T ) で，|V \ (S ∪ T )| ≤ k + 1
であるにもかかわらず k 分離可能でないものを，|V \ (S ∪ T )| が最小になるように選ぶ．もし，V \ (S ∪ T ) =
N − (S) = N + (T ) であれば，(N − [S], N + [T ]) は，単独で幅 k 以下の密な S–T 分離鎖を構成するので，これ
はあり得ない．したがって，ある v ∈ V \ (S ∪ T ) で，（1）v ̸∈ N − (S) または（2）v ̸∈ N − (T ) であるもの
が存在する．（1）の場合，T ′ = T ∪ {v} とおくと，v ̸∈ N − (S) より，N + (T ′ ) ⊆ V \ (S ∪ T ∪ {v}) であ
るから，|N + (T ′ )| ≤ k が成り立つ．また，v ̸∈ N − (S) より N − [S] ∩ T ′ = ∅ も成り立つ．よって，(S, T ′ )
は弱 k 分離可能である．|V \ (S ∪ T ′ )| < |V \ (S ∪ T )| ≤ k + 1 であるので，(S, T ) の選び方から，(S, T ′ )
は k 分離可能であり，幅 k 以下の密な S–T ′ 分離鎖 C ′ が存在する．C ′ の最後の分離対を (A, B) とおくと，
A = (V \ T ′ ) ⊆ (V \ T ) であり B ⊇ N + [T ′ ] ⊇ N + [T ] なので，C ′ の直後に (V \ T, N + [T ]) を追加してでき
る列 C は S–T 分離鎖である．また，C ′ が密でありかつ (V \ T ) \ A = {v} であるので，C も密である．さ
らに，C ′ の幅が k 以下でありかつ (V \ T, N + [T ]) の位数が |N + (T )| ≤ k であるので，C の幅も k 以下であ
る．以上より，(S, T ) が k 分離可能であることが結論され，仮定に矛盾する．（2）の場合も，
（1）の場合と対
称な議論により，矛盾が導かれる．
上の証明は背理法の形をとっているが実質は帰納法であり，条件を満たす対 (S, T ) から幅 k 以下の密な
(S, T ) 分離鎖を構成する手続きを与えていることに注意する．
補題 12. 対 (S, T ) が k 分離可能であるとする．もし |V \ (S ∪ T )| ≥ k + 2 であるならば相異なる頂点
u ∈ V \ (S ∪ N + [T ]) と v ∈ V \ (T ∪ N − [S]) の対で，(S ∪ {u}, T )，(S, T ∪ {v})，および (S ∪ {u}, T ∪ {v})
のいずれも k 分離可能であるようなものが存在する．
証明. (S, T ) は k 分離可能であるので，補題 10 より，幅 k 以下のタイトかつ好適な S–T 分離鎖 C =
((A0 , B0 ), (A1 , B1 ), . . . , (Ar , Br )) が存在する．C はタイトであるので，Br = N + [T ] であり，また B0 = V \S
14
である．したがって，|B0 | ≥ |T | + k + 2 ≥ |Br | + 2 が成り立つ．0 < i ≤ r の範囲で |Bi−1 \ Bi | = 1 で
あるような最小の i を j で表す．Bj−1 \ Bj = {u}，C ′ = ((Aj , Bj ), (Aj+1 , Bj+1 ), . . . , (Ar , Br )) とおくと，
Bj = V \ (S ∪ {u}) であり，Ar = V \ T であるので，C ′ は幅 k 以下の密な (S ∪ {u})–T 分離鎖である．こ
の u は，Br \ B0 = V \ (S ∪ N + [T ]) に属すので，補題の条件を満たしている．(S ∪ {u}, T ) が k 分離可能で
あるので，幅 k 以下のタイトかつ好適な (S ∪ {u})–T 分離鎖が存在する．|Ar | ≥ |A0 \ {u}| + 1 であること
に注意して上と対称な議論を用いることにより，頂点 v ∈ V \ (T ∪ N − [S]) で，(S ∪ {u}, T ∪ {v}) が k 分離
可能であるものの存在が示される．幅 k 以下の密な (S ∪ {u})–(T ∪ {v}) 分離鎖の前に (N − [S], V \ T ) を置
いてできる分離鎖の幅は k 以下であるので，(S, T ∪ {v}) もまた k 分離可能である．
最後に，可約な対 (S, T ) に対する問題の分割を可能にする補題を挙げる．
補題 13. (X, Y ) を最小 S–T 分離対であるとする．このとき，任意の S–T 分離対 (A, B) について，
|(A ∩ X) ∩ (B ∪ Y )| ≤ |A ∩ B|
|(A ∪ X) ∩ (B ∩ Y )| ≤ |A ∩ B|
が成り立つ．
証明. まず，|A ∩ B| + |X ∩ Y | = |(A ∩ X) ∩ (B ∪ Y )| + |(A ∪ X) ∩ (B ∩ Y )| である．これは任意の頂点 v
に対して左辺で v が数えれれる回数と右辺で v が数えられる回数が一致することからわかる．
(X, Y ) と (A, B) がともに S–T 分離対であるので，((A ∩ X), (B ∪ Y )) と ((A ∪ X), (B ∩ Y )) はともに
S–T 分離対である．(X, Y ) は S–T 分離対の中で位数が最小であるので，|X ∩ Y | ≤ |(A ∪ X) ∩ (B ∩ Y )| で
ある．よって，|(A ∩ X) ∩ (B ∪ Y )| ≤ |A ∩ B| がいえる．
また，|X ∩ Y | ≤ |(A ∩ X) ∩ (B ∪ Y )| でもあるので，|(A ∪ X) ∩ (B ∩ Y )| ≤ |A ∩ B| もいえる
補題 14. (X, Y ) を最小 S–T 分離対とする．このとき，(S, T ) が k 分離可能であるならば，(S, Y \ X) およ
び (X \ Y, T ) はどちらも k 分離可能である．
証明. (S, T ) は k 分離可能であるので，幅が k 以下の密な S–T 分離鎖が存在する．そのような分離鎖を
C = ((A0 , B0 ), (A1 , B1 ), . . . , (Ar , Br )) とする．このとき，B0 = V \ S ，Ar = V \ T である．C は S–T 分
離鎖であるので，C ′ = ((A0 ∩ X, B0 ∪ Y ), (A1 ∩ X, B1 ∪ Y ), . . . , (Ar ∩ X, Br ∪ Y )) も S–T 分離鎖である．
ここで，C は密な分離鎖であり，かつ N − [S] ⊆ X かつ N + [T ] ⊆ Y を満たしている．よって，B0 ∪ Y =
(V \ S) ∪ Y = (V \ S) であり，Ar ∩ X = (V \ T ) ∩ X = X = V \ (Y \ X) である．また，(X, Y ) は最小
S–T 分離対であるので，X ∩ Y = N − (X \ Y ) = N + (Y \ X) である．
よって，C ′ は，密な S–(Y \ X) 分離鎖である．補題 13 より，0 ≤ i ≤ r に対して |(Ai ∩ X) ∩ (Bi ∪ Y )| ≤
|Ai ∩ Bi | であるので，その幅は k 以下である．
((A0 ∪ X, B0 ∩ Y ), (A1 ∪ X, B1 ∩ Y ), . . . , (Ar ∪ X, Br ∩ Y )) についても同様の議論より，密な (X \ Y )–T
分離鎖であり，その幅は k 以下であることが示せる．
4.3 アルゴリズム
有向グラフ G = (V, E) と正整数 k を入力し，G のパス幅が k 以下であるかどうかを判定するアルゴリズム
を記述する．答えが肯定的であるとき，アルゴリズムは幅が k 以下の ∅–∅ 分離鎖を構築する．
15
以下のアルゴリズム記述では，入力のグラフ G と正整数 k を固定する．再帰関数 SC は，弱 k 分離可能な
対 (S, T ) に対して (S, T ) が k 分離可能であるかを判定し，もし可能であれば幅 k 以下の密な S–T 分離鎖を，
そうでなければ特別な値 FAILURE を返す．関数 SC のなかでは，対 (S, T ) が可約であるかを検査し，可約
な場合には非自明な最小分離対を求める必要がある．S も T も空でないときにはこれは，最大流アルゴリズ
ムによって実装することができる．S が空である場合には，(∅, V ) は位数 0 の自明な最小 S–T 分離対である．
この場合に，非自明な最小 S–T 分離対が存在するかどうかは，強連結成分分解アルゴリズムによって判定す
ることができる．T が空の場合も同様である．
Algorithm 2 SC(S, T )
1: if |V \ (S ∪ T )| ≤ k + 1 then
2:
return 補題 11 によって構築される幅 k 以下の S–T 分離鎖
3:
else if (S, T ) が可約である． then
4:
SC(S, T )-分割の処理を行う．
5:
6:
7:
8:
9:
10:
11:
else if d− (S) = d+ (T ) then
SC(S, T )-等しいの処理を行う．
else if d− (S) < d+ (T ) then
SC(S, T )-小さいの処理を行う．
else
SC(S, T )-大きいの処理を行う．
end if
Algorithm 3 SC(S, T )-分割
1: (X, Y ) を非自明な最小 S–T 分離対とする．
2:
SC(S, Y \ X) と SC(X \ Y, T ) を呼び出す．
3:
if どちらかの結果が FAILURE である then
4:
return FAILURE
5:
end if
6:
SC(S, Y \ X) の返した分離鎖を C ，SC(X \ Y, T ) の返した分離鎖を C ′ とする．
7:
return (C, (X, Y ), C ′ )．
対 (S, T ) が既約である場合には，補題 12 に基づいて，解の可能性を探索する．
16
Algorithm 4 SC(S, T )-等しい
1: for d− (S∪{u}) ≤ k である各 u ∈ V \(S∪N + [T ]) と d+ (T ∪{v}) ≤ k である各 v ∈ V \(N − [S∪{u}]∪T )
do
2:
SC(S ∪ {u}, T ∪ {v}) を呼び出す．
3:
if 結果が分離鎖 C である then
4:
5:
return ((N − [S], V \ S), C, (V \ T, N + [T ]))．
end if
6:
end for
7:
return FAILURE
Algorithm 5 SC(S, T )-小さい
1: for d− (S ∪ {u}) ≤ k である各 u ∈ V \ (S ∪ N + [T ]) do
2:
SC(S ∪ {u}, T ) を呼び出す．
3:
if 結果が分離鎖 C である then
4:
5:
return ((N − [S], V \ S), C)．
end if
6:
end for
7:
return FAILURE
Algorithm 6 SC(S, T )-大きい
1: for d+ (T ∪ {v}) ≤ k である各 v ∈ V \ (N − [S] ∪ T ) do
2:
SC(S, T ∪ {v}) を呼び出す．
3:
if 結果が分離鎖 C である then
4:
5:
return (C, (V \ T, N + [T ]))．
end if
6:
end for
7:
return FAILURE
4.4 正しさの証明
補題 15. 弱 k 分離可能な対 (S, T ) に対する呼び出し SC(S, T ) は，(S, T ) が k 分離可能であるとき幅 k 以下
の密な S–T 分離鎖を，そうでないときは FAILURE を返す．
証明. |V \ (S ∪ T )| についての帰納法で証明する．基底は |V \ (S ∪ T )| ≤ k + 1 のときであり，補題 11 よ
り，SC(S, T ) は正しい値を返す．
次に，|V \ (S ∪ T )| ≥ k + 2 のときを考える．まず (S, T ) が可約であるとする．このとき，非自明な最小
S–T 分離対 (X, Y ) に対して，SC(S, Y \ X) と SC(X \ Y, T ) が呼ばれる．(X, Y ) が非自明な最小 S–T 分離
対であることから，Y \ X は S にも T にも属さない頂点を要素として持ち，X \ Y も同様である．したがっ
て |V \ (S ∪ (Y \ X))| < |V \ (S ∪ T )| かつ |V \ ((X \ Y ) ∪ T )| < |V \ (S ∪ T )| が成り立つ．もし，(S, T )
17
が k 分離可能であるならば，補題 14 により，(S, Y \ X) と (X \ Y, T ) はともに k 分離可能であり，したがっ
て弱 k 分離可能でもある．このとき，帰納法の仮定により，SC(S, Y \ X) と SC(X \ Y, T ) はそれぞれ幅 k
以下の密な S–(Y \ X) 分離鎖 C = ((A0 , B0 ), (A1 , B1 ), . . . , (Ap , Bp )) と幅 k 以下の密な (X \ Y )–T 分離鎖
C ′ = ((A′0 , B0′ ), . . . , (A′q , Bq′ )) を返す．このとき，Ap = V \ (Y \ X) = X かつ N + [Y \ X] ⊆ Bp であり
N − [X \ Y ] ⊆ A′0 かつ B0′ = V \ (X \ Y ) = Y であるので，SC(S, T ) の返す分離鎖 (C, (X, Y ), C ′ ) は幅 k 以
下の密な S–T 分離鎖である．一方，(S, T ) が k 分離可能でなければ，(S, Y \ X) と (X \ Y, T ) の少なくとも
一方は k 分離可能ではなく，したがって，SC(S, T ) は FAILURE を返す．
次に (S, T ) が既約であり，SC(S, T )-等しいの処理が行われる場合を考える．この処理においては，(S ∪
{u}, T ∪ {v}) が弱 k 分離可能であるような u ∈ V \ (S ∪ N + [T ]) と v ∈ V \ (N − [S] ∪ T ) の対のすべてに対
して，SC(S ∪ {u}, T ∪ {v}) が呼ばれる．もし (S, T ) が k 分離可能であれば，補題 14 により，そのような
u と v の対のなかで，(S ∪ {u}, T ∪ {v}) が k 分離可能であるようなものが存在する．帰納法の仮定より，そ
のような u と v の対に対して，SC(S ∪ {u}, T ∪ {v}) は幅 k 以下の密な (S ∪ {u})–(T ∪ {v}) 分離鎖を返す．
このとき，SC(S, T ) の返す分離鎖は，この分離鎖の先頭に (N − [S], V \ S) を追加し，後尾に (V \ T, N + [T ])
を追加したものであるので，幅 k 以下の密な S–T 分離鎖である．一方，(S, T ) が k 分離可能でないならば，
SC(S ∪ {u}, T ∪ {v}) の呼び出しのどれについても，(S ∪ {u}, T ∪ {v}) が k 分離可能ではないので，帰納法
の仮定により，FAILURE が返る．したがって，SC(S, T ) も正しい値 FAILURE を返す．
(S, T ) が既約であり，SC(S, T )-小さいまたは SC(S, T )-大きいの処理が行われる場合も同様である．
系 1. 呼び出し SC(∅, ∅) は，G のパス幅が k 以下のとき密な ∅–∅ 分離鎖を返し，そうでないとき FAILURE
を返す．
4.5 実行時間の解析
関数 SC の入力となる対 (S, T ) の「大きさ」を表現するために，ふたつの関数 γ(S, T ) および µ(S, T ) を定
義する．まず，γ(S, T ) は，最小 S–T 分離対の位数を表す．また， µ(S, T ) は
µ(S, T ) = 2|V \ (N − [S] ∪ N + [T ])| + |N − (S)∆N + (T )|
によって定義する．ここで，X∆Y は，X と Y の対称差 (X \ Y ) ∪ (Y \ X) を表す．
補題 16. (X, Y ) を最小 S–T 分離対とする．このとき，
µ(S, Y \ X) + µ(X \ Y, T ) = µ(S, T )
が成り立つ．
証明. (X, Y ) が最小 S–T 分離対であることから，N − (X \ Y ) = N + (Y \ X) = X ∩ Y であり，したがって
N − [X \ Y ] = X, N + [Y \ X] = Y である．互いに素な 3 つの集合 C0 , C1 , C2 を
C0 = X ∩ Y \ (N − (S) ∪ N + (T ))
C1 = X ∩ Y ∩ (N − (S) \ N + (T ))
C2 = X ∩ Y ∩ (N + (T ) \ N − (S))
18
によって定義する．このとき，(X ∩ Y ) \ N + (T ) = C0 ∪ C1 であることや N + (T ) ∩ (X \ Y ) = ∅ であるから
N + (T ) \ (X ∩ Y ) = N + (T ) \ X が成り立つことを用いて，
µ(X \ Y, T ) = 2|V \ (X ∪ N + [T ])| + |(X ∩ Y )∆N + (T )|
= 2|V \ (X ∪ N + [T ])| + |C0 | + |C1 | + |N + (T ) \ X|
を得る．同様にして，
µ(S, Y \ T ) = 2|V \ (N − [S] ∪ Y )| + |N − (S)∆(X ∩ Y )|
= 2|V \ (N − [S] ∪ Y )| + |C0 | + |C2 | + |N − (S) \ Y |
を得る．また
|V \ (N − [S] ∪ N + [T ])| = |V \ (Y ∪ N − [S])| + |V \ (X ∪ N + [T ])| + |C0 |
および
|N − (S)∆N + (T )| = |C1 | + |C2 | + |N − (S) \ Y | + |N + (T ) \ X|
が成り立つ．よって，
µ(S, T ) = 2|V \ (N − [S] ∪ N + [T ])| + |N − (S)∆N + (T )|
= 2|V \ (Y ∪ N − [S])| + 2|(V \ (X ∪ N + [T ])| + 2|C0 | + |C1 | + |C2 | + |N − (S) \ Y | + |N + (T ) \ X|
= µ(S, Y \ X) + µ(X \ Y, T )
であり，補題の等式を得る．
補題 17. (X, Y ) を非自明な S–T 分離対であるとき，µ(S, Y \ X) ≥ 1 かつ µ(X \ Y, T ) ≥ 1 が成り立つ．
証明. 対称性より，最初の不等式を証明すれば十分である．(X, Y ) は非自明な S–T 分離対であるから，
(X \Y )\S に属す頂点 v が存在する．分離対の定義より，N + [Y \X] ⊆ Y であるから，v ̸∈ N + [Y \X] が成り立
つ．v ∈ N − (S) であれば，v ∈ N − (S)∆N + (Y \X) であり，v ̸∈ N − (S) であれば，v ∈ V \(N − [S]∪N + [Y \X])
である． したがって，いずれの場合にも
µ(S, Y \ X) = 2|V \ (N − [S] ∪ N + [Y \ X])|
+|N − (S)∆N + (Y \ X)|
≥1
を得る．
以 下 の 解 析 で は ，R(S, T ) に よ っ て ，SC(S, T ) を 呼 び 出 す こ と で 引 き 起 こ さ れ る 呼 び 出 し
SC(S ′ , T ′ )(SC(S, T ) 自 身 を 含 む) の う ち ，|V \ (S ∪ T )| ≥ k + 2 で あ る よ う な も の の 個 数 を 表 す ．
また，µ′ (S, T ) = max{0, 2µ(S, T ) − 1} によって µ′ を定義する．
補題 18. 入力グラフ G が (k, b) 有界であるとき，弱 k 分離可能な対 (S, T ) のそれぞれに対して，
R(S, T ) ≤ µ′ (S, T ) · b2(k−γ(S,T ))
が成り立つ．
19
(4.1)
証明. 証明は，再帰の構造に基づく帰納法による．
呼び出し SC(S, T ) が，|V \ (S ∪ T )| ≤ k + 1 であるためにそれ以上再帰をしないときには，R(S, T ) = 0
であるので，不等式（4.1）が成り立つ．µ(S, T ) = 0 のときは，V \ (S ∪ T ) = N − (S) = N + (T ) であるの
で，この場合が該当することに注意する．
次に呼び出し SC(S, T ) が「分割」の処理において，SC(S, T ′ ) と SC(S ′ , T ) を呼び出す場合を考える．こ
こで，(S, T ) の非自明な最小分離対 (X, Y ) に対して，S ′ = X \ Y であり，T ′ = Y \ X である．このと
き，補題 16 により，µ(S, T ) = µ(S, T ′ ) + µ(S ′ , T ) が成り立つ．さらに，補題 17 により µ(S, T ′ ) ≥ 1 かつ
µ(S ′ , T ) ≥ 1 であるので，
µ′ (S, T ) = 2µ(S, T ) − 1
= (2µ(S, T ′ ) − 1) + (2µ(S ′ , T ) − 1) + 1
= µ′ (S, T ′ ) + µ′ (S ′ , T ) + 1
を得る．また，S–T ′ 分離対のどれもが S–T 分離対であることから，γ(S, T ′ ) ≥ γ(S, T ) が成り立ち，同様に
γ(S ′ , T ) ≥ γ(S, T ) が成り立つ．帰納法の仮定を対 (S, T ′ ) と (S ′ , T ) に適用することにより，
R(S, T ) = 1 + R(S, T ′ ) + R(S ′ , T )
≤ 1 + (µ′ (S, T ′ ) + µ′ (S ′ , T )) · b2(k−γ(S,T ))
≤ 1 + (µ′ (S, T ) − 1) · b2(k−γ(S,T ))
≤ µ′ (S, T ) · b2(k−γ(S,T ))
すなわち，不等式（4.1）が成り立つ．
次に，(S, T ) が既約であり d− (S) = d+ (T ) である場合を考える．このとき，「等しい」の処理によって，
(S ∪ {u}, T ∪ {v}) が弱 k 分離可能であるような u ∈ V \ (S ∪ N + [T ]) と v ∈ V \ (N − [S] ∪ T ) の対のすべて
に対して，SC(S ∪ {u}, T ∪ {v}) が呼ばれる．グラフは (k, b) 有界であるので，そのような u と v の対の個数
は b2 以下である．帰納法の仮定により，u と v の各対に対して，
R(S ∪ {u}, T ∪ {v}) ≤ µ′ (S ∪ {u}, T ∪ {v}) · b2(k−γ(S∪{u},S∪{v}))
が成り立つ．(S, T ) が既約であるので，γ(S ∪{u}, T ∪{v}) > γ(S, T ) が成り立つ．また µ(S ∪{v}, T ∪{v}) <
µ(S, T ) および µ(S, T ) > 0 より，µ′ (S ∪ {v}, T ∪ {v}) < µ′ (S, T ) が成り立つ．したがって，
R(S, T ) ≤ 1 +
∑
R(S ∪ {u}, T ∪ {v})
u,v
≤ 1 + b2 · (µ′ (S, T ) − 1) · b2(k−γ(S,T )−1)
≤ µ′ (S, T ) · b2(k−γ(S,T ))
すなわち，不等式（4.1）が成り立つ．
(S, T ) が既約でありかつ d− (S) > d+ (T ) または d− (S) < d+ (T ) である場合の解析も同様である．
定理 2 の証明：与えられた有向グラフ G と正整数 k に対して，SC(∅, ∅) を実行することによって，G のパ
ス幅が k 以下であるかを判定することができる．この呼び出しによって発生する SC の呼び出しで基底を除い
20
たものの回数は R(∅, ∅) ≤ b2k n である．基底以外の SC のそれぞれの実行において，再帰呼び出しに費やさ
れる部分を除いた実行時間は nO(1) である．また，SC の呼び出しのうち，基底であるものの回数は，基底以
外の呼び出し一回あたりたかだか b である．故に，SC(∅, ∅) の実行に要する時間の合計は b2k nO(1) である．
4.6 実装上の工夫
ここでは，理論的な実行時間には影響はないが，実装上の実行時間をより高速化できる補題と，その補題を
用いたアルゴリズムについて説明する．この補題は Tamaki が提案した「コミットメント」[15] の特別な場合
である．
補題 19. 対 (S, T ) が k 分離可能であるとする．このとき，d− (S ∪ {u}) ≤ d− (S) を満たすような頂点
u ∈ V \ (S ∪ N + [T ]) について，対 (S ∪ {u}, T ) は k 分離可能である．同様に，d+ (T ∪ {v}) ≤ d+ (T ) を満
たすような頂点 v ∈ V \ (N − [S] ∪ T ) について，対 (S, T ∪ {v}) は k 分離可能である．
証明. C = ((A0 , B0 ), (A1 , B1 ), . . . , (Ar , Br )) を幅が k 以下である密な S − T 分離鎖とする．このとき，
B0 = V \ S ，Ar = V \ T である．
d− (S ∪ {u}) ≤ d− (S) であるような u ∈ V \ (S ∪ N + [T ]) について考える．
N − (u) ⊆ N − [S] であるとき，N − (S ∪ {u}) ⊆ N − (S) である．よって，任意の 0 ≤ i ≤ r について
(Ai ∪ {u}, Bi \ {u}) は S ∪ {u}–T 分離対である．また，その位数は明らかに (Ai , Bi ) 以下である．ここ
で，B0 \ {u} = (V \ S) \ {u} = V \ (S ∪ {u}) かつ，Ar ∪ {u} = (V \ T ) ∪ {u} = V \ T であるので，
C ′ = ((A0 ∪ {u}, B0 \ {u}), (A1 ∪ {u}, B1 \ {u}), . . . , (Ar ∪ {u}, Br \ {u})) は幅が k 以下の密な S ∪ {u}–T
分離鎖である．
次に N − (u) ⊆ N − [S] でないとき d− (S ∪ {u}) ≤ d− (S) であるので，u ∈ N − (S) であり，かつ |N − (u) \
N − (S)| = 1 である．よって，N − (u)\N − (S) = {w} とすると，任意の 0 ≤ i ≤ r について (Ai ∪{w}, Bi \{u})
は S ∪{u}–T 分離対である．B0 \{u} = (V \S)\{u} = V \(S ∪{u}) かつ，Ar ∪{w} = (V \T )∪{w} = V \T
であるので，C ′ = ((A0 ∪ {w}, B0 \ {u}), (A1 ∪ {w}, B1 \ {u}), . . . , (Ar ∪ {w}, Br \ {u})) は密な S ∪ {u}–T
分離鎖である．
ここで，u ∈ Bi であるとき，u ∈ N − (S) であることから，u ∈ Ai でもあるので，|(Ai ∪ {w}) ∩ (Bi \ {u})| ≤
|(Ai ∪ {w}) ∩ Bi | − 1 ≤ |Ai ∩ Bi | である
また，u ∈
/ Bi であるとき，(Ai , Bi ) が分離対であり，w ∈ N − (u) であることから，w ∈ Ai である．よっ
て，Ai ∪ {w} = Ai ，Bi \ {u} = Bi となる．
よって C ′ の幅は k 以下のとなる．
対称的な議論より，後者についても正しいことが示せる．
各再帰の初めに，この補題を用いて S と T をできる限り拡張する．以下に疑似コードを載せる．
21
Algorithm 7 SC(S, T )
1: if d− (S ∪ {u}) ≤ d− (S) であるような u ∈ V \ (S ∪ N + [T ]) が存在する then
2:
SC(S ∪ {u}, T ) を呼び出す．
3:
if 結果が分離鎖 C である． then
4:
return ((N − [S], V \ S), C)．
5:
end if
6:
return F AILU RE
7:
else if d+ (T ∪ {v}) ≤ d+ (T ) であるような v ∈ V \ (N − [S] ∪ T ) が存在する then
8:
SC(S, T ∪ {v}) を呼び出す．
9:
if 結果が分離鎖 C である then
return (C, (V \ T, N + [T ]))．
10:
11:
end if
12:
return F AILU RE
13:
14:
else if |V \ (S ∪ T )| ≤ k + 1 then
return 補題 11 によって構築される幅 k 以下の S–T 分離鎖
15:
else if (S, T ) が可約である． then
16:
SC(S, T )-分割の処理を行う．
17:
18:
19:
20:
21:
22:
23:
else if d− (S) = d+ (T ) then
SC(S, T )-等しいの処理を行う．
else if d− (S) < d+ (T ) then
SC(S, T )-小さいの処理を行う．
else
SC(S, T )-大きいの処理を行う．
end if
補題 19 より正しさについては自明であり，また，補題を満たすような u, v によって S ，T を拡張するのに
かかる時間は高々 O(n) であるので，定理 2 を満たすことがわかる．
22
第5章
実装，実験
この章では本稿で記述した二つのアルゴリズムについての実験を行う．実験で得たデータについては，付録
に一部抜粋して掲載する．
5.1 実験で使用するテストデータについて
この節では，実験で使用するテストデータの種類と，その生成法について記述する．
実験では以下のテストデータを利用する．
• (1) 辺密度を指定したランダムな準完全グラフ
• (2) 強連結なランダム h 準完全グラフ
• (3) 強連結なパス幅を指定したランダム h 準完全グラフ
• (4) 強連結な辺密度を指定したランダム有向グラフ
• (5) 強連結な辺密度とパス幅を指定したランダム有向グラフ
以降，それぞれの生成法について記述する．
5.1.1 辺密度を指定したランダムな準完全グラフ
d と n を指定して，次のようにして辺密度が d の n 頂点の準完全グラフを生成する．
任意の 2 頂点 u, v について，以下のうちのどれかをランダムに実行する．
• 辺 (u, v) のみが存在する．
• 辺 (v, u) のみが存在する.
• 辺 (u, v),(v, u) の両方が存在する．
準完全グラフは最低でも辺密度が 50% であるので，2(d − 50)% の確率で 3 つ目が実行されるようにすれば
よい．
5.1.2 強連結なランダム h 準完全グラフ
h と n を指定して，次のようにしてパス幅がランダムな n 頂点の h 準完全グラフを生成する．強連結性を
満たすように全頂点を含むサイクルを生成し，準完全性を満たすように辺を追加している．最後に h 準完全グ
23
ラフになるように辺を削除する．
1. 頂点をランダムに並び替えたものを {v0 , v1 , . . . , vn } とする．
2. 強連結性を満たすように任意の i について vi から vi+1 への辺 (vn からは v0 へ辺) を追加する．
3. 全ての頂点の組 (u, v) について，以下の 3 つのどれかをランダムに実行する．
• u から v への辺と v から u への辺を追加する．
• u から v への辺を追加する．
• v から u への辺を追加する．
4. 全ての頂点から強連結性を崩さないように h 準完全性を満たす範囲で辺をランダムに削除する．
5.1.3 強連結なパス幅を指定したランダム h 準完全グラフ
h と k と n を指定して，次のようにして n 頂点のパス幅が k 以下であるような h 準完全グラフを生成する．
強連結性を満たすように全頂点を含むサイクルを生成し，準完全性を満たすように辺を追加している．その
後，幅 k 以下のパス分解を持つように辺を追加していき， 最後に h 準完全グラフになるように辺を削除する．
1. 頂点をランダムに並び替えたものを {v0 , v1 , . . . , vn } とする．
2. 強連結性を満たすように全ての i について vi から vi+1 への辺 (vn からは v0 へ辺) を追加する．
3. 準完全性を満たすように i < j となるような全ての i,j について，vi から vj への辺を追加する．
4. 次を満たすような好適なパス分解 W = (W1 , W2 , . . . , Wr ) を持つように辺をランダムに追加する．
Wi−1 \ Wi = {vj } となるような vj について，i が小さい順に並べたものを {uj1 , uj2 , . . . , ujn } とする．
これが {v0 , v1 , . . . , vn } と等しい．
5. 全ての頂点から強連結性を崩さないように h 準完全性を満たす範囲で辺をランダムに削除する．
5.1.4 強連結な辺密度を指定したランダム有向グラフ
d と n を指定して，次のようにして辺密度が d であるパス幅がランダムな n 頂点の有向グラフを生成する．
強連結性を満たすように全頂点を含むサイクルを生成し，その後ランダムに辺を追加している．
1. 頂点をランダムに並び替えたものを {v0 , v1 , . . . , vn } とする．
2. 強連結性を満たすように全ての i について vi から vi+1 への辺 (vn からは v0 へ辺) を追加する．
3. d% の確率でランダムに辺を追加する．
5.1.5 強連結な辺密度とパス幅を指定したランダム有向グラフ
d と k と n を指定して，次のようにして辺密度が d で n 頂点のパス幅が k 以下の有向グラフを生成する．
強連結性を満たすように全頂点を含むサイクルを生成し，その後幅 k 以下のパス分解を持つように辺を追加し
ている．
1. 頂点をランダムに並び替えたものを {v0 , v1 , . . . , vn } とする．
2. 強連結性を満たすように全ての i について vi から vi+1 への辺 (vn からは v0 へ辺) を追加する．
24
3. 次を満たすような好適なパス分解 W = (W1 , W2 , . . . , Wr ) を持つように辺をランダムに追加する．
Wi−1 \ Wi = {vj } となるような vj について，i が小さい順に並べたものを {uj1 , uj2 , . . . , ujn } とする．
これが {v0 , v1 , . . . , vn } と等しい．
5.2 [実験 1]3 章のアルゴリズムの実装実験
この節では，3 章で説明した Pilipczuk のアルゴリズムの実装実験について記述する．
このアルゴリズムについて書かれた論文 [11] においては，計算時間は O(2O(klogk) n2 ) となっているが，今
回は実装のデータ構造を単純にしたため，実際の計算時間は O(2O(klogk) n3 ) となっている．
実験は
• k を固定した上で，n を動かす
• n を固定したうえで，k を動かす
という 2 種類の方法であ行った．以下，実験結果について記述する．
5.2.1 k を固定したうえで n を動かす (その１)
頂点数が 1 から 10 のグラフに対して，そのグラフのパス幅が 1 以下であるかを判定するための実行時間を
計測をした．テストケースは (1) 辺密度を指定したランダム準完全グラフを使用した．頂点数，辺密度に対し
て各 10 回の実行をし，その平均をとる．
表 5.1 に密度，解別にかかった実行時間 (ミリ秒) の平均を示す．ただし，この平均には，障害を見つけた
ことで NO という解を出したケースは含まない．空欄は，10 回の実行でそのようなものがなかったことを表
す．また，図 5.1 に，そのデータをグラフにしたものを載せる．
25
表 5.1
密度，解別の実行時間の平均
YES
NO
頂点数
密度 60
密度 70
密度 80
密度 90
密度 60
密度 70
密度 80
密度 90
1
0.30
0.20
0.20
0.20
-
-
-
-
2
0.50
0.30
0.10
0.20
-
-
-
-
3
0.71
0.75
0.50
1.00
0.67
0.50
0.50
0.50
4
3.00
-
-
-
1.89
1.90
1.80
1.70
5
-
-
-
-
9.20
8.70
8.60
8.40
6
-
-
-
-
43.10
42.40
42.10
40.60
7
-
-
-
-
180.00
178.71
171.80
173.00
8
-
-
-
-
701.00
706.43
677.00
683.00
9
-
-
-
-
2720.60
2879.33
2667.50
2707.00
10
-
-
-
-
11196.00
11223.33
10856.00
-
図 5.1 密度，解別の実行時間の平均のグラフ
密度別ではほとんど違いが出なかった．また，答えが YES と NO の場合もほとんど違いが出ていない．こ
れはアルゴリズムにおいて最も時間がかかる部分が，YES の場合も NO の場合も同様に実行されているから
と考えられる．最も時間がかかる部分は列挙した分離対同士に辺を引く部分だと予想できる．
続いて各 10 回の試行のうち，障害を発見した回数について考察する．アルゴリズムにおいて (k + 1, k)-
matchin tangle を見つけるのは，バス選択子の大きさが (6k + 1)2 + (6k + 1) ときである．つまり k = 1 の
とき，グラフの頂点数が少なくとも 56 以上である必要がある．そのため，今回の実験では matching tangle
が見つかることはありえない．頂点数別の degree tangle を発見した回数を表 5.2 載せる．また，それをグラ
フにしたものを図 5.2 に載せる．
26
表 5.2
頂点数別の degree tangle 発見数
頂点数
1
2
3
4
5
6
7
8
9
10
degree tangle 発見数
0
0
0
0
0
0
22
26
29
34
図 5.2
頂点数別の degree tangle 発見数のグラフ
k の値と頂点の違いが大きいほど tangle を見つけやすいことが読み取れる．degree tangle を見つけた場合
は実行時間が O(n log n) で答えを出せる．
表 5.3 に，アルゴリズムのうち，分離対間に包含関係によって辺を引くという部分での実行時間の割合 (%)
を載せる．また，それをグラフにしたものを図 5.3 に載せる．頂点数が増えるにつれて，その割合が大きく上
昇することがわかる，10 頂点のグラフに対しては，実行時間の 90% 以上を占めている．この部分をどうにか
することで，より高速化すると思われる．
27
表 5.3 アルゴリズムに対する辺を張る部分の割合
頂点数
1
2
3
4
5
6
7
8
9
10
辺張りの割合
22.22
18.18
54.17
62.16
76.22
84.72
90.01
93.97
96.21
97.73
図 5.3
アルゴリズムに対する辺を張る部分の割合のグラフ
5.2.2 k を固定したうえで n を動かす (その 2)
頂点数が 1 から 10 のグラフに対して，そのグラフのパス幅が 1 以下であるかを判定するための実行時間を
計測をした．前回の実験で，YES という解が出る場合と，tangle を見つけずに NO という解が出る場合でも
実行時間にはほぼ差が出なかったので，テストケースには (3) パス幅を 1 以下に指定したランダム 0 準完全グ
ラフを使用する．そのため，アルゴリズムの解は YES になる．頂点数ごとに 10 回の実行をする．
実行時間 (ミリ秒) を平均したデータを表 5.4 に，そのデータをグラフにしたものを図 5.4 に載せる．固定
パラメータアルゴリズムであるので，2n の変化と比べてかなり緩くなっていて，n3 の変化とほぼ同じである
ことがわかる．
表 5.4
頂点数別の実行時間
頂点数
1
2
3
4
5
6
7
8
9
10
実行時間
0.30
0.30
0.80
2.40
10.90
51.20
129.20
259.10
437.50
697.40
頂点数
11
12
13
14
15
16
17
18
19
20
実行時間
1032.70
1434.00
1979.70
2586.10
3264.60
3895.10
4685.70
5502.10
6192.40
7039.20
28
図 5.4
頂点数による実行時間のグラフ
5.2.3 n を固定したうえで k を動かす．
頂点数を固定したグラフに対して，そのグラフのパス幅が k 以下であるかを判定するための実行時間を計測
をした．ここで，k は 1 から n − 1 である．テストケースには (3) パス幅を 1 以下に指定したランダム 0 準完
全グラフを使用する．そのため，アルゴリズムの解は YES になる．k ごとに 10 回の実行をする．
頂点数別の実行時間 (ミリ秒) のデータを表 5.5 に，そのデータをグラフにしたものを図 5.5 に載せる．
表 5.5 頂点数,k 別の実行時間
k
頂点数
1
2
3
4
5
6
7
8
6
53.2
52.8
56.7
58.2
62.5
-
-
-
7
136.5
266
274.4
291.2
313.6
322.8
-
-
8
255.8
1220.9
1260.5
1303.8
1364
1420.1
1454.5
-
9
434.5
5849.7
5895.8
6081.2
6305.4
6908.7
7116.3
8092.8
29
図 5.5
頂点数別の k による実行時間のグラフ
図 5.5 を見てみると，k については指数時間変化をするはずなのに，k = 2 のあたりで計算時間が頭打ちに
なっているように見える．これは，このアルゴリズムの構造によるものだと考えられる．このアルゴリズムで
は，ある頂点集合に含まれる頂点を 3 種類に場合分けするという動作に対して，すべての場合を保存してお
り，この部分がネックになっている．このとき，振り分ける集合の大きさが高々 5k + 2 であるため，おおよ
そ 35k+2 に依存するような計算時間になる．しかし，頂点数 n が n < 5k + 2 である場合，振り分ける集合は
n で頭打ちになってしまう．k = 1 の場合，5k + 2 = 7 であり，k = 2 の場合，5k + 2 = 12 である．そのた
め，k = 2 になった時点で，計算時間が n によって頭打ちになっていると考えられる．さらに大きな n に対し
て実行を行った場合，この頭打ちがなくなるので，大きく計算時間が増えると予想できる．
30
5.3 [実験 2]4 章のアルゴリズムの実装実験
この節では，4 章で説明した h 準完全グラフのアルゴリズムについての実装実験について記述する．
5.3.1 実装方法ごとの比較実験
ここでは，複数の実装法に対する比較実験について記述する．
以下の 3 種類の方法で実装を行い，同じグラフについてそれぞれの実行時間を比較する．
• (A):4.3 節で記述したアルゴリズム
• (B):(A) に 4.6 節で記述した工夫を加えたアルゴリズム
• (C):(B) にメモ化再帰を加えたアルゴリズム
h と k を固定したうえで頂点数が 10 から 80(10 頂点刻み) の h 準完全グラフに対して，そのグラフのパス
幅が k 以下であるかを判定するための実行時間を計測をした．アルゴリズムの構造上，k がグラフのパス幅に
近く，かつ解が N O の場合が最も時間がかかることが予想されるので，テストケースには (3) パス幅を指定し
たランダム h 準完全グラフを使用する．ここでパス幅は c を整数として k + c に指定する．c の値は，h,k,n
に対して 10 回グラフの生成を行い，そのパス幅の平均が k + 1 を超えるような最小の値とする．また，頂点
数ごとに 20 回の実行をする．
(A)，(B)，(C) 別の実行時間 (ミリ秒) の順位を表 5.6 に載せる．
表 5.6
(A),(B),(C) 別の実行時間の順位
h=0,k=1
(A)
(B)
(C)
h=5,k=1
(A)
(B)
(C)
1位
133
145
150
1位
140
118
122
2位
8
10
4
2位
17
34
29
3位
19
5
6
3位
3
8
9
h=0,k=3
(A)
(B)
(C)
h=5,k=3
(A)
(B)
(C)
1位
80
81
147
1位
64
74
148
2位
20
59
11
2位
18
68
9
3位
60
20
2
3位
78
18
3
h=0,k=5
(A)
(B)
(C)
h=5,k=5
(A)
(B)
(C)
1位
28
31
158
1位
33
36
159
2位
16
114
2
2位
4
124
0
3位
116
15
0
3位
123
0
1
実行時間が同じ場合は，同じ順位となることに注意する．この表から，k が小さいうちは，順位に大きな違
いはないけれど，k が大きくなるにつれて (A) よりも (B) が，(B) よりも (C) が早なっていることが読み取
れる．
31
続いて，(A)，(B)，(C) について，実行時間，および，最大流の実行回数の比較を行う．(A)，(B)，(C) に
ついて，実行時間の平均と，最大流の実行回数の平均を表 5.7，表 5.8 に，そのグラフを図 5.6，図 5.7 に載
せる．
表 5.7 (A)，(B)，(C) 別の実行時間
h=0,k=5
h=5,k=5
頂点数
(A)
(B)
(C)
(A)
(B)
(C)
10
0
0
0
-
-
-
20
17.5
16.5
2.8
65.40
37.40
9.20
30
151.6
113.3
7.4
479.21
294.05
11.47
40
606.7
485.3
24.1
1333.60
677.95
24.25
50
1716.7
1325.2
54.7
3473.55
1933.55
62.40
60
4136.5
2906.5
146.7
2951.65
2195.75
140.40
70
9363.2
5303.3
227.0
14616.95
8367.90
282.40
80
14133.0
11302.3
490.7
17210.45
12256.10
514.05
図 5.6 (A)，(B)，(C) 別の実行時間のグラフ
32
表 5.8 (A)，(B)，(C) 別の最大流実行回数
h=0,k=5
h=5,k=5
頂点数
(A)
(B)
(C)
(A)
(B)
(C)
10
15.0
11.6
9.8
-
-
-
20
762.8
413.8
35.2
2516.0
1218.2
54.8
30
2500.1
1580.4
59.8
9895.2
5042.9
94.7
40
3130.6
2143.3
67.5
10962.8
4921.1
92.8
50
5608.9
3705.7
80.1
11384.0
5847.6
116.3
60
5391.3
3088.9
120.1
4686.5
3107.3
121.1
70
6094.1
3513.3
102.3
12458.4
7473.7
152.3
80
5239.0
3953.7
139.6
9494.3
6097.4
172.4
図 5.7 (A)，(B)，(C) 別の最大流実行回数のグラフ
h が同じ場合，(A) よりも (B) のほうが，また (B) よりも (C) のほうが実行時間が早くなっていることがわ
かる．特に (C) については，(A)，(B) よりも大きく実行時間が下がっている．同様のことが最大流の実行回
数についてもいえる．このアルゴリズムにおいては，最大流を行う部分に最も時間がかかる．そのため，全体
の実行時間は，1 回の最大流をおこなうのにかかる時間，および最大流の実行回数に依存している．特に前者
は，頂点数に比例して長くなるため，最大流の実行回数が少なくとも，全体の実行時間が長くなることがあり
得る．
33
5.3.2 (C) に対する実験
最も実行時間が早い (C) に対しての実験を行う．4.6 節で記述した工夫とメモ化再帰を行ったものが理論的
な実行時間である b2k nO(1) に対して，どの程度早くなっているかを観察する．
実験は，
• h と k を固定して n を動かす．
• h と n を固定して k を動かす．
• k と n を固定して h を動かす．
の 3 通りについて行う．
h と k を固定して n を動かす．
n 頂点の h 準完全グラフに対して，パス幅が k であるかどうかを判定するためにかかる時間を計測する．
• h = 0，k = 1
• h = 0，k = 10
• h = 0，k = 20
• h = 5，k = 1
• h = 5，k = 10
• h = 5，k = 20
の 6 通りのケースについて n を 10 から 150 まで 10 刻みに動かして実行する．テストケースには (3) パス
幅を指定したランダム h 準完全グラフを使用する．ここでパス幅は c を整数として k + c に指定する．c の値
は，h,k,n に対して 10 回グラフの生成を行い，そのパス幅の平均が k + 1 を超えるような最小の値とする．ま
た，頂点数ごとに 10 回の実行をする．
4 章のアルゴリズムは，深さ優先であるため，解が YES であるときは，実行時間にばらつきがでると予想
できる．よって，今回の実験では，解が NO であるようなテストケースに着目する．
解が NO であるテストケースに対するアルゴリズムの実行時間 (ミリ秒) を表 5.9 に，そのグラフを図 5.8，
図 5.9 に載せる．
34
表 5.9
解が NO であるテストケースに対する実行時間 (n を変化)
h=0
h=5
頂点数
k=1
k=10
k=20
k=1
k=10
k=20
10
1.5
-
-
0.0
-
-
20
0.0
16.0
-
0.0
47
-
30
3.1
23.5
118.0
1.5
23
218.0
40
3.2
70.2
637.5
4.6
72.83333
1591.0
50
6.3
131.7
1025.9
14.0
220.125
3253.6
60
23.4
318.4
1016.0
0.0
329.2
2404.1
70
15.6
507.9
1988.3
37.4
663.1
3159.2
80
79.5
1001.6
2050.0
34.4
922.1
3625.5
90
114.0
1520.9
3811.2
61.0
1668
4784.5
100
245.0
2244.9
5282.3
154.4
2755
10709.4
110
262.2
2943.9
10341.2
100.0
3939.1
15913.6
120
418.2
5531.8
19340.9
310.5
6120
15283.4
130
722.3
6204.4
25120.7
234.1
6672.2
28503.1
140
709.9
8595.6
21769.9
1.5
9739.1
38724.4
150
1185.6
7742.2
50180.8
686.5
13539.7
46967.9
35
図 5.8
h = 0 かつ解が NO であるテストケースに対する実行時間 (n を変化) のグラフ
図 5.9
h = 0 かつ解が NO であるテストケースに対する実行時間 (n を変化) のグラフ
このアルゴリズムは，FPT アルゴリズムであるので，k を定数と考えると，n に対して多項式時間で動作す
る．図 5.8，図 5.9 より，ばらつきはあるが，多項式時間変化に近い形であることがわかる．また，同じ頂点
数であるならば k が大きいほど時間がかかっていることが読み取れる．
36
h と n を固定して k を動かす．
n 頂点の h 準完全グラフに対して，パス幅が k であるかどうかを判定するためにかかる時間を計測する．
• h = 0，n = 100
• h = 0，n = 150
• h = 10，n = 100
• h = 10，n = 150
の 4 通りのケースについて k を 1 から 30 まで 1 刻みに動かして実行する．テストケースには (3) パス幅を
指定したランダム h 準完全グラフを使用する．ここでパス幅は c を整数として k + c に指定する．c の値は，
h,k,n に対して 10 回グラフの生成を行い，そのパス幅の平均が k + 1 を超えるような最小の値とする．また，
各 k ごとに 10 回の実行をする．
解が NO であるテストケースに対するアルゴリズムの実行時間 (ミリ秒) の平均を表 5.10，表 5.11 に，そ
のグラフを図 5.10 に載せる．
表 5.10 解が NO であるテストケースに対する実行
表 5.11 解が NO であるテストケースに対する実行
時間 (k = 1 から k = 15)
時間 (k = 16 から k = 30)
h=0
h=10
h=0
h=10
k
n=100
n=150
n=100
n=150
k
n=100
n=150
n=100
n=150
1
115.4
783.1
64.0
287.0
16
5586.7
28778.9
7266.4
40330.9
2
14.2
14.2
148.2
1511.8
17
4846.9
22357.0
10434.6
37376.1
3
650.5
3087.3
646.0
1519.6
18
4943.6
27479.8
9195.4
38241.9
4
698.9
2652.1
571.1
2500.8
19
4676.8
43906.6
8545.7
78411.9
5
702.0
2614.6
733.3
2914.1
20
7098.2
51695.6
11147.2
73938.1
6
954.7
3176.6
1170.1
3688.0
21
7643.9
51669.5
15312.3
50859.3
7
847.8
4911.1
1683.3
8590.3
22
8598.7
39204.9
16347.4
94640.4
8
1837.6
6266.7
2000.0
8252.5
23
10668.8
59093.4
13331.8
89598.8
9
1691.3
5870.5
2976.6
9616.0
24
9783.3
51239.4
20699.6
77211.8
10
2700.5
9895.1
3440.0
10563.0
25
14636.0
65928.9
54302.0
73228.3
11
2943.6
14781.2
5091.8
27647.9
26
13806.1
61045.3
15657.6
127574.0
12
3107.7
13553.6
4748.8
14695.4
27
15217.0
77546.2
24835.0
104374.1
13
3803.0
23351.6
4809.7
24577.0
28
12363.1
90815.7
23913.5
173580.1
14
3488.3
20507.9
6658.1
29683.6
29
16857.8
86434.8
35989.4
149659.0
15
4636.5
29284.8
6578.2
25899.1
30
23469.7
110340.3
69992.4
134418.0
37
図 5.10
解が NO であるテストケースに対する実行時間 (k を変化) のグラフ
アルゴリズムの理論的な実行時間は b2k nO(1) であるので，k については指数時間変化するはずである．し
かし，図 5.10 を見てみると，2k の変化よりもかなり緩い変化となっている．k が近いもの同士では，実行時
間にばらつきがあるが，全体を俯瞰すると，k が大きくなるにつ入れて時間がかかるようになっていることが
読み取れる．
k と n を固定して h を動かす．
n 頂点の h 準完全グラフに対して，パス幅が k であるかどうかを判定するためにかかる時間を計測する．
• k = 10，n = 100
• k = 10，n = 150
• k = 20，n = 100
• k = 20，n = 150
の 4 通りのケースについて h を 1 から 30 まで 1 刻みに動かして実行する．テストケースには (3) パス幅を
指定したランダム h 準完全グラフを使用する．ここでパス幅は c を整数として k + c に指定する．c の値は，
h,k,n に対して 10 回グラフの生成を行い，そのパス幅の平均が k + 1 を超えるような最小の値とする．また，
各 h ごとに 10 回の実行をする．
解が NO であるテストケースに対するアルゴリズムの実行時間 (ミリ秒) の平均を表 5.12，表 5.13 に，そ
のグラフを図 5.11 に載せる．
38
表 5.12 解が NO であるテストケースに対する実行
表 5.13 解が NO であるテストケースに対する実行
時間 (h = 1 から h = 15)
時間 (h = 16 から h = 30)
k=10
k=20
k=10
k=20
h
n=100
n=150
n=100
n=150
h
n=100
n=150
n=100
n=150
1
2405.5
13128.9
9158.9
50821.9
16
4301.1
20569.0
20346.4
73127.8
2
3313.6
8386.6
6985.8
48708.2
17
4369.6
14874.9
16605.0
50616.1
3
3377.6
17275.7
7538.4
46079.6
18
4277.9
14569.0
17509.4
71623.3
4
2937.7
11140.1
11961.9
31014.6
19
4378.3
18867.6
21654.5
89094.9
5
2062.9
13684.2
11668.8
52280.5
20
4996.8
16226.1
32923.1
79889.8
6
3507.2
10847.0
10515.9
70875.8
21
4985.1
17976.0
31915.9
106460.6
7
2350.6
11452.4
15210.1
36685.0
22
3191.7
19578.1
32984.0
81519.1
8
3087.2
10425.5
9154.5
49006.9
23
4180.9
14908.9
36477.7
89916.6
9
3889.0
10151.1
12260.0
43500.8
24
4923.4
12378.5
31654.4
103537.4
10
3717.4
15432.2
11413.4
72100.1
25
5740.9
20756.1
60802.4
131701.8
11
4632.0
13402.1
12158.4
63042.9
26
5310.6
23328.2
31188.6
161242.1
12
3065.5
14530.0
15593.4
71316.6
27
6744.4
14589.1
42378.8
93745.4
13
4318.3
15017.9
15798.3
59241.2
28
5364.9
14436.3
45842.8
90152.7
14
3404.0
15599.9
20036.4
76903.6
29
6095.0
23665.2
45125.6
129898.4
15
3811.0
20547.2
18784.5
145090.9
30
4567.3
25666.8
68599.6
119614.8
39
図 5.11 解が NO であるテストケースに対する実行時間 (h を変化) のグラフ
アルゴリズムの理論的な実行時間は b2k nO(1) であり，今回テストケースに用いた h 準完全グラフは，補
題 1 より，(k, h + 2k + 1) 有界であるので，b = h + 2k + 1 である．よって h については，c を整数として，
(c + h)2k のように変化すると予想できる．しかし，実際は k = 10，k = 20 両方とも，h に近いもの同士でば
らつきが存在するが，全体を俯瞰すると h に対して，とても小さい傾きで変化していることが読み取れる．
5.3.3 (C) を用いて，グラフのパス幅を求める実験
(C) はグラフのパス幅が k 以下かどうかを判定するアルゴリズムである．この節では，これを用いてグラフ
の正確なパス幅を求めるのに，どの程度の時間がかかるかの実験を行う．
実装方法は，n 頂点グラフのパス幅が k 以下であるかという判定について，解が YES である間，k = n − 1
から 1 刻みで減少させる方法で行う．解が初めて NO になったときの k + 1 がグラフのパス幅になる．
実装上の工夫として，再帰にたいして F AILU RE の解を返すような (S, T ) のペアを覚えておく．ある k
について，(S, T ) が F AILU RE を返す，つまり，(S, T ) が k 分離可能でないとき，明らかに (S, T ) は k − 1
分解可能でないので，そのような (S, T ) を覚えておくことでより高速化することができる．
また，このアルゴリズムは，一般有向グラフに対しても (実行時間は保障されないが) 正しさが保障される
ため，実験は h 準完全グラフと一般有向グラフの両方について行う．
h 準完全グラフのパス幅を求める実験
n 頂点の h 準完全グラフのパス幅を求めるのにかかる実行時間を計測する．
• h = 0 準完全グラフ
• h = 10 準完全グラフ
• パス幅が k = 10 以下の h = 0 準完全グラフ
• パス幅が k = 20 以下の h = 0 準完全グラフ
• パス幅が k = 30 以下の h = 0 準完全グラフ
40
• パス幅が k = 10 以下の h = 10 準完全グラフ
• パス幅が k = 20 以下の h = 10 準完全グラフ
• パス幅が k = 30 以下の h = 10 準完全グラフ
の 8 通りのケースについて前者 2 つのケースは n を 10 から 60 まで 10 刻みに後者 6 つのケースは n を 10
から 150 まで 10 刻みに動かして実行する．テストケースは，(2) ランダム h 準完全グラフおよび，(3) パス
幅を指定したランダム h 準完全グラフを利用する．ここでパス幅は c を整数として k + c に指定する．c の値
は，h,k,n に対して 10 回グラフの生成を行い，そのパス幅の平均が k + 1 を超えるような最小の値とする．ま
た，頂点数ごとに 10 回の実行をする．
h 準完全グラフのパス幅を求めるのにかかった実行時間 (ミリ秒) を表 5.14 に，その中で，h が同じ者同士
を抜き出したグラフを図 5.12，図 5.13 に載せる．
表 5.14 h 準完全グラフのパス幅を求めるための時間
h=0
h=10
頂点数
ランダム
k=10
k=20
k=30
ランダム
k=10
k=20
k=30
10
1.6
1.5
0.0
0
0.0
0
0
0
20
12.5
3.2
9.5
7.8
103.0
4.7
56.2
46.9
30
192.0
7.8
40.6
162.4
1961.7
9.5
85.9
875.9
40
1509.8
107.7
62.4
357.5
25815.8
63.9
167.2
1813.6
50
8184.7
507.5
260.7
596
140167.3
220
366.6
1626.4
60
43027.8
766.1
588.2
1181.5
646170.2
587
813.3
2663.8
70
-
908.1
997.5
1333.2
-
766.4
1379.9
5058.4
80
-
2109.5
3921.2
1933.5
-
894.4
4186.3
7031.8
90
-
2423.0
2983.7
6265.7
-
5889.5
4773.1
6854
100
-
7554.2
4258.5
8274
-
7312.3
6623.2
11780.7
110
-
4981.9
8021.0
10939.7
-
10134.5
9039.5
26492.7
120
-
6643.3
8134.8
16769.4
-
3863.2
13796.4
22210.4
130
-
16499.6
17310.7
27444.6
-
10925.9
20188.9
29812.5
140
-
10134.7
26781.5
53619.7
-
43857.1
28466.4
30189
150
-
6954.1
26460.3
44163.2
-
6861.7
37450.3
74093.4
41
図 5.12 h = 0 準完全グラフのパス幅を求めるための時間
図 5.13
h = 10 準完全グラフのパス幅を求めるための時間
ばらつきはあるが，おおよそグラフのパス幅と頂点数に比例して実行時間が大きくなる傾向が読み取れる．
また，パス幅を指定しない (ランダムな) グラフに対しては，h に対する依存が大きくなっているように見え
る．ここで，図 5.14，図 5.15，図 5.16，図 5.17 に k が同じもの同士の実行時間のグラフを載せる．
42
図 5.14 パス幅を指定しないテストケースの実行時間の比較
図 5.15 k = 10 テストケースの実行時間の比較
43
図 5.16
k = 20 のテストケースの実行時間の比較
図 5.17
k = 30 のテストケースの実行時間の比較
パス幅を指定しないグラフについては，h に対する依存度が大きいことが読み取れる．逆にパス幅を指定し
たグラフについては，h に対する依存度はそこまで大きくない．
一般有向グラフのパス幅を求める実験
n 頂点の一般有向グラフのパス幅を求めるのにかかる実行時間を計測する．
• 辺密度 70% の一般有向グラフ
• 辺密度 80% の一般有向グラフ
• パス幅が k = 10 以下，辺密度 70% の一般有向グラフ
44
• パス幅が k = 20 以下，辺密度 70% の一般有向グラフ
• パス幅が k = 30 以下，辺密度 70% の一般有向グラフ
• パス幅が k = 10 以下，辺密度 80% の一般有向グラフ
• パス幅が k = 20 以下，辺密度 80% の一般有向グラフ
• パス幅が k = 30 以下，辺密度 80% の一般有向グラフ
の 8 通りのケースについて前者 2 つのケースは n を 10 から 60 まで 10 刻みに後者 6 つのケースは n を 10
から 150 まで 10 刻みに動かして実行する．テストケースは，(4) 辺密度を指定したランダム有向グラフおよ
び，(5) 辺密度とパス幅を指定したランダム有向グラフを利用する．ここでパス幅は c を整数として k + c に
指定する．c の値は，h,k,n に対して 10 回グラフの生成を行い，そのパス幅の平均が k + 1 を超えるような最
小の値とする．また，頂点数ごとに 10 回の実行をする．
一般有向グラフのパス幅を求めるのにかかった実行時間 (ミリ秒) を表 5.15 に，その中で，h が同じ者同士
を抜き出したグラフを図 5.18，図 5.19 に載せる．
表 5.15 一般有向グラフのパス幅を求めるための時間
dence=70
dence=80
頂点数
ランダム
k=10
k=20
k=30
ランダム
k=10
k=20
k=30
10
0
0.0
1.6
1.6
1.5
0.0
0
0
20
10.9
1.7
14.1
21.8
6.3
6.2
6.3
9.4
30
117
26.6
65.5
273.3
45.3
18.8
56.1
195
40
827.7
70.5
221.7
485.6
298.3
71.8
222.1
273.4
50
5141.1
213.7
730.7
1351.9
1061.4
196.7
513.5
1164.2
60
21345.3
338.8
1033.2
3925.8
3168.2
215.3
944.6
2941.6
70
-
638.7
1949.3
6493.7
-
441.6
2041.5
3383.1
80
-
967.6
3170.9
7281.3
-
864.8
3166.3
7420.4
90
-
2008.8
4284.9
10473.1
-
1578.0
4682.5
10122.3
100
-
3041.5
8403.1
17806.8
-
1670.0
5763.6
17212.5
110
-
5124.1
8343.9
27734.9
-
3707.7
8080.2
27815.7
120
-
6864.9
12078.7
32865.6
-
8582.6
15225.3
25249.8
130
-
8704.2
23345.0
52754.1
-
11468.6
13931
35033.7
140
-
15516.9
29040.5
88854.1
-
7283.0
24945.5
59224.9
150
-
20558.9
49272.0
85969.8
-
17006.5
35606.5
79527
45
図 5.18
辺密度 70% の一般有向グラフのパス幅を求めるための時間
図 5.19
辺密度 80% の一般有向グラフのパス幅を求めるための時間
h 準完全グラフと同様に，グラフのパス幅と頂点数に比例して実行時間が大きくなる傾向が読み取れる．し
かし，ばらつきは h 準完全グラフよりも小さい．ここで，図 5.20，図 5.21，図 5.22，図 5.23 に k が同じも
の同士の実行時間のグラフを載せる．
46
図 5.20 パス幅を指定しないテストケースの実行時間の比較
図 5.21
k = 10 のテストケースの実行時間の比較
47
図 5.22
k = 20 のテストケースの実行時間の比較
図 5.23
k = 30 のテストケースの実行時間の比較
h 準完全グラフにおける h と似た結果になることが読み取れる．パス幅を指定しないグラフに対しては，辺
密度に大きく依存している．逆にパス幅を指定したグラフに対しては，あまり辺密度に依存していない．
5.4 [実験 3]3 章のアルゴリズムと 4 章のアルゴリズムの比較実験
この節では，3 章のアルゴリズムと 4 章のアルゴリズムの比較実験を行う．
5.4.1 3 章の障害を含まないグラフでの実験
3 章の障害を含まないグラフに対してパス幅が k 以下かどうかを判定するのにかかる時間を計測する．
48
5.2 節の実験より，障害が存在しない時，3 章のアルゴリズムの実行時間はグラフの密度や解によって大き
く変化しない．また，4 章のアルゴリズムは，深さ優先であるため，解が YES であるほうが高速に動作する．
よってテストケースには，(3) パス幅を指定した h 準完全グラフを利用し，解が YES であるようにパス幅は
k 以下に指定する．なお，3 章のアルゴリズムは準完全グラフに対するアルゴリズムであるので，h = 0 と指
定する．
• k=1
• k=2
の 2 通りのテストケースに対して，グラフの頂点数が 5 から 12 までの 1 刻みに動かして実行する．
表 5.16 に，頂点数別の実行時間 (ミリ秒) の平均を載せる．
表 5.16 障害を含まないグラフに対しての実行時間の平均
k=1
k=2
頂点数
3章
4章
3章
4章
5
9.4
1.5
7.9
0
6
43.7
0.0
37.5
0
7
174.9
0.0
156.1
0
8
463.6
0.0
802.3
0
9
890.1
0.0
3964.9
0
10
1453.3
0.0
23841.1
0
11
2174.3
0.0
91506.1
0
12
3032.2
0.0
409713.9
0
障害が見つからない場合，3 章の理論的な計算時間は O(2O(k log k) |V (T )|2 ) である．対して 4 章のアルゴリ
ズムの理論的な計算時間は準完全グラフが (k, 2k + 1) 有界であることから，(2k + 1)2k nO(1) である．つま
り，n についての依存度は 4 章のアルゴリズムの方が大きいといえる．しかし，表 5.16 からは，明らかに 4
章のアルゴリズムの方が早いことが読み取れる．
3 章のアルゴリズムにおいては，分離対を全列挙し，それらの間に辺を引くという部分で多大な時間がか
かっている．理論的にはその個数は高々 2O(klogk) で抑えられるが，実際には，かなり大きな係数がかかって
いる．
以上のことから，4 章のアルゴリズムのほうがより実用的であると考えられる．ただし，degree tangle を
含むグラフに対しては，3 章のアルゴリズムの方が早く動作する (理論的には O(n log n)) と予想できるので，
続く節でそのようなグラフに対しての実験を行う．
5.4.2 3 章の degree tangle を含むグラフでの実験
3 章の degree tangle を含むグラフに対してパス幅が k 以下かどうかを判定するのにかかる時間を計測する．
degree tangle を含むグラフに対しては，3 章のアルゴリズムは O(n log n) で動作する．(5k + 2, k)-degree
tangle を含むグラフは以下のようにして生成する．
1. 頂点をランダムに並び替えたものを {v0 , v1 , . . . , vn } とする．
49
2. 強連結性を満たすように任意の i について vi から vi+1 への辺 (vn からは v0 へ辺) を追加する．
3. 準完全性を満たすように任意の i, j(i < j) について，vi から vj への辺を追加する．
4. 先頭の 5k + 2 個の頂点 vi (0 ≤ i ≤ 5k + 1) について，N + (vi ) ≥ n − k − 1 となるように辺を引く
このようにして生成したグラフでは，{v0 , v1 , . . . , v5k+1 } が (5k + 2, k)-degree tangle になっている．
• k=1
• k=5
• k = 10
• k = 15
の 4 通りのテストケースに対して，頂点数を 100 から 300 まで 10 刻みに動かして実行する．(5k + 2, k)-
degree tangle を含むことから，解は NO になる．
表 5.17 に，頂点別の実行時間 (ミリ秒) の平均を載せる．
表 5.17 (5k + 2, k)-degree tangle を含むグラフに対しての実行時間
k=1
k=5
k=10
k=15
頂点数
3章
4章
3章
4章
3章
4章
3章
4章
100
0
7.9
0
54.6
1.5
269.5
1.6
866.1
110
0
4.7
0
56.3
0
267.5
0
913.2
120
0
7.8
0
62.3
0
285.7
0
952.1
130
0
10.9
0
73.5
0
317
1.6
1041.2
140
0
10.9
0
76.4
0
343.9
0
1053.9
150
0
14
0
78.1
0
363.8
0
1120.9
160
1.6
12.5
0
98.4
1.6
402.7
0
1203.6
170
0
17.2
0
96.8
0
398.5
0
1320.7
180
0
20.3
0
99.8
0
416.8
0
1364.5
190
0
21.9
0
100.1
0
440.3
1.6
1362.7
200
0
28
0
113.8
0
468.5
1.6
1459.6
210
0
26.6
1.5
126.4
0
505.8
0
1501.8
220
0
29.6
0
135.7
0
526.1
0
1587.6
230
0
34.3
0
143.6
0
555.9
0
1640.5
240
0
34.3
0
179.5
1.5
574.7
0
1742.1
250
0
40.6
0
212.6
3.1
568.5
0
1742.1
260
0
45.3
1.5
203.4
1.5
615
0
1887.3
270
0
48.6
0
223.5
1.6
677.3
0
2108.7
280
0
54.7
0
236.1
0
691.4
3.1
1960.5
290
1.6
56.2
1.6
242
1.5
704
0
2024.4
300
0
62.5
1.6
256.2
0
719.4
0
2055.4
(5k + 2, k)-degree tangle を含むグラフについては，3 章のアルゴリズムの方が高速に動作することが読み
50
取れる．
しかし，もう一つの障害 (マッチング障害) は，バス選択子の大きさが (6k + 1)2 + (6k + 1) 以上の時に見つ
かるため，グラフの頂点数が最低でも 56 以上である必要がある．そのようなグラフに対して，3 章のアルゴ
リズムを適用したところ，障害を見つけるまでに最低でも 30 分以上かかる (実際には 30 分で実行を打ち切っ
た) ことが分かった．
51
第6章
むすびに
6.1 まとめ
本稿では，n 頂点の (k, b) 有界であるグラフ G と正整数 k が与えられたとき，G のパス幅が k 以下かどう
かを判定する b2k nO(1) 時間のアルゴリズムについて記述した．特に，h 準完全グラフは，(k, h + 2k + 1) 有
界であるので，このアルゴリズムは (h + 2k + 1)2k nO(1) 時間で動作する．h 準完全グラフは，準完全グラフ
をより一般化したもので，0 準完全性は準完全性と一致する．Pilipczuk[11] が n 頂点の準完全グラフのパス
幅が k 以下かどうかを判定する O(2O(klogk) n2 ) 時間アルゴリズムを考案しており，我々のアルゴリズムはこ
の結果に対して，k に対する依存度が小さく，より一般的である．また，実装実験においてもほとんどのテス
トケースに対して，我々のアルゴリズムのほうが高速に動作した．
6.2 課題
準完全グラフのうち，(5k + 2, k)-次数障害をもつようなものに対しては，Pilipczuk のアルゴリズムのほう
が高速に動作した．これは，(5k + 2, k)-次数障害が「パス幅が k より大きい証拠」であり，この障害を見つけ
ることのみについて考えると O(n log n) 時間で動作しているからである．しかし，この次数障害は準完全グ
ラフの構造に依存しており，h 準完全グラフにそのまま適用することはできない．h 準完全グラフや (k, b) 有
界なグラフにに適用できる障害を見つけることでよりアルゴリズムを高速化できると予想できる．
また，現在は h 準完全のみについて考えているが，(k, b) 有界である有用なグラフクラスが見つかれば，我々
のアルゴリズムを適用することができる．
52
謝辞
指導教員である玉木久夫教授には，研究の方向付けや詳しい議論，論文の書き方など様々な面でお世話にな
りました．心より感謝申し上げます．
また，共同研究において多くのアドバイスをいただいた学習院大学の小林靖明氏にも深く感謝いたします．
最後に，計算理論研究室で過ごした学生生活はとても充実したものでした．色々な面でお世話になった同研
究室の皆様にも深く感謝いたします．
53
参考文献
[1] H.L. Bodlaender: A Tourist Guide Through Treewidth. Acta Cybernetica 11, 1–23 (1993)
[2] H.L. Bodlaender: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM
Journal on Computing 25(6), 1305–1317 (1996)
[3] H.L. Bodlaender and T. Kloks: Efficient and constructive algorithms for the pathwidth and treewidth
of graphs. Journal of Algorithms 21(2), 358–402 (96)
[4] M. Chudnovsky, A. Fradkin, P.D. Seymour: Tournament immersion and cutwisth. Journal of Combinatorial Theory, Series B 102(1), 93–101 (2012)
[5] M. Chudnovsky, P.D. Seymour: A well-quasi-order for tournaments. Journal of Combinatorial Theory, Series B 101(1), 47–53 (2011)
[6] F.V. Fomin, M. Pilipczuk: Jungles, bundles, and fixed-parameter tractability. In: Proceedings of
24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA2013), pp. 396–413 (2013)
[7] T. Kashiwabara and T. Fujisawa: NP-completeness of the problem of finding a minimum-cliquenumber interval graph containing a given graph as a subgraph. In: Proceedings of International
Symposium on Circuits and Systems, pp. 657–660 (1979)
[8] I. Kim, P.D. Seymour: Tournament minors. CoRR. abs/1206.3135 (2012)
[9] K. Kitsunai, Y. Kobayashi, K. Komuro, H. Tamaki, T. Tano: Computing directed pathwidth in
O(1.89n ) time. In: Proceedings of the 7th International Symposium on Parameterized and Exact
Computation (IPEC2012), pp. 182–193 (2012)
[10] H. Nagamochi: Linear layouts in submodular systems. In: Proceedings of the 23rd Internal Symposium on Algorithms and Computation (ISAAC2012), pp. 475–484 (2012)
[11] M. Pilipczuk: Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings.
In: Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science
(STACS 2013), pp. 197–208 (2013)
[12] N. Robertson, P.D. Seymour: Graph minors. I. Excluding a forest. Journal of Combinatorial Theory,
Series B 35(1), 39–61 (1983)
[13] N. Robertson, P.D. Seymour: Graph minors VIII. The disjoint paths problem. Journal of Combinatorial Theory, Series B 63(1), 65–110 (1995)
[14] N. Robertson, P.D. Seymour: Graph minors XX. Wagner’s conjecture. Journal of Combinatorial
Theory, Series B 92(2), 325–257 (2004)
[15] H. Tamaki: A polynomial time algorithm for bounded directed pathwidth. In: Proceedings of 37th
International Workshop on Graph-Theoretic Concepts in Computer Science (WG2011), pp. 331-342
(2011)
54
付録 A
実験データ (一部抜粋)
[実験 1]3 章のアルゴリズムの実装実験
k を固定したうえで n を動かす (その１)
表 A.1
辺密度 60% に対する実行 (一部抜粋)
実行時間 (内訳)
頂点数
辺密度
k
解
実行時間
次数障害
分離対列挙
辺張り
到達判定
1
60
1
1
2
0
1
0
0
1
60
1
1
1
0
1
0
0
2
60
1
1
1
0
1
0
0
2
60
1
1
1
0
0
1
0
3
60
1
1
1
0
1
0
0
3
60
1
1
1
0
0
1
0
4
60
1
1
3
0
1
2
0
4
60
1
1
2
0
1
1
0
5
60
1
0
11
0
2
9
0
5
60
1
0
11
0
2
9
0
6
60
1
0
67
0
7
59
1
6
60
1
0
55
0
7
48
0
7
60
1
0
227
0
17
209
1
7
60
1
0
242
0
19
223
0
8
60
1
0
883
0
40
843
0
8
60
1
0
1030
0
44
985
1
9
60
1
0
2844
0
94
2750
0
9
60
1
-1
0
0
0
0
0
10
60
1
0
9955
0
182
9773
0
10
60
1
0
14003
0
248
13755
0
55
表 A.2
辺密度 70% に対する実行 (一部抜粋)
実行時間 (内訳)
頂点数
辺密度
k
解
実行時間
次数障害
分離対列挙
辺張り
到達判定
1
70
1
1
0
0
0
0
0
1
70
1
1
0
0
0
0
0
1
70
1
1
0
0
0
0
0
2
70
1
1
0
0
0
0
0
2
70
1
1
0
0
0
0
0
2
70
1
1
0
0
0
0
0
3
70
1
1
0
0
0
0
0
3
70
1
1
1
0
1
0
0
3
70
1
1
1
0
0
1
0
4
70
1
1
2
0
0
2
0
4
70
1
1
3
0
0
2
0
4
70
1
1
2
0
1
1
0
5
70
1
1
10
0
2
8
0
5
70
1
0
11
0
2
9
0
5
70
1
1
18
0
2
15
1
6
70
1
0
61
0
7
54
0
6
70
1
0
71
0
8
63
0
6
70
1
0
48
0
7
41
0
7
70
1
0
229
0
16
212
0
7
70
1
0
205
0
17
188
0
7
70
1
0
217
0
17
200
0
8
70
1
0
889
0
40
849
0
8
70
1
0
697
0
30
667
0
8
70
1
0
749
0
40
708
0
9
70
1
0
3883
0
103
3780
0
9
70
1
0
3422
0
103
3318
1
9
70
1
0
3871
0
106
3765
0
10
70
1
0
13178
0
247
12931
0
10
70
1
0
14673
0
250
14422
1
10
70
1
-1
0
0
0
0
0
56
表 A.3
辺密度 80% に対する実行 (一部抜粋)
実行時間 (内訳)
頂点数
辺密度
k
解
実行時間
次数障害
分離対列挙
辺張り
到達判定
1
80
1
1
1
0
0
1
0
1
80
1
1
0
0
0
0
0
1
80
1
1
0
0
0
0
0
2
80
1
1
0
0
0
0
0
2
80
1
1
0
0
0
0
0
2
80
1
1
0
0
0
0
0
3
80
1
1
1
0
0
1
0
3
80
1
1
0
0
0
0
0
3
80
1
1
1
0
1
0
0
4
80
1
1
3
0
1
2
0
4
80
1
0
3
0
1
2
0
4
80
1
1
2
0
0
2
0
5
80
1
0
11
0
2
8
1
5
80
1
0
10
0
2
8
0
5
80
1
0
9
0
2
7
0
6
80
1
0
50
0
6
44
0
6
80
1
0
58
0
6
52
0
6
80
1
0
52
0
6
46
0
7
80
1
0
253
0
16
236
1
7
80
1
0
250
0
18
231
1
7
80
1
0
257
0
16
241
0
8
80
1
0
947
0
39
908
0
8
80
1
0
804
0
37
766
1
8
80
1
0
966
0
41
925
0
9
80
1
0
3765
0
104
3661
0
9
80
1
0
3965
0
100
3865
0
9
80
1
0
3906
0
99
3807
0
10
80
1
0
12314
0
248
12066
0
10
80
1
0
12565
0
249
12316
0
10
80
1
0
16630
0
267
16363
0
57
表 A.4
辺密度 90% に対する実行 (一部抜粋)
実行時間 (内訳)
頂点数
辺密度
k
解
実行時間
次数障害
分離対列挙
辺張り
到達判定
1
90
1
1
0
0
0
0
0
1
90
1
1
1
0
1
0
0
1
90
1
1
0
0
0
0
0
2
90
1
1
1
0
1
0
0
2
90
1
1
0
0
0
0
0
2
90
1
1
0
0
0
0
0
3
90
1
1
1
0
0
1
0
3
90
1
1
1
0
0
1
0
3
90
1
1
0
0
0
0
0
4
90
1
1
2
0
1
1
0
4
90
1
0
4
0
1
1
2
4
90
1
1
2
0
1
1
0
5
90
1
1
13
0
2
11
0
5
90
1
0
9
0
2
7
0
5
90
1
1
15
0
2
13
0
6
90
1
0
61
0
6
54
1
6
90
1
0
56
0
6
50
0
6
90
1
0
46
0
7
39
0
7
90
1
0
226
0
16
210
0
7
90
1
0
243
0
17
226
0
7
90
1
0
212
0
16
196
0
8
90
1
0
869
0
31
838
0
8
90
1
0
1090
0
42
1048
0
8
90
1
-1
0
0
0
0
0
9
90
1
0
3881
0
104
3777
0
9
90
1
0
3542
0
99
3442
1
9
90
1
0
4096
0
104
3992
0
10
90
1
-1
0
0
0
0
0
10
90
1
-1
0
0
0
0
0
10
90
1
0
11591
0
258
11333
0
58
k を固定したうえで n を動かす (その 2)
表 A.5 1 から 10 頂点に対する実行 (一部抜粋)
実行時間 (内訳)
頂点数
辺密度
k
解
実行時間
次数障害
分離対列挙
辺張り
到達判定
1
70
1
1
1
0
0
0
0
1
70
1
1
1
0
0
1
0
1
70
1
1
0
0
0
0
0
2
70
1
1
1
0
1
0
0
2
70
1
1
1
0
0
0
1
2
70
1
1
0
0
0
0
0
3
70
1
1
2
0
1
1
0
3
70
1
1
1
0
0
1
0
3
70
1
1
0
0
0
0
0
4
70
1
1
2
0
0
2
0
4
70
1
1
3
0
1
2
0
4
70
1
1
2
0
1
1
0
5
70
1
1
13
0
4
9
0
5
70
1
1
10
0
1
9
0
5
70
1
1
11
0
3
8
0
6
70
1
1
51
0
5
46
0
6
70
1
1
50
0
5
45
0
6
70
1
1
51
0
5
46
0
7
70
1
1
128
0
9
119
0
7
70
1
1
135
0
9
126
0
7
70
1
1
130
0
11
119
0
8
70
1
1
255
0
15
240
0
8
70
1
1
248
0
13
235
0
8
70
1
1
256
0
14
242
0
9
70
1
1
430
0
20
410
0
9
70
1
1
423
0
20
403
0
9
70
1
1
481
0
19
462
0
10
70
1
1
692
0
26
666
0
10
70
1
1
718
0
26
692
0
10
70
1
1
718
0
24
694
0
59
表 A.6 11 から 20 頂点に対する実行 (一部抜粋)
実行時間 (内訳)
頂点数
辺密度
k
解
実行時間
次数障害
分離対列挙
辺張り
到達判定
11
70
1
1
1029
0
33
996
0
11
70
1
1
1040
0
33
1007
0
11
70
1
1
992
0
32
960
0
12
70
1
1
1417
0
40
1377
0
12
70
1
1
1462
0
41
1421
0
12
70
1
1
1470
0
42
1428
0
13
70
1
1
1984
0
50
1934
0
13
70
1
1
1913
0
50
1863
0
13
70
1
1
1870
0
48
1822
0
14
70
1
1
2637
0
59
2578
0
14
70
1
1
2565
0
59
2506
0
14
70
1
1
2479
0
58
2421
0
15
70
1
1
3469
0
67
3401
1
15
70
1
1
3177
0
82
3095
0
15
70
1
1
3135
0
68
3067
0
16
70
1
1
3823
0
79
3743
1
16
70
1
1
3815
0
79
3736
0
16
70
1
1
3945
0
78
3867
0
17
70
1
1
4534
0
90
4444
0
17
70
1
1
4645
0
108
4537
0
17
70
1
1
4513
0
92
4421
0
18
70
1
1
5503
0
105
5398
0
18
70
1
1
5516
0
105
5411
0
18
70
1
1
5429
0
106
5323
0
19
70
1
1
6223
0
118
6105
0
19
70
1
1
6377
0
119
6258
0
19
70
1
1
6199
0
119
6080
0
20
70
1
1
6903
0
132
6770
1
20
70
1
1
6869
0
134
6735
0
20
70
1
1
6852
0
151
6701
0
60
n を固定したうえで k を動かす．
表 A.7
5 頂点に対する実行 (一部抜粋)
実行時間 (内訳)
頂点数
辺密度
k
解
実行時間
次数障害
分離対列挙
辺張り
到達判定
5
70
1
1
13
0
2
11
0
5
70
1
1
12
0
2
10
0
5
70
1
1
11
0
2
9
0
5
70
1
1
13
0
4
9
0
5
70
1
1
11
0
2
9
0
5
70
1
1
10
0
1
9
0
5
70
1
1
12
0
2
10
0
5
70
1
1
11
0
2
9
0
5
70
2
1
11
0
2
9
0
5
70
2
1
12
0
2
10
0
5
70
2
1
10
0
1
9
0
5
70
2
1
11
0
2
9
0
5
70
2
1
11
0
2
9
0
5
70
2
1
12
0
2
10
0
5
70
2
1
11
0
2
9
0
5
70
2
1
11
0
2
9
0
5
70
3
1
12
0
3
9
0
5
70
3
1
12
0
2
10
0
5
70
3
1
11
0
2
9
0
5
70
3
1
13
0
2
11
0
5
70
3
1
11
0
2
9
0
5
70
3
1
11
0
2
9
0
5
70
3
1
14
0
2
11
1
5
70
3
1
11
0
1
10
0
5
70
4
1
12
0
1
11
0
5
70
4
1
11
0
2
9
0
5
70
4
1
12
0
2
10
0
5
70
4
1
13
0
2
11
0
5
70
4
1
12
0
2
10
0
5
70
4
1
11
0
2
9
0
61
表 A.8
6 頂点に対する実行 (一部抜粋)
実行時間 (内訳)
頂点数
辺密度
k
解
実行時間
次数障害
分離対列挙
辺張り
到達判定
6
70
1
1
63
0
10
51
0
6
70
1
1
57
0
9
48
0
6
70
1
1
50
0
6
44
0
6
70
1
1
51
0
7
44
0
6
70
1
1
52
0
7
45
0
6
70
1
1
52
0
6
46
0
6
70
2
1
53
0
5
48
0
6
70
2
1
53
0
7
46
0
6
70
2
1
53
0
5
48
0
6
70
2
1
54
0
6
48
0
6
70
2
1
52
0
5
47
0
6
70
2
1
54
0
5
49
0
6
70
3
1
56
0
6
50
0
6
70
3
1
57
0
5
52
0
6
70
3
1
55
0
6
49
0
6
70
3
1
69
0
5
64
0
6
70
3
1
54
0
5
49
0
6
70
3
1
55
0
5
50
0
6
70
4
1
57
0
6
51
0
6
70
4
1
57
0
5
52
0
6
70
4
1
71
0
5
66
0
6
70
4
1
55
0
5
50
0
6
70
4
1
57
0
5
52
0
6
70
4
1
57
0
5
52
0
6
70
5
1
56
0
5
51
0
6
70
5
1
58
0
5
53
0
6
70
5
1
58
0
5
53
0
6
70
5
1
59
0
6
53
0
6
70
5
1
57
0
5
52
0
6
70
5
1
82
0
11
71
0
62
表 A.9
7 頂点に対する実行 (一部抜粋)
実行時間 (内訳)
頂点数
辺密度
k
解
実行時間
次数障害
分離対列挙
辺張り
到達判定
7
70
1
1
149
0
15
133
0
7
70
1
1
140
0
12
128
0
7
70
1
1
133
0
11
122
0
7
70
1
1
134
0
11
123
0
7
70
1
1
133
0
10
123
0
7
70
2
1
265
0
17
248
0
7
70
2
1
266
0
18
248
0
7
70
2
1
266
0
16
249
1
7
70
2
1
261
0
18
243
0
7
70
2
1
265
0
18
247
0
7
70
3
1
273
0
16
257
0
7
70
3
1
283
0
19
264
0
7
70
3
1
276
0
16
260
0
7
70
3
1
268
0
16
252
0
7
70
3
1
272
0
19
253
0
7
70
4
1
295
0
16
279
0
7
70
4
1
284
0
16
268
0
7
70
4
1
278
0
16
262
0
7
70
4
1
298
0
16
282
0
7
70
4
1
281
0
16
265
0
7
70
5
1
300
0
15
285
0
7
70
5
1
322
0
20
302
0
7
70
5
1
288
0
16
272
0
7
70
5
1
338
0
25
313
0
7
70
5
1
297
0
16
281
0
7
70
6
1
335
0
16
319
0
7
70
6
1
301
0
24
277
0
7
70
6
1
341
0
26
315
0
7
70
6
1
295
0
16
279
0
7
70
6
1
333
0
16
317
0
63
表 A.10 8 頂点に対する実行 (一部抜粋)
実行時間 (内訳)
頂点数
辺密度
k
解
実行時間
次数障害
分離対列挙
辺張り
到達判定
8
70
1
1
274
0
21
252
0
8
70
1
1
263
0
14
249
0
8
70
1
1
249
0
13
236
0
8
70
1
1
255
0
14
240
1
8
70
2
1
1228
0
51
1177
0
8
70
2
1
1189
0
51
1138
0
8
70
2
1
1242
0
51
1191
0
8
70
2
1
1233
0
51
1182
0
8
70
3
1
1254
0
51
1203
0
8
70
3
1
1248
0
51
1197
0
8
70
3
1
1254
0
53
1201
0
8
70
3
1
1312
0
50
1262
0
8
70
4
1
1328
0
50
1278
0
8
70
4
1
1317
0
52
1264
1
8
70
4
1
1272
0
47
1225
0
8
70
4
1
1291
0
55
1236
0
8
70
5
1
1370
0
55
1315
0
8
70
5
1
1429
0
62
1367
0
8
70
5
1
1348
0
48
1299
1
8
70
5
1
1406
0
47
1359
0
8
70
6
1
1490
0
47
1442
1
8
70
6
1
1361
0
69
1292
0
8
70
6
1
1354
0
46
1308
0
8
70
6
1
1410
0
47
1363
0
8
70
7
1
1459
0
192
1266
0
8
70
7
1
1382
0
86
1294
1
8
70
7
1
1480
0
195
1285
0
8
70
7
1
1636
0
89
1547
0
64
表 A.11 9 頂点に対する実行 (一部抜粋)
実行時間 (内訳)
頂点数
辺密度
k
解
実行時間
次数障害
分離対列挙
辺張り
到達判定
9
70
1
1
454
0
26
427
0
9
70
1
1
428
0
18
410
0
9
70
1
1
426
0
20
406
0
9
70
2
1
5830
0
157
5673
0
9
70
2
1
5830
0
156
5674
0
9
70
2
1
5817
0
178
5639
0
9
70
2
1
5955
0
158
5797
0
9
70
3
1
5868
0
157
5711
0
9
70
3
1
5802
0
212
5590
0
9
70
3
1
5977
0
213
5764
0
9
70
4
1
5910
0
161
5749
0
9
70
4
1
5977
0
162
5815
0
9
70
4
1
5962
0
162
5800
0
9
70
4
1
6083
0
161
5922
0
9
70
5
1
6316
0
162
6154
0
9
70
5
1
6264
0
189
6075
0
9
70
5
1
6229
0
190
6039
0
9
70
5
1
6479
0
188
6290
1
9
70
6
1
6768
0
188
6580
0
9
70
6
1
6702
0
150
6552
0
9
70
6
1
6770
0
149
6621
0
9
70
6
1
6897
0
150
6747
0
9
70
7
1
6909
0
149
6760
0
9
70
7
1
7055
0
149
6906
0
9
70
7
1
7034
0
592
6441
1
9
70
7
1
6992
0
573
6419
0
9
70
8
1
7635
0
150
7484
1
9
70
8
1
7860
0
163
7697
0
9
70
8
1
8357
0
715
7642
0
9
70
8
1
8318
0
149
8169
0
65
[実験 2]4 章のアルゴリズムの実装実験
実装方法ごとの比較実験
表 A.12 h = 0，k = 1 に対する実行 (一部抜粋)
解
実行時間
最大流実行回数
h
k
n
(A)
(B)
(C)
(A)
(B)
(C)
(A)
(B)
(C)
0
1
10
0
0
0
0
0
0
8
8
8
0
1
10
0
0
0
0
0
0
16
4
4
0
1
20
0
0
0
0
0
0
0
0
0
0
1
20
0
0
0
0
0
0
27
15
15
0
1
20
0
0
0
0
0
0
0
0
0
0
1
30
0
0
0
0
0
0
0
0
0
0
1
30
0
0
0
0
0
0
0
0
0
0
1
30
0
0
0
15
0
16
63
21
21
0
1
30
0
0
0
0
0
0
55
26
26
0
1
40
0
0
0
0
0
0
0
0
0
0
1
40
0
0
0
0
0
0
0
0
0
0
1
40
0
0
0
0
0
0
0
0
0
0
1
40
0
0
0
0
0
0
0
0
0
0
1
50
0
0
0
32
46
31
48
48
48
0
1
50
0
0
0
0
0
0
0
0
0
0
1
50
0
0
0
0
0
0
0
0
0
0
1
50
0
0
0
0
0
0
0
0
0
0
1
60
0
0
0
109
47
47
109
56
56
0
1
60
0
0
0
175
62
94
148
56
56
0
1
60
0
0
0
93
78
78
59
57
57
0
1
60
0
0
0
62
78
78
58
58
58
0
1
70
0
0
0
329
156
124
171
65
65
0
1
70
0
0
0
0
0
0
0
0
0
0
1
70
0
0
0
0
0
0
0
0
0
0
1
70
0
0
0
0
0
0
0
0
0
0
1
80
0
0
0
0
0
0
0
0
0
0
1
80
0
0
0
235
234
202
91
77
77
0
1
80
0
0
0
344
202
187
135
74
74
0
1
80
0
0
0
235
203
203
91
75
75
66
表 A.13 h = 0，k = 3 に対する実行 (一部抜粋)
解
実行時間
最大流実行回数
h
k
n
(A)
(B)
(C)
(A)
(B)
(C)
(A)
(B)
(C)
0
3
10
0
0
0
0
0
0
6
6
6
0
3
10
0
0
0
0
0
0
40
14
4
0
3
20
0
0
0
15
0
0
139
80
28
0
3
20
0
0
0
0
0
0
0
0
0
0
3
20
0
0
0
0
16
0
97
81
14
0
3
30
0
0
0
32
46
15
220
207
48
0
3
30
0
0
0
16
31
0
183
124
22
0
3
30
0
0
0
0
0
0
1
1
1
0
3
30
0
0
0
31
15
16
104
100
50
0
3
40
0
0
0
78
47
0
299
141
29
0
3
40
0
0
0
15
31
31
72
72
72
0
3
40
0
0
0
0
0
0
0
0
0
0
3
40
0
0
0
94
94
15
343
255
29
0
3
50
0
0
0
0
0
0
8
4
2
0
3
50
0
0
0
0
0
0
14
6
2
0
3
50
0
0
0
0
0
0
4
2
1
0
3
50
0
0
0
125
125
47
145
116
58
0
3
60
0
0
0
327
312
171
222
218
112
0
3
60
0
0
0
79
94
94
59
59
59
0
3
60
0
0
0
546
561
125
483
435
99
0
3
60
0
0
0
0
0
0
0
0
0
0
3
70
0
0
0
1030
1030
94
674
654
59
0
3
70
0
0
0
0
16
0
19
9
2
0
3
70
0
0
0
47
47
16
84
58
21
0
3
70
0
0
0
15
16
16
192
126
18
0
3
80
0
0
0
874
812
281
244
225
76
0
3
80
0
0
0
0
0
0
0
0
0
0
3
80
0
0
0
484
531
265
150
148
74
0
3
80
0
0
0
2357
1654
265
626
436
74
67
表 A.14 h = 0，k = 5 に対する実行 (一部抜粋)
解
実行時間
最大流実行回数
h
k
n
(A)
(B)
(C)
(A)
(B)
(C)
(A)
(B)
(C)
0
5
10
1
1
1
15
0
0
5
0
0
0
5
10
1
1
1
0
0
0
8
4
4
0
5
20
0
0
0
47
15
0
1276
640
50
0
5
20
0
0
0
0
0
0
67
64
18
0
5
20
0
0
0
16
15
16
603
321
35
0
5
30
0
0
0
32
31
0
890
504
23
0
5
30
0
0
0
125
78
15
3082
1293
50
0
5
30
0
0
0
95
47
0
538
270
25
0
5
30
0
0
0
63
47
0
720
459
24
0
5
40
0
0
0
454
390
31
1971
1382
99
0
5
40
0
0
0
719
655
31
3204
3029
78
0
5
40
0
0
0
298
312
0
908
707
30
0
5
40
0
0
0
109
94
16
491
333
69
0
5
50
0
0
0
1343
1388
141
1611
1569
175
0
5
50
0
0
0
3105
1778
110
5618
3802
168
0
5
50
0
0
0
250
187
46
313
251
53
0
5
50
0
0
0
2699
2184
141
5406
3598
148
0
5
60
0
0
0
7567
6614
328
6340
4949
239
0
5
60
0
0
0
19002
12246
328
34058
14852
258
0
5
60
0
0
0
1436
1420
265
1266
1216
142
0
5
60
0
0
0
1031
686
47
1244
910
48
0
5
70
0
0
0
4275
3073
374
2772
1671
164
0
5
70
0
0
0
3075
2776
577
2199
1599
174
0
5
70
0
0
0
1795
1685
31
3152
2838
61
0
5
70
0
0
0
438
281
16
1284
758
25
0
5
80
0
0
0
61371
50045
1451
21838
17105
390
0
5
80
0
0
0
3761
3744
593
1266
1188
174
0
5
80
0
0
0
27005
22963
593
8953
7454
169
0
5
80
0
0
0
10297
6833
234
4782
3183
103
68
表 A.15 h = 5，k = 1 に対する実行 (一部抜粋)
解
実行時間
最大流実行回数
h
k
n
(A)
(B)
(C)
(A)
(B)
(C)
(A)
(B)
(C)
5
1
10
1
1
1
0
0
0
14
9
9
5
1
10
1
1
1
0
0
0
7
0
0
5
1
20
0
0
0
0
0
0
0
0
0
5
1
20
1
1
1
0
15
0
38
0
0
5
1
20
0
0
0
0
0
0
0
0
0
5
1
30
0
0
0
0
0
0
0
0
0
5
1
30
0
0
0
15
0
0
69
51
17
5
1
30
0
0
0
0
0
0
0
0
0
5
1
30
0
0
0
0
16
0
88
38
19
5
1
40
0
0
0
0
0
0
34
34
21
5
1
40
0
0
0
0
0
0
0
0
0
5
1
40
0
0
0
15
16
15
84
30
30
5
1
40
1
1
1
0
0
0
88
6
6
5
1
50
0
0
0
16
0
0
59
34
17
5
1
50
0
0
0
0
0
0
0
0
0
5
1
50
1
1
1
15
0
16
130
43
43
5
1
50
0
0
0
0
0
0
0
0
0
5
1
60
0
0
0
0
15
0
17
17
17
5
1
60
0
0
0
16
0
0
27
27
27
5
1
60
1
1
1
16
0
0
174
28
28
5
1
60
1
1
1
16
0
0
164
0
0
5
1
70
0
0
0
0
0
0
21
18
18
5
1
70
0
0
0
0
0
0
0
0
0
5
1
70
0
0
0
0
0
0
17
17
17
5
1
70
0
0
0
0
0
0
0
0
0
5
1
80
0
0
0
0
0
0
0
0
0
5
1
80
0
0
0
0
0
15
11
11
11
5
1
80
0
0
0
0
0
0
0
0
0
5
1
80
0
0
0
0
0
0
0
0
0
69
表 A.16 h = 5，k = 3 に対する実行 (一部抜粋)
解
実行時間
最大流実行回数
h
k
n
(A)
(B)
(C)
(A)
(B)
(C)
(A)
(B)
(C)
5
3
10
1
1
1
0
0
0
8
4
4
5
3
10
0
0
0
15
0
0
78
52
29
5
3
20
0
0
0
16
0
0
188
83
17
5
3
20
0
0
0
16
0
15
263
126
36
5
3
20
0
0
0
0
0
0
220
94
25
5
3
30
0
0
0
32
15
0
446
242
40
5
3
30
0
0
0
78
31
0
864
321
47
5
3
30
0
0
0
0
0
0
0
0
0
5
3
30
0
0
0
16
0
0
132
76
12
5
3
40
0
0
0
31
31
0
106
93
31
5
3
40
0
0
0
15
16
0
77
57
15
5
3
40
0
0
0
15
0
0
79
43
15
5
3
40
0
0
0
78
63
0
204
201
35
5
3
50
0
0
0
156
156
47
241
231
74
5
3
50
0
0
0
0
0
0
0
0
0
5
3
50
0
0
0
109
78
63
134
118
88
5
3
50
0
0
0
79
62
46
90
89
46
5
3
60
0
0
0
157
125
62
128
102
51
5
3
60
0
0
0
811
749
171
533
489
110
5
3
60
0
0
0
16
17
15
32
30
17
5
3
60
0
0
0
94
93
93
57
57
57
5
3
70
0
0
0
31
47
32
22
20
20
5
3
70
0
0
0
0
0
0
0
0
0
5
3
70
0
0
0
5351
4758
421
2831
2467
200
5
3
70
0
0
0
204
202
203
69
69
69
5
3
80
0
0
0
31
32
15
62
61
31
5
3
80
0
0
0
890
858
297
234
226
76
5
3
80
0
0
0
0
0
0
12
6
2
5
3
80
0
0
0
47
32
0
64
53
27
70
表 A.17 h = 5，k = 5 に対する実行 (一部抜粋)
解
実行時間
最大流実行回数
h
k
n
(A)
(B)
(C)
(A)
(B)
(C)
(A)
(B)
(C)
5
5
10
1
1
1
0
0
0
1
0
0
5
5
10
1
1
1
0
0
0
2
1
1
5
5
20
1
1
1
0
0
0
26
10
10
5
5
20
1
1
1
0
0
15
38
12
12
5
5
20
1
1
1
0
0
0
27
5
5
5
5
30
0
0
0
234
219
0
2674
1905
63
5
5
30
0
0
0
79
47
0
1052
720
54
5
5
30
0
0
0
109
63
15
1887
1005
65
5
5
30
0
0
0
234
141
15
5296
3340
112
5
5
40
0
0
0
422
296
16
5880
3220
72
5
5
40
0
0
0
125
125
16
2770
2265
55
5
5
40
0
0
0
421
234
15
4432
1976
58
5
5
40
0
0
0
1171
531
16
14335
7913
94
5
5
50
0
0
0
9860
6303
110
31962
19084
206
5
5
50
0
0
0
687
374
63
3142
1624
92
5
5
50
0
0
0
12419
7144
140
45811
20583
221
5
5
50
0
0
0
4042
1123
31
23405
6366
77
5
5
60
0
0
0
812
780
219
1076
696
150
5
5
60
0
0
0
765
312
47
1370
696
87
5
5
60
0
0
0
16
16
0
108
102
12
5
5
60
0
0
0
920
468
0
1420
895
19
5
5
70
0
0
0
6820
3837
203
6874
5056
155
5
5
70
0
0
0
5601
4321
328
8706
6362
180
5
5
70
0
0
0
6413
6302
312
5749
5160
173
5
5
70
0
0
0
12388
7223
141
6752
3892
87
5
5
80
0
0
0
2606
2481
328
2691
2258
114
5
5
80
0
0
0
6413
6396
406
1776
1762
117
5
5
80
0
0
0
47799
36925
1404
21373
14155
395
5
5
80
0
0
0
50109
23229
562
19420
11068
193
71
(C) に対する実験
h と k を固定して n を動かす．
表 A.18
h = 0，k = 1 に対する実行 (一部抜粋)
表 A.19 h = 5，k = 1 に対する実行 (一部抜粋)
h
k
n
解
実行時間
最大流実行回数
h
k
n
解
実行時間
最大流実行回数
0
1
10
0
15
0
5
1
10
0
0
15
0
1
10
0
0
0
5
1
10
0
0
7
0
1
20
0
0
0
5
1
20
0
0
36
0
1
20
0
0
0
5
1
20
0
0
0
0
1
30
0
16
26
5
1
30
0
15
28
0
1
30
0
15
28
5
1
30
0
0
23
0
1
40
0
16
34
5
1
40
0
15
38
0
1
40
0
16
36
5
1
40
0
31
76
0
1
50
0
31
47
5
1
50
0
47
45
0
1
50
0
32
44
5
1
50
0
46
47
0
1
60
0
93
58
5
1
60
0
0
0
0
1
60
0
63
55
5
1
60
0
0
0
0
1
70
0
156
67
5
1
70
0
187
68
0
1
70
0
0
0
5
1
70
0
0
0
0
1
80
0
234
78
5
1
80
0
344
78
0
1
80
0
280
78
5
1
80
0
0
0
0
1
90
0
391
87
5
1
90
0
0
0
0
1
90
0
375
86
5
1
90
0
610
84
0
1
100
0
531
91
5
1
100
0
889
98
0
1
100
0
640
96
5
1
100
0
655
95
0
1
110
0
875
108
5
1
110
0
1000
106
0
1
110
0
905
108
5
1
110
0
0
0
0
1
120
0
1623
118
5
1
120
0
1607
116
0
1
120
0
1217
114
5
1
120
0
1498
118
0
1
130
0
1779
126
5
1
130
0
0
0
0
1
130
0
1841
127
5
1
130
0
2341
126
0
1
140
0
2497
138
5
1
140
0
15
0
0
1
140
0
2324
137
5
1
140
0
0
0
0
1
150
0
2855
144
5
1
150
0
15
0
0
1
150
0
2823
143
5
1
150
0
3495
147
72
表 A.20
h = 0，k = 10 に対する実行 (一部抜粋)
表 A.21
h = 5，k = 10 に対する実行 (一部抜粋)
h
k
n
解
実行時間
最大流実行回数
h
k
n
解
実行時間
最大流実行回数
0
10
10
1
0
0
5
10
10
1
0
0
0
10
10
1
0
0
5
10
10
1
16
0
0
10
20
1
0
37
5
10
20
0
47
482
0
10
20
0
16
133
5
10
20
1
0
158
0
10
30
1
16
24
5
10
30
0
15
267
0
10
30
1
0
21
5
10
30
1
16
43
0
10
40
0
31
201
5
10
40
0
78
344
0
10
40
0
109
389
5
10
40
0
46
269
0
10
50
0
140
395
5
10
50
0
296
406
0
10
50
0
46
193
5
10
50
0
359
611
0
10
60
0
157
183
5
10
60
0
313
579
0
10
60
0
250
298
5
10
60
0
436
384
0
10
70
0
468
270
5
10
70
0
1123
680
0
10
70
0
328
373
5
10
70
0
515
291
0
10
80
0
578
251
5
10
80
0
1638
610
0
10
80
0
297
364
5
10
80
0
1498
521
0
10
90
0
1296
409
5
10
90
0
2873
709
0
10
90
0
2746
680
5
10
90
0
1997
469
0
10
100
0
2622
435
5
10
100
0
2605
484
0
10
100
0
1856
346
5
10
100
0
3557
674
0
10
110
0
4260
711
5
10
110
0
2232
533
0
10
110
0
6443
833
5
10
110
0
4789
603
0
10
120
0
10327
1004
5
10
120
0
7722
775
0
10
120
0
3447
432
5
10
120
0
12714
1174
0
10
130
0
10312
750
5
10
130
0
22464
1317
0
10
130
0
5460
488
5
10
130
0
12043
881
0
10
140
0
13634
776
5
10
140
0
15070
1010
0
10
140
0
16333
944
5
10
140
0
21793
1200
0
10
150
0
23635
1179
5
10
150
0
28410
1234
0
10
150
0
12121
625
5
10
150
0
18596
828
73
表 A.22
h = 0，k = 20 に対する実行 (一部抜粋)
表 A.23
h = 5，k = 20 に対する実行 (一部抜粋)
h
k
n
解
実行時間
最大流実行回数
h
k
n
解
実行時間
最大流実行回数
0
20
10
1
0
0
5
20
10
1
0
0
0
20
10
1
0
0
5
20
10
1
0
0
0
20
20
1
0
0
5
20
20
1
0
0
0
20
20
1
0
0
5
20
20
1
0
0
0
20
30
0
140
788
5
20
30
0
218
1246
0
20
30
0
78
462
5
20
30
1
32
128
0
20
40
1
188
452
5
20
40
0
2480
4942
0
20
40
0
702
1512
5
20
40
0
3198
7520
0
20
50
0
1575
1903
5
20
50
0
4104
4011
0
20
50
0
1888
2355
5
20
50
0
4009
4773
0
20
60
0
1561
1503
5
20
60
0
2497
2382
0
20
60
0
1342
1581
5
20
60
0
2137
1693
0
20
70
0
2168
2123
5
20
70
0
4572
2919
0
20
70
0
4088
2175
5
20
70
0
6256
4620
0
20
80
0
1202
1084
5
20
80
0
5460
2233
0
20
80
0
5273
3053
5
20
80
0
2855
1845
0
20
90
0
3806
2014
5
20
90
0
6068
1964
0
20
90
0
5788
1899
5
20
90
0
7613
2757
0
20
100
0
3308
1220
5
20
100
0
11857
3284
0
20
100
0
4774
1577
5
20
100
0
24102
4367
0
20
110
0
14555
2522
5
20
110
0
25459
4486
0
20
110
0
13572
2628
5
20
110
0
29593
4880
0
20
120
0
27941
3739
5
20
120
0
42106
4584
0
20
120
0
31232
3370
5
20
120
0
22994
2815
0
20
130
0
34368
3109
5
20
130
0
37269
4352
0
20
130
0
27316
2913
5
20
130
0
42292
3899
0
20
140
0
23665
2163
5
20
140
0
26988
2833
0
20
140
0
11154
1251
5
20
140
0
107672
6421
0
20
150
0
115377
5235
5
20
150
0
91807
4822
0
20
150
0
57440
2858
5
20
150
0
59607
3659
74
h と n を固定して k を動かす．
表 A.24
h = 0，n = 100，k = 1 から k = 15 に対
表 A.25
する実行 (一部抜粋)
h = 0，n = 100，k = 16 から k = 30 に
対する実行 (一部抜粋)
h
k
n
解
実行時間
最大流実行回数
h
k
n
解
実行時間
最大流実行回数
0
1
100
0
624
98
0
16
100
0
7770
1864
0
1
100
0
530
95
0
16
100
0
9157
2030
0
2
100
0
16
24
0
17
100
0
8097
1955
0
2
100
0
0
2
0
17
100
0
8330
1943
0
3
100
0
1372
222
0
18
100
0
10187
2678
0
3
100
0
624
107
0
18
100
0
5944
1357
0
4
100
0
1747
248
0
19
100
0
5226
2262
0
4
100
0
1435
237
0
19
100
0
7426
1619
0
5
100
0
1560
291
0
20
100
0
9844
2254
0
5
100
0
1498
251
0
20
100
0
12371
3087
0
6
100
0
1124
232
0
21
100
0
9453
2876
0
6
100
0
1436
311
0
21
100
0
10327
3429
0
7
100
0
2262
483
0
22
100
0
10374
3569
0
7
100
0
1560
405
0
22
100
0
14914
4880
0
8
100
0
3837
728
0
23
100
0
13137
3413
0
8
100
0
1544
315
0
23
100
0
11700
3367
0
9
100
0
5054
725
0
24
100
0
18423
3865
0
9
100
0
1981
392
0
24
100
0
10062
5168
0
10
100
0
2964
511
0
25
100
0
17877
5366
0
10
100
0
8050
1443
0
25
100
0
21107
7446
0
11
100
0
5055
959
0
26
100
0
21419
7087
0
11
100
0
5585
1111
0
26
100
0
21886
8062
0
12
100
0
5805
1210
0
27
100
0
19531
5330
0
12
100
0
3042
835
0
27
100
0
33681
7253
0
13
100
0
8081
1394
0
28
100
0
21201
5587
0
13
100
0
9859
1771
0
28
100
0
17519
5219
0
14
100
0
6630
1050
0
29
100
0
21435
5882
0
14
100
0
5335
1102
0
29
100
0
25974
8628
0
15
100
0
10611
1978
0
30
100
0
11576
4830
0
15
100
0
7426
1531
0
30
100
0
111509
24973
75
表 A.26
h = 0，n = 150，k = 1 から k = 15 に対
表 A.27
する実行 (一部抜粋)
h = 0，n = 150，k = 16 から k = 30 に
対する実行 (一部抜粋)
h
k
n
解
実行時間
最大流実行回数
h
k
n
解
実行時間
最大流実行回数
0
1
150
0
2637
147
0
16
150
0
50731
2404
0
1
150
0
2683
147
0
16
150
0
46348
2737
0
2
150
0
0
1
0
17
150
0
42948
2483
0
2
150
0
15
8
0
17
150
0
32589
1863
0
3
150
0
2839
154
0
18
150
0
40155
2470
0
3
150
0
6443
322
0
18
150
0
41746
2771
0
4
150
0
3525
489
0
19
150
0
42480
2916
0
4
150
0
3837
198
0
19
150
0
127766
5433
0
5
150
0
3495
197
0
20
150
0
92930
5139
0
5
150
0
7160
330
0
20
150
0
141726
7473
0
6
150
0
6834
384
0
21
150
0
102462
5204
0
6
150
0
6084
464
0
21
150
0
92120
5131
0
7
150
0
7223
403
0
22
150
0
54196
3774
0
7
150
0
13229
611
0
22
150
0
49312
4647
0
8
150
0
11856
672
0
23
150
0
75192
6050
0
8
150
0
10187
581
0
23
150
0
103490
6777
0
9
150
0
10079
557
0
24
150
0
93756
6810
0
9
150
0
11248
622
0
24
150
0
86628
6302
0
10
150
0
10655
630
0
25
150
0
82664
8962
0
10
150
0
10951
647
0
25
150
0
123163
8352
0
11
150
0
16676
934
0
26
150
0
87190
7100
0
11
150
0
56768
2429
0
26
150
0
135127
8832
0
12
150
0
33899
1800
0
27
150
0
160368
9376
0
12
150
0
17191
963
0
27
150
0
100089
6771
0
13
150
0
23588
1336
0
28
150
0
119200
8382
0
13
150
0
21840
1441
0
28
150
0
123599
9813
0
14
150
0
30264
1634
0
29
150
0
145019
12224
0
14
150
0
32152
1607
0
29
150
0
102212
10710
0
15
150
0
72557
3744
0
30
150
0
165095
11801
0
15
150
0
41700
2434
0
30
150
0
219523
15791
76
表 A.28
h = 10，n = 100，k = 1 から k = 15 に
表 A.29 h = 10，n = 150，k = 16 から k = 30 に
対する実行 (一部抜粋)
対する実行 (一部抜粋)
h
k
n
解
実行時間
最大流実行回数
h
k
n
解
実行時間
最大流実行回数
10
1
100
0
624
98
10
16
100
0
14571
3178
10
1
100
0
16
12
10
16
100
0
11980
3203
10
2
100
0
749
98
10
17
100
0
21107
3968
10
2
100
0
593
97
10
17
100
0
21091
4132
10
3
100
0
1419
219
10
18
100
0
18080
3457
10
3
100
0
1264
201
10
18
100
0
21388
4181
10
4
100
0
1545
226
10
19
100
0
13104
4783
10
4
100
0
1888
290
10
19
100
0
22791
4596
10
5
100
0
1435
268
10
20
100
0
15257
3272
10
5
100
0
827
167
10
20
100
0
19921
6075
10
6
100
0
1592
320
10
21
100
0
25928
6658
10
6
100
0
2574
431
10
21
100
0
19017
4757
10
7
100
0
2029
361
10
22
100
0
25335
7314
10
7
100
0
2293
447
10
22
100
0
22620
5395
10
8
100
0
2887
525
10
23
100
0
17519
5277
10
8
100
0
3198
633
10
23
100
0
15070
6077
10
9
100
0
3120
789
10
24
100
0
36505
6335
10
9
100
0
6116
893
10
24
100
0
31216
10630
10
10
100
0
4899
814
10
25
100
0
37939
11043
10
10
100
0
4399
777
10
25
100
0
24742
7433
10
11
100
0
12776
2035
10
26
100
0
26256
11414
10
11
100
0
6583
1085
10
26
100
0
19016
5795
10
12
100
0
12106
2121
10
27
100
0
35505
6369
10
12
100
0
5429
1102
10
27
100
0
30747
7663
10
13
100
0
11076
2004
10
28
100
0
29890
7566
10
13
100
0
7208
1708
10
28
100
0
35303
9820
10
14
100
0
12917
2788
10
29
100
0
33229
9766
10
14
100
0
12261
2475
10
29
100
0
51293
12984
10
15
100
0
13073
3051
10
30
100
0
92711
15472
10
15
100
0
11810
2534
10
30
100
0
102508
11271
77
表 A.30
h = 10，n = 150，k = 1 から k = 15 に
表 A.31 h = 10，n = 150，k = 16 から k = 30 に
対する実行 (一部抜粋)
対する実行 (一部抜粋)
h
k
n
解
実行時間
最大流実行回数
h
k
n
解
実行時間
最大流実行回数
10
1
150
0
327
73
10
16
150
0
60232
4188
10
1
150
0
2418
138
10
16
150
0
60122
2955
10
2
150
0
3074
144
10
17
150
0
53415
2748
10
2
150
0
3291
173
10
17
150
0
73304
3520
10
3
150
0
3291
161
10
18
150
0
43539
2562
10
3
150
0
3307
159
10
18
150
0
97594
5830
10
4
150
0
7676
368
10
19
150
0
141554
7263
10
4
150
0
3651
164
10
19
150
0
76128
4247
10
5
150
0
7504
362
10
20
150
0
115317
6313
10
5
150
0
3869
228
10
20
150
0
131212
7067
10
6
150
0
6085
393
10
21
150
0
84302
5873
10
6
150
0
9937
450
10
21
150
0
75458
5812
10
7
150
0
12496
631
10
22
150
0
108889
6955
10
7
150
0
11606
497
10
22
150
0
140151
8080
10
8
150
0
10390
652
10
23
150
0
207917
11400
10
8
150
0
13307
679
10
23
150
0
150649
9319
10
9
150
0
23042
1074
10
24
150
0
158887
10155
10
9
150
0
19344
933
10
24
150
0
100089
7392
10
10
150
0
17239
872
10
25
150
0
83132
5552
10
10
150
0
18049
822
10
25
150
0
131492
8199
10
11
150
0
28892
1327
10
26
150
0
136189
12072
10
11
150
0
34585
1467
10
26
150
0
129028
8543
10
12
150
0
18548
1070
10
27
150
0
115253
8725
10
12
150
0
20405
1501
10
27
150
0
124473
9715
10
13
150
0
25615
1289
10
28
150
0
440545
24873
10
13
150
0
36628
1934
10
28
150
0
203986
15416
10
14
150
0
25554
1615
10
29
150
0
164908
12555
10
14
150
0
38813
2003
10
29
150
0
431887
19856
10
15
150
0
38892
2312
10
30
150
0
142866
13757
10
15
150
0
35474
2303
10
30
150
0
272298
13213
78
k と n を固定して h を動かす．
表 A.32 k = 10，n = 100，h = 1 から h = 15 に
表 A.33
対する実行 (一部抜粋)
対する実行 (一部抜粋)
k = 10，n = 100，h = 16 から h = 30 に
h
k
n
解
実行時間
最大流実行回数
h
k
n
解
実行時間
最大流実行回数
1
10
100
0
6567
887
16
10
100
0
5398
855
1
10
100
0
3525
700
16
10
100
0
4040
750
2
10
100
0
7614
996
17
10
100
0
5975
1037
2
10
100
0
4805
686
17
10
100
0
7863
1137
3
10
100
0
4744
820
18
10
100
0
9470
1665
3
10
100
0
8767
1172
18
10
100
0
6911
1279
4
10
100
0
6427
972
19
10
100
0
5413
1337
4
10
100
0
4586
698
19
10
100
0
7706
1624
5
10
100
0
3806
661
20
10
100
0
8705
1590
5
10
100
0
6459
969
20
10
100
0
11590
2189
6
10
100
0
4073
574
21
10
100
0
7661
1345
6
10
100
0
7941
1088
21
10
100
0
4555
1015
7
10
100
0
4071
615
22
10
100
0
6583
1445
7
10
100
0
2886
650
22
10
100
0
5600
1449
8
10
100
0
4789
844
23
10
100
0
6646
1399
8
10
100
0
4540
698
23
10
100
0
8408
1576
9
10
100
0
8830
1452
24
10
100
0
5898
1277
9
10
100
0
4867
832
24
10
100
0
6911
1836
10
10
100
0
4025
675
25
10
100
0
6208
1300
10
10
100
0
3728
550
25
10
100
0
10187
1856
11
10
100
0
7552
1253
26
10
100
0
9268
1999
11
10
100
0
4259
668
26
10
100
0
5882
1214
12
10
100
0
5164
790
27
10
100
0
9532
1758
12
10
100
0
4368
673
27
10
100
0
8580
1815
13
10
100
0
5741
937
28
10
100
0
13073
2498
13
10
100
0
9017
1280
28
10
100
0
9220
1964
14
10
100
0
5148
846
29
10
100
0
10406
1995
14
10
100
0
4040
752
29
10
100
0
9391
1863
15
10
100
0
6147
1124
30
10
100
0
7098
1604
15
10
100
0
4274
868
30
10
100
0
7332
1634
79
表 A.34 k = 10，n = 150，h = 1 から h = 15 に
表 A.35
対する実行 (一部抜粋)
対する実行 (一部抜粋)
k = 10，n = 150，h = 16 から h = 30 に
h
k
n
解
実行時間
最大流実行回数
h
k
n
解
実行時間
最大流実行回数
1
10
150
0
22401
1326
16
10
150
0
22214
1284
1
10
150
0
24851
1131
16
10
150
0
42838
1766
2
10
150
0
18939
782
17
10
150
0
23915
1333
2
10
150
0
16411
1013
17
10
150
0
17020
988
3
10
150
0
16380
829
18
10
150
0
38470
1782
3
10
150
0
21154
1165
18
10
150
0
23463
1223
4
10
150
0
11903
720
19
10
150
0
30749
1930
4
10
150
0
37394
1494
19
10
150
0
20872
1170
5
10
150
0
23370
1057
20
10
150
0
15039
892
5
10
150
0
18923
1117
20
10
150
0
29625
1564
6
10
150
0
10749
608
21
10
150
0
21170
1103
6
10
150
0
21075
903
21
10
150
0
15428
957
7
10
150
0
43994
1907
22
10
150
0
24181
1760
7
10
150
0
20499
1026
22
10
150
0
22792
1305
8
10
150
0
19531
1064
23
10
150
0
23509
1293
8
10
150
0
22948
1162
23
10
150
0
23229
1286
9
10
150
0
23666
1306
24
10
150
0
22058
1201
9
10
150
0
14492
1033
24
10
150
0
18985
1221
10
10
150
0
12964
859
25
10
150
0
30156
1425
10
10
150
0
26738
1322
25
10
150
0
32230
1510
11
10
150
0
21341
1017
26
10
150
0
25709
1217
11
10
150
0
22027
1106
26
10
150
0
36114
1936
12
10
150
0
22512
1204
27
10
150
0
21886
1186
12
10
150
0
26161
1404
27
10
150
0
25818
1366
13
10
150
0
39593
1644
28
10
150
0
23290
1182
13
10
150
0
15538
937
28
10
150
0
30326
1646
14
10
150
0
20248
1163
29
10
150
0
43477
1963
14
10
150
0
21653
1139
29
10
150
0
38174
1970
15
10
150
0
26974
1211
30
10
150
0
51279
2840
15
10
150
0
48079
2214
30
10
150
0
29250
1463
80
表 A.36 k = 20，n = 100，h = 1 から h = 15 に
表 A.37
対する実行 (一部抜粋)
対する実行 (一部抜粋)
k = 20，n = 100，h = 16 から h = 30 に
h
k
n
解
実行時間
最大流実行回数
h
k
n
解
実行時間
最大流実行回数
1
20
100
0
12948
2817
16
20
100
0
39733
9477
1
20
100
0
11809
3724
16
20
100
0
33228
7048
2
20
100
0
9501
2986
17
20
100
0
18939
5816
2
20
100
0
8408
2293
17
20
100
0
31761
8548
3
20
100
0
10983
3450
18
20
100
0
28501
5436
3
20
100
0
8736
1968
18
20
100
0
26754
6443
4
20
100
0
20451
4513
19
20
100
0
43603
9099
4
20
100
0
15553
4209
19
20
100
0
21996
6824
5
20
100
0
10343
2220
20
20
100
0
31310
8315
5
20
100
0
19890
4239
20
20
100
0
58515
11834
6
20
100
0
16396
4213
21
20
100
0
62401
9848
6
20
100
0
19562
4943
21
20
100
0
24273
6168
7
20
100
0
29532
6832
22
20
100
0
78844
12717
7
20
100
0
30716
6096
22
20
100
0
71776
14674
8
20
100
0
14180
3780
23
20
100
0
58547
11429
8
20
100
0
10608
2921
23
20
100
0
64693
16210
9
20
100
0
24275
4951
24
20
100
0
45833
10154
9
20
100
0
10405
4144
24
20
100
0
54413
13277
10
20
100
0
15132
4838
25
20
100
0
66535
16589
10
20
100
0
21434
5133
25
20
100
0
112258
35447
11
20
100
0
15023
4373
26
20
100
0
39828
13539
11
20
100
0
17300
4144
26
20
100
0
62026
13163
12
20
100
0
20997
4446
27
20
100
0
86659
16678
12
20
100
0
24071
4780
27
20
100
0
72166
13338
13
20
100
0
17052
4645
28
20
100
0
56925
11549
13
20
100
0
42073
8461
28
20
100
0
104957
18868
14
20
100
0
27925
9148
29
20
100
0
50826
13090
14
20
100
0
30763
6507
29
20
100
0
115159
32068
15
20
100
0
27035
5451
30
20
100
0
125284
33768
15
20
100
0
22152
5282
30
20
100
0
88124
21251
81
表 A.38 k = 20，n = 150，h = 1 から h = 15 に
表 A.39
対する実行 (一部抜粋)
対する実行 (一部抜粋)
k = 20，n = 150，h = 16 から h = 30 に
h
k
n
解
実行時間
最大流実行回数
h
k
n
解
実行時間
最大流実行回数
1
20
150
0
74771
4212
16
20
150
0
131118
8587
1
20
150
0
143271
7610
16
20
150
0
105206
6683
2
20
150
0
80231
4520
17
20
150
0
81029
4901
2
20
150
0
75582
4509
17
20
150
0
61121
5361
3
20
150
0
66752
3835
18
20
150
0
133427
9452
3
20
150
0
86237
4413
18
20
150
0
106267
6493
4
20
150
0
35927
2837
19
20
150
0
138887
9455
4
20
150
0
43275
3162
19
20
150
0
126813
8049
5
20
150
0
92852
5411
20
20
150
0
98967
7712
5
20
150
0
87875
4865
20
20
150
0
146921
10636
6
20
150
0
84536
4753
21
20
150
0
191989
11808
6
20
150
0
132506
6605
21
20
150
0
120978
6562
7
20
150
0
62885
3794
22
20
150
0
104537
6442
7
20
150
0
50997
3241
22
20
150
0
133209
7056
8
20
150
0
137639
7704
23
20
150
0
147685
9870
8
20
150
0
56472
4004
23
20
150
0
154846
10221
9
20
150
0
66128
4221
24
20
150
0
265903
15196
9
20
150
0
55614
3540
24
20
150
0
121119
7323
10
20
150
0
129418
7149
25
20
150
0
183347
11241
10
20
150
0
80964
4509
25
20
150
0
288772
15444
11
20
150
0
124223
7288
26
20
150
0
202317
13012
11
20
150
0
105643
6009
26
20
150
0
307196
15632
12
20
150
0
168137
8616
27
20
150
0
286869
18155
12
20
150
0
110620
8098
27
20
150
0
120510
8486
13
20
150
0
71167
4607
28
20
150
0
159167
12452
13
20
150
0
100667
6560
28
20
150
0
120292
8035
14
20
150
0
184815
10753
29
20
150
0
345323
18199
14
20
150
0
101962
6108
29
20
150
0
188495
10890
15
20
150
0
158451
10125
30
20
150
0
160307
8820
15
20
150
0
395772
20346
30
20
150
0
162583
10587
82
(C) を用いて，グラフのパス幅を求める実験
h 準完全グラフのパス幅を求める実験
表 A.40
パス幅ランダムな h = 0 準完全グラフのパ
表 A.41
パス幅ランダムな h = 10 準完全グラフの
パス幅を求める時間 (一部抜粋)
ス幅を求める時間 (一部抜粋)
h
k
n
パス幅
実行時間
h
k
n
パス幅
実行時間
0
10
10
5
16
10
10
10
3
0
0
10
10
6
0
10
10
10
3
0
0
10
10
6
0
10
10
10
1
0
0
10
10
5
0
10
10
10
3
0
0
10
10
6
0
10
10
10
3
0
0
20
20
14
16
10
20
20
10
94
0
20
20
14
0
10
20
20
10
93
0
20
20
14
15
10
20
20
9
79
0
20
20
14
16
10
20
20
10
78
0
20
20
13
15
10
20
20
9
78
0
30
30
23
218
10
30
30
20
2199
0
30
30
23
141
10
30
30
19
1436
0
30
30
23
218
10
30
30
19
1795
0
30
30
23
172
10
30
30
18
1171
0
30
30
21
140
10
30
30
18
2404
0
40
40
31
1530
10
40
40
28
8503
0
40
40
31
1218
10
40
40
29
34118
0
40
40
31
1483
10
40
40
28
13074
0
40
40
32
1889
10
40
40
29
54523
0
40
40
32
1779
10
40
40
28
22606
0
50
50
41
9158
10
50
50
39
133803
0
50
50
40
5976
10
50
50
39
200805
0
50
50
41
12044
10
50
50
38
58282
0
50
50
41
7864
10
50
50
38
91401
0
50
50
41
9455
10
50
50
38
146158
0
60
60
50
40624
10
60
60
48
788770
0
60
60
50
47784
10
60
60
48
436693
0
60
60
50
42434
10
60
60
47
598543
0
60
60
50
38783
10
60
60
48
587405
0
60
60
50
59905
10
60
60
48
601663
83
表 A.42
パス幅 10 以下，h = 0 準完全グラフのパ
表 A.43
ス幅を求める時間 (一部抜粋)
パス幅 10 以下，h = 10 準完全グラフのパ
ス幅を求める時間 (一部抜粋)
h
k
n
パス幅
実行時間
h
k
n
パス幅
実行時間
0
10
10
2
0
10
10
10
1
0
0
10
10
2
0
10
10
10
1
0
0
10
20
4
0
10
10
20
2
0
0
10
20
2
16
10
10
20
4
15
0
10
30
3
16
10
10
30
4
0
0
10
30
4
0
10
10
30
8
16
0
10
40
9
16
10
10
40
6
281
0
10
40
8
140
10
10
40
7
31
0
10
50
9
2013
10
10
50
8
94
0
10
50
7
1233
10
10
50
8
218
0
10
60
9
1279
10
10
60
5
63
0
10
60
9
47
10
10
60
9
47
0
10
70
7
156
10
10
70
9
4946
0
10
70
5
187
10
10
70
9
157
0
10
80
9
16504
10
10
80
9
484
0
10
80
6
156
10
10
80
8
3932
0
10
90
9
14119
10
10
90
8
5211
0
10
90
9
3199
10
10
90
7
10125
0
10
100
9
34134
10
10
100
9
20077
0
10
100
9
3230
10
10
100
8
6272
0
10
110
9
34881
10
10
110
9
48220
0
10
110
9
516
10
10
110
9
329
0
10
120
9
26334
10
10
120
9
11997
0
10
120
9
640
10
10
120
9
1764
0
10
130
9
123818
10
10
130
9
60264
0
10
130
8
2045
10
10
130
9
3402
0
10
140
9
4915
10
10
140
9
35491
0
10
140
9
26318
10
10
140
9
749
0
10
150
9
2232
10
10
150
9
17535
0
10
150
9
11374
10
10
150
8
9969
84
表 A.44
パス幅 20 以下，h = 0 準完全グラフのパ
表 A.45
ス幅を求める時間 (一部抜粋)
パス幅 20 以下，h = 10 準完全グラフのパ
ス幅を求める時間 (一部抜粋)
h
k
n
パス幅
実行時間
h
k
n
パス幅
実行時間
0
20
10
7
0
10
20
10
1
0
0
20
10
5
0
10
20
10
1
0
0
20
20
12
16
10
20
20
10
125
0
20
20
13
0
10
20
20
10
109
0
20
30
13
47
10
20
30
10
141
0
20
30
11
16
10
20
30
10
125
0
20
40
13
62
10
20
40
11
203
0
20
40
13
31
10
20
40
12
202
0
20
50
13
592
10
20
50
12
250
0
20
50
13
157
10
20
50
12
592
0
20
60
13
827
10
20
60
13
1653
0
20
60
14
1623
10
20
60
13
1544
0
20
70
14
1686
10
20
70
13
1388
0
20
70
14
1296
10
20
70
14
2591
0
20
80
14
4228
10
20
80
14
6116
0
20
80
14
4478
10
20
80
14
10078
0
20
90
14
5866
10
20
90
14
6943
0
20
90
13
1467
10
20
90
14
8519
0
20
100
14
5399
10
20
100
14
14743
0
20
100
14
5227
10
20
100
14
11654
0
20
110
15
7942
10
20
110
14
9658
0
20
110
15
10250
10
20
110
14
11170
0
20
120
14
12029
10
20
120
14
16725
0
20
120
14
14680
10
20
120
13
12107
0
20
130
14
27878
10
20
130
14
26115
0
20
130
15
22168
10
20
130
14
36864
0
20
140
15
30904
10
20
140
15
63774
0
20
140
15
47129
10
20
140
14
30499
0
20
150
14
66379
10
20
150
14
58750
0
20
150
14
28768
10
20
150
14
79436
85
表 A.46
パス幅 30 以下，h = 0 準完全グラフのパ
表 A.47
ス幅を求める時間 (一部抜粋)
パス幅 30 以下，h = 10 準完全グラフのパ
ス幅を求める時間 (一部抜粋)
h
k
n
パス幅
実行時間
h
k
n
パス幅
実行時間
0
30
10
6
0
10
30
10
2
0
0
30
10
6
0
10
30
10
2
0
0
30
20
12
0
10
30
20
9
31
0
30
20
14
0
10
30
20
9
31
0
30
30
19
109
10
30
30
17
1405
0
30
30
17
125
10
30
30
17
1717
0
30
40
20
266
10
30
40
16
2076
0
30
40
18
250
10
30
40
17
3994
0
30
50
17
436
10
30
50
18
2668
0
30
50
19
592
10
30
50
17
3496
0
30
60
19
781
10
30
60
20
5398
0
30
60
18
2996
10
30
60
18
3386
0
30
70
21
1249
10
30
70
19
8721
0
30
70
20
1156
10
30
70
19
9423
0
30
80
20
3261
10
30
80
19
11217
0
30
80
20
2621
10
30
80
20
9782
0
30
90
20
9485
10
30
90
19
12559
0
30
90
20
9315
10
30
90
20
7941
0
30
100
20
12762
10
30
100
20
12138
0
30
100
21
12278
10
30
100
19
20718
0
30
110
20
11732
10
30
110
20
23635
0
30
110
20
15508
10
30
110
21
54226
0
30
120
20
19828
10
30
120
20
10313
0
30
120
21
12309
10
30
120
21
57502
0
30
130
20
37706
10
30
130
20
41341
0
30
130
21
21607
10
30
130
20
40779
0
30
140
21
49078
10
30
140
21
75942
0
30
140
21
63711
10
30
140
21
15461
0
30
150
21
88750
10
30
150
21
113397
0
30
150
21
33869
10
30
150
21
100076
86
一般有向グラフのパス幅を求める実験
表 A.48
パス幅ランダム，辺密度 70% の一般有向
表 A.49 パス幅ランダム，辺密度 80% の一般有向
グラフのパス幅を求める時間 (一部抜粋)
グラフのパス幅を求める時間 (一部抜粋)
h
k
n
パス幅
実行時間
辺密度
k
n
パス幅
実行時間
70
10
10
6
0
80
10
10
7
0
70
10
10
6
0
80
10
10
6
0
70
10
10
6
0
80
10
10
6
0
70
10
10
7
0
80
10
10
6
0
70
10
10
6
0
80
10
10
7
0
70
20
20
13
0
80
20
20
15
16
70
20
20
14
16
80
20
20
15
0
70
20
20
15
0
80
20
20
15
16
70
20
20
14
15
80
20
20
15
0
70
20
20
15
16
80
20
20
16
16
70
30
30
23
93
80
30
30
24
47
70
30
30
23
156
80
30
30
24
47
70
30
30
22
157
80
30
30
25
62
70
30
30
24
94
80
30
30
25
31
70
30
30
22
124
80
30
30
24
63
70
40
40
32
1139
80
40
40
33
265
70
40
40
32
1067
80
40
40
34
329
70
40
40
31
718
80
40
40
33
297
70
40
40
32
874
80
40
40
34
312
70
40
40
32
780
80
40
40
34
312
70
50
50
42
3464
80
50
50
43
1062
70
50
50
41
4416
80
50
50
43
890
70
50
50
42
8128
80
50
50
43
952
70
50
50
41
3948
80
50
50
43
1077
70
50
50
41
6787
80
50
50
43
1156
70
60
60
51
24213
80
60
60
53
3904
70
60
60
51
26895
80
60
60
52
2621
70
60
60
51
22434
80
60
60
53
3683
70
60
60
51
21904
80
60
60
52
3183
70
60
60
51
23417
80
60
60
52
3277
87
表 A.50
パス幅 10 以下，辺密度 70% の一般有向グ
表 A.51
ラフのパス幅を求める時間 (一部抜粋)
パス幅 10 以下，辺密度 80% の一般有向グ
ラフのパス幅を求める時間 (一部抜粋)
辺密度
k
n
パス幅
実行時間
辺密度
k
n
パス幅
実行時間
70
10
10
5
0
80
10
10
5
0
70
10
10
5
0
80
10
10
6
0
70
10
20
6
16
80
10
20
7
0
70
10
20
6
0
80
10
20
7
0
70
10
30
8
31
80
10
30
8
16
70
10
30
7
32
80
10
30
8
16
70
10
40
8
109
80
10
40
8
47
70
10
40
8
109
80
10
40
7
62
70
10
50
7
421
80
10
50
8
329
70
10
50
7
375
80
10
50
8
327
70
10
60
7
578
80
10
60
7
328
70
10
60
7
453
80
10
60
8
297
70
10
70
8
812
80
10
70
8
655
70
10
70
7
1062
80
10
70
8
514
70
10
80
8
1263
80
10
80
8
1327
70
10
80
8
1139
80
10
80
8
1280
70
10
90
8
3090
80
10
90
8
1436
70
10
90
8
3729
80
10
90
8
2418
70
10
100
8
5524
80
10
100
8
2232
70
10
100
8
3464
80
10
100
8
3183
70
10
110
8
9471
80
10
110
8
4245
70
10
110
8
11779
80
10
110
8
4431
70
10
120
9
9814
80
10
120
8
12153
70
10
120
8
18565
80
10
120
8
7988
70
10
130
7
14010
80
10
130
8
26396
70
10
130
8
14415
80
10
130
8
12123
70
10
140
9
25367
80
10
140
8
17145
70
10
140
8
23213
80
10
140
9
11981
70
10
150
8
30608
80
10
150
8
15071
70
10
150
8
26365
80
10
150
8
41777
88
表 A.52
パス幅 20 以下，辺密度 70% の一般有向グ
表 A.53
ラフのパス幅を求める時間 (一部抜粋)
パス幅 20 以下，辺密度 80% の一般有向グ
ラフのパス幅を求める時間 (一部抜粋)
辺密度
k
n
パス幅
実行時間
辺密度
k
n
パス幅
実行時間
70
20
10
6
0
80
20
10
5
0
70
20
10
5
0
80
20
10
6
0
70
20
20
11
17
80
20
20
12
15
70
20
20
11
0
80
20
20
10
16
70
20
30
11
47
80
20
30
14
93
70
20
30
13
94
80
20
30
13
78
70
20
40
14
281
80
20
40
14
219
70
20
40
13
94
80
20
40
14
312
70
20
50
14
1467
80
20
50
13
281
70
20
50
14
594
80
20
50
15
438
70
20
60
15
1436
80
20
60
14
1201
70
20
60
14
1310
80
20
60
14
1143
70
20
70
14
1732
80
20
70
14
1670
70
20
70
14
3402
80
20
70
14
2419
70
20
80
14
3543
80
20
80
14
3885
70
20
80
14
6132
80
20
80
14
4182
70
20
90
14
6553
80
20
90
14
8737
70
20
90
14
6382
80
20
90
14
10094
70
20
100
13
8020
80
20
100
15
12668
70
20
100
14
11779
80
20
100
14
8410
70
20
110
14
19361
80
20
110
14
12980
70
20
110
14
9002
80
20
110
14
16584
70
20
120
14
14384
80
20
120
14
17223
70
20
120
14
18815
80
20
120
14
11218
70
20
130
15
32683
80
20
130
14
14743
70
20
130
14
40093
80
20
130
14
19205
70
20
140
15
45194
80
20
140
15
36381
70
20
140
15
33947
80
20
140
15
26225
70
20
150
15
84756
80
20
150
15
63259
70
20
150
15
108889
80
20
150
14
42261
89
表 A.54
パス幅 30 以下，辺密度 70% の一般有向グ
表 A.55
ラフのパス幅を求める時間 (一部抜粋)
パス幅 30 以下，辺密度 80% の一般有向グ
ラフのパス幅を求める時間 (一部抜粋)
辺密度
k
n
パス幅
実行時間
辺密度
k
n
パス幅
実行時間
70
30
10
5
0
80
30
10
5
0
70
30
10
5
0
80
30
10
5
0
70
30
20
13
31
80
30
20
12
15
70
30
20
12
31
80
30
20
14
16
70
30
30
18
281
80
30
30
18
312
70
30
30
17
390
80
30
30
17
234
70
30
40
19
1560
80
30
40
18
500
70
30
40
18
593
80
30
40
16
593
70
30
50
18
1592
80
30
50
19
1654
70
30
50
20
1171
80
30
50
20
1374
70
30
60
21
3292
80
30
60
20
3776
70
30
60
21
6631
80
30
60
20
3620
70
30
70
21
9829
80
30
70
20
4713
70
30
70
20
16958
80
30
70
20
4150
70
30
80
20
10000
80
30
80
21
8519
70
30
80
20
16318
80
30
80
22
11919
70
30
90
20
13791
80
30
90
20
11545
70
30
90
21
14774
80
30
90
20
19641
70
30
100
20
27004
80
30
100
20
18752
70
30
100
21
19438
80
30
100
21
30843
70
30
110
20
21327
80
30
110
20
38096
70
30
110
20
41295
80
30
110
21
54211
70
30
120
20
51247
80
30
120
20
22106
70
30
120
20
32574
80
30
120
20
30109
70
30
130
21
105270
80
30
130
21
64195
70
30
130
21
68610
80
30
130
21
33962
70
30
140
20
100870
80
30
140
20
79779
70
30
140
21
300613
80
30
140
21
95785
70
30
150
21
120682
80
30
150
21
86285
70
30
150
21
173006
80
30
150
20
159792
90
[実験 3]3 章のアルゴリズムと 4 章のアルゴリズムの比較実験
3 章の障害を含まないグラフでの実験
表 A.56
表 A.57 パス幅 2 以下，障害を含まない準完全グラ
パス幅 1 以下，障害を含まない準完全グラ
フの実行時間 (一部抜粋)
フの実行時間 (一部抜粋)
解
実行時間
解
実行時間
k
n
3章
4章
3章
4章
k
n
3章
4章
3章
4章
1
5
1
1
15
0
2
5
1
1
16
0
1
5
1
1
0
0
2
5
1
1
0
0
1
5
1
1
16
0
2
5
1
1
15
0
1
6
1
1
47
0
2
6
1
1
47
0
1
6
1
1
31
0
2
6
1
1
47
0
1
6
1
1
47
0
2
6
1
1
31
0
1
7
1
1
172
0
2
7
1
1
140
0
1
7
1
1
172
0
2
7
1
1
172
0
1
7
1
1
188
0
2
7
1
1
156
0
1
8
1
1
468
0
2
8
1
1
702
0
1
8
1
1
468
0
2
8
1
1
812
0
1
8
1
1
453
0
2
8
1
1
858
0
1
8
1
1
468
0
2
8
1
1
703
0
1
9
1
1
889
0
2
9
1
1
3230
0
1
9
1
1
875
0
2
9
1
1
4228
0
1
9
1
1
889
0
2
9
1
1
4073
0
1
9
1
1
890
0
2
9
1
1
3839
0
1
10
1
1
1467
0
2
10
1
1
21997
0
1
10
1
1
1467
0
2
10
1
1
26880
0
1
10
1
1
1436
0
2
10
1
1
19984
0
1
10
1
1
1468
0
2
10
1
1
21311
0
1
11
1
1
2169
0
2
11
1
1
83992
0
1
11
1
1
2201
0
2
11
1
1
77112
0
1
11
1
1
2154
0
2
11
1
1
115862
0
1
11
1
1
2185
0
2
11
1
1
79140
0
1
12
1
1
3027
0
2
12
1
1
386507
0
1
12
1
1
3028
0
2
12
1
1
319880
0
1
12
1
1
3012
0
2
12
1
1
315137
0
1
12
1
1
3043
0
2
12
1
1
409315
0
91
3 章の degree tangle を含むグラフでの実験
表 A.58 (7, 1)-degree tangle を含む準完全グラフ
の実行時間 (n = 100 から n = 200)(一部抜粋)
実行時間
表 A.59 (7, 1)-degree tangle を含む準完全グラフ
の実行時間 (n = 210 から n = 300)(一部抜粋)
コミット
k
n
3章
4章
あり なし
実行時間
1
100
32
0
91
2
k
n
3章
4章
あり なし
1
100
0
0
91
2
1
210
16
0
201
2
1
110
0
0
101
2
1
210
16
0
201
2
1
110
16
0
101
2
1
220
32
0
211
2
1
120
0
0
111
2
1
220
31
0
211
2
1
120
16
0
111
2
1
230
47
0
221
2
1
130
15
0
121
2
1
230
31
0
221
2
1
130
0
0
121
2
1
240
31
0
231
2
1
140
16
0
131
2
1
240
31
0
231
2
1
140
15
0
131
2
1
250
47
0
241
2
1
150
15
0
141
2
1
250
47
0
241
2
1
150
16
0
141
2
1
260
46
0
251
2
1
160
16
0
151
2
1
260
47
0
251
2
1
160
15
0
151
2
1
270
47
0
261
2
1
170
16
0
161
2
1
270
47
0
261
2
1
170
16
0
161
2
1
280
47
0
271
2
1
180
15
0
171
2
1
280
62
0
271
2
1
180
16
0
171
2
1
290
63
0
281
2
1
190
31
0
181
2
1
290
62
0
281
2
1
190
16
0
181
2
1
300
62
0
291
2
1
200
31
0
191
2
1
300
63
0
291
2
1
200
31
0
191
2
92
コミット
表 A.60
(27, 5)-degree tangle を含む準完全グラフ
の実行時間 (n = 100 から n = 200)(一部抜粋)
実行時間
表 A.61 (27, 5)-degree tangle を含む準完全グラフ
の実行時間 (n = 210 から n = 300)(一部抜粋)
コミット
k
n
3章
4章
あり なし
実行時間
5
100
62
0
291
3
k
n
3章
4章
あり なし
5
100
47
0
269
3
5
210
110
0
509
3
5
110
47
0
317
3
5
210
124
0
480
3
5
110
47
0
291
3
5
220
125
0
507
3
5
120
63
0
304
3
5
220
141
0
508
3
5
120
62
0
301
3
5
230
141
0
525
3
5
130
63
0
323
3
5
230
171
0
519
3
5
130
93
0
330
3
5
240
156
0
545
3
5
140
109
0
375
3
5
240
157
0
591
3
5
140
78
0
343
3
5
250
203
0
561
3
5
150
62
0
359
3
5
250
172
0
563
3
5
150
79
0
481
3
5
260
203
15
589
3
5
160
94
0
508
3
5
260
188
0
601
3
5
160
78
0
409
3
5
270
203
0
607
3
5
170
93
0
492
3
5
270
219
0
602
3
5
170
94
0
428
3
5
280
234
0
626
3
5
180
93
0
437
3
5
280
234
0
629
3
5
180
111
0
440
3
5
290
265
0
652
3
5
190
109
0
442
3
5
290
265
0
670
3
5
190
110
0
449
3
5
300
250
0
663
3
5
200
109
0
480
3
5
300
298
0
677
3
5
200
141
0
462
3
93
コミット
表 A.62 (52, 10)-degree tangle を含む準完全グラ
フの実行時間 (n = 100 から n = 200)(一部抜粋)
実行時間
表 A.63
(52, 10)-degree tangle を含む準完全グラ
フの実行時間 (n = 210 から n = 300)(一部抜粋)
コミット
k
n
3章
4章
あり なし
実行時間
10
100
281
15
871
3
k
n
3章
4章
あり なし
10
100
250
0
898
3
10
210
499
0
1019
3
10
110
250
0
821
3
10
210
469
0
1030
3
10
110
249
0
875
3
10
220
500
0
1061
3
10
120
313
0
892
3
10
220
499
0
1129
3
10
120
265
0
891
3
10
230
531
0
1151
3
10
130
297
0
997
3
10
230
500
0
1072
3
10
130
312
0
972
3
10
240
608
0
1313
3
10
140
377
0
929
3
10
240
641
0
1367
3
10
140
343
0
833
3
10
250
561
0
1331
3
10
150
407
0
977
3
10
250
641
0
1156
3
10
150
343
0
973
3
10
260
624
15
1154
3
10
160
437
0
982
3
10
260
578
0
1179
3
10
160
391
0
972
3
10
270
608
16
1266
3
10
170
421
0
995
3
10
270
671
0
1190
3
10
170
375
0
1008
3
10
280
687
0
1216
3
10
180
390
0
1016
3
10
280
672
0
1182
3
10
180
453
0
1024
3
10
290
780
0
1211
3
10
190
436
0
1037
3
10
290
781
0
1250
3
10
190
422
0
1071
3
10
300
811
0
1368
3
10
200
437
0
1015
3
10
300
718
0
1193
3
10
200
484
0
1027
3
94
コミット
表 A.64 (77, 15)-degree tangle を含む準完全グラ
フの実行時間 (n = 100 から n = 200)(一部抜粋)
実行時間
表 A.65
(77, 15)-degree tangle を含む準完全グラ
フの実行時間 (n = 210 から n = 300)(一部抜粋)
コミット
k
n
3章
4章
あり なし
実行時間
15
100
795
0
1974
3
k
n
3章
4章
あり なし
15
100
764
0
2223
3
15
210
1530
0
2453
3
15
110
999
0
2179
3
15
210
1514
0
2458
3
15
110
843
0
2221
3
15
220
1577
0
2622
3
15
120
967
0
2273
3
15
220
1686
0
2439
3
15
120
1030
0
2163
3
15
230
1592
0
2431
3
15
130
1015
0
2302
3
15
230
1576
0
2548
3
15
130
1015
0
2412
3
15
240
1795
0
2608
3
15
140
1140
0
2291
3
15
240
1748
0
2405
3
15
140
1030
0
2220
3
15
250
1967
0
2518
3
15
150
1108
0
2429
3
15
250
1779
0
2461
3
15
150
1093
0
2404
3
15
260
1779
0
2540
3
15
160
1140
0
2339
3
15
260
2029
0
2560
3
15
160
1124
0
2422
3
15
270
2092
0
2671
3
15
170
1389
0
2683
3
15
270
1873
0
2717
3
15
170
1280
0
2273
3
15
280
2185
0
2877
3
15
180
1203
0
2419
3
15
280
1888
0
2712
3
15
180
1468
0
2321
3
15
290
1889
0
2530
3
15
190
1467
0
2522
3
15
290
2216
0
2740
3
15
190
1436
16
2404
3
15
300
2232
0
2636
3
15
200
1437
0
2497
3
15
300
2169
0
2591
3
15
200
1499
0
2571
3
95
コミット

No.438 家事関連費の必要経費該当性 - 税理士法人トータル ...

学校評価 - さいたま市立指扇中学校

学校体育施設開放事業における学校周辺での喫煙について（平成23年7

入学式 校長式辞より

アンケート結果（一部抜粋） - TRY 北海道から海外教育旅行

学校だより 第17号 更新 - Page ON

上場会社E−LearningLibrary 上場会社E−LearningLibrary

「名鉄沿線 酒蔵めぐり2016」を1月22日(金)から実施します