Burning Schedule 遷移問題に対する
多項式時間アルゴリズムと FPT アルゴリズム
理学専攻・情報科学コース 2140650 小川佐和子 (指導教員：長尾篤樹)

1

はじめに離散的な時間の経過によって周囲に影響が広がっていく様子をグラフ上で表現するモデルとして graphburning が Bonato ら に よ っ て 提 案 さ れ て い る [1].
Graph burning は以下の要領で進行する. 入力として単純無向グラフ G = (V, E) が入力として与えられ,時間の経過は 0 以上の整数をとるラウンドで表される.
初期状態 (0 ラウンド) ではどの頂点も燃えていない状態であり, 各ラウンドではそれまでのラウンドで燃えた頂点の近傍に燃え広がり, さらにまだ燃えていない 1 点が新たに燃やされる. 一度燃えた頂点は燃えていない状態に戻ることはない.
そのように各ラウンドで新たに発火させる発火点の集合 B ⊆ V が与えられ, それらのみを発火させて |B|
ラウンドまでにグラフ上の全ての頂点を燃やし尽くせるか判定する問題は Burning スケジュール問題 (BSP)として知られていて, NP 困難であることが示されている [4].
BSP に対して燃やし尽くすという条件を満たしつつ発火させる順番を調整したい状況が考えられ, そのような問題は遷移問題として研究されている. 遷移問題は問題の入力と 2 つの実行可能解が与えられたとき, 実行可能解のみを辿ることで一方の解から他方の解へ遷移できるかを判定する問題であり, 様々な問題の遷移問題版について解析されている [3]. 同様の設定で BSP の遷移問題版である Burning Schedule 遷移問題 (BSRP) を考えることができる.
本稿では BSRP の定義を行い, その定義の下では最大次数 3 のグラフに対する BSRP が PSPACE 完全であることを示す. 一方で入力のグラフクラスを制限したときの BSRP に対して多項式時間アルゴリズムが存在することを示し, さらに FPT アルゴリズムを提案する.
FPT アルゴリズムとはあるパラメータ k および n, k に依存しない定数 c に対して, 計算時間が f (k) · nc 時間となるアルゴリズムである.

2

B = {b1 , b2 , b3 }, スケジュール b2 b1 b3 で燃やし尽くした様子.

図1

Schedule 遷移問題 (BSRP) は, グラフ G, 発火点の集合 B ⊆ V (G), および G, B に対する 2 つの実行可能なスケジュール s, t に対して, swap を繰り返すことで sから t まで遷移できるか判定する問題である. ただし
swap はスケジュールにおける任意の 2 点の発火する順を入れ替える操作である.
|B| = k, B = {b1 , . . . bk } とおく. スケジュールの隣接関係を以下のように定義する.
定義 1 (スケジュールの隣接関係). si , s′i ∈ {b1 , . . . bk }と す る. 2 つ の ス ケ ジ ュ ー ル S, S ′ に つ い て S =s1 s2 · · · sk , S ′ = s′1 s′2 · · · s′k と す る. i, j, l を 1 ≤i, j, l ≤ k かつ l ̸= i, j を満たす任意の整数とする.
スケジュール S, S ′ が隣接しているとき, またそのときのみ, S, S ′ について si ̸= s′i , sj ̸= s′j , sl = s′l が成り立つ.
以上の定義を言い換えると, 異なる 2 つのスケジュー
ル S, S ′ 間のハミング距離を H(S, S ′ ) と表記すると,S, S ′ が互いに隣接しているとき, またそのときのみH(S, S ′ ) = 2 が成り立つと言える.
本稿では特に断らない限り, BSRP の入力として与えられる G は path forest, すなわち各連結成分がパスである非連結グラフとする. G の各パスを Pi とおく.
G の各パスに発火点が 1 点ずつ存在するときを考える. すなわち, 入力のグラフにパスは |B| = k 個存在する. G の各パスを Pi とおき, そのパスに存在する発火点を bi とおく. Pi において, bi から左の端点までの距離を dli , bi から右の端点までの距離を dri とおき,
Di = max(dli , dri ) とする. 簡単のために, Di の降順にPi を並べ替えても一般性を失わなず, 以下はパスをこの通りに番号付けを行う. すなわち P1 , P2 , . . . , Pk に対して D1 ≥ D2 ≥ · · · ≥ Dk が成り立つ.
bi を i ラウンドに燃やすようなスケジュールを対角線スケジュールと定義し, dS と表記する. 図 2 の右のように G 全体を燃やし尽くすために各発火点が燃やす必要のある距離と, グラフ全体を燃やし尽くすために各発火点をいつ燃やせばよいかを表したものを G の構造と呼ぶ.

数学的準備

グラフ G = (V, E) について |V | = n とおく. Graphburning は以下のように進行する. 各ラウンドではそれまでのラウンドで燃えた頂点の近傍に燃え広がり, さらにまだ燃えていない 1 点を新たに発火させる. 一度燃えた頂点は燃えていない状態に戻ることはない. グ
ラフ上の全ての頂点を燃やし尽くすまでに各ラウンドで新たに発火した頂点を並べた列をスケジュールと呼ぶ. Burning schedule 問題（BSP）は, グラフ G と発火点の集合 B ⊆ V が入力として与えられたとき, G の全ての頂点を |B| ラウンド以内に燃やし尽くすようなB の頂点のみからなるスケジュールを作成できるかを判定する問題である. 与えられた G, B に対して, |B|ラウンド以内に G の全ての頂点を燃やし尽くすスケジュールを実行可能なスケジュールとする. Burning

1

に対応した FPT アルゴリズムを提案する. 入力の pathforest において発火点が複数存在するパスが存在し, そのような発火点の数の合計が定数 c 個であるときを考える (2 ≤ c ≤ k). このときパスに 1 点だけ存在する発火点は k − c 点であり, B = {b1 , b2 , . . . , bc , bc+1 , . . . , bk }となる. {b1 , . . . , bc } 上の全ての順列 π1 , . . . , πc! とそれらを部分列として含むスケジュールを考えることで, 以下の定理が得られる.
定理 7. 入力が各パスに複数存在する発火点の数がc 個であるような path forest に制限された BSRP をO(cc ) × O(n log n) 時間で解く FPT アルゴリズムが存在する.
定理 7 は一般の非連結グラフに拡張可能である.
定理 8. 1 つの連結成分に複数個存在する発火点が定数個であるような入力が与えられたとき, BSRP の解を求める FPT アルゴリズムが存在する.

図 2 D1 = 2, D2 = 2, D3 = 1, D4 = 0 より,
dS = b1 b2 b3 b4 となる.

3PSPACE 完全性

一般的に遷移問題は P または PSPACE 完全であり,3SAT 遷移問題は PSPACE 完全であることが示されている [2]. BSP の NP 困難性が 3SAT から帰着されることによって示されていることに着想を得て, BSRP のPSPACE 困難性を 3SAT 遷移問題からの多項式時間帰着によって証明した.
定理 2. Burning Schedule 遷移問題は PSPACE 完全である.
また 3SAT 遷移問題が PSPACE 完全となる条件 [2]と, 入力の論理式において各変数の出現回数が高々 3回かつ各リテラルの出現回数が高々 2 回に制限された
3SAT 遷移問題からの帰着により, 以下の系が成り立つ.
系 3. BSRP は入力のグラフを最大次数 3 に制限しても PSPACE 完全である.

46

入力のグラフの最大次数が 3 以上であるとき BSRPが PSPACE 完全であることを示した. また path forest
上の BSRP について, 各パスに存在する発火点が 1 点の場合と 2 点の場合の多項式時間アルゴリズム, およびパスに複数存在する発火点が定数個のときの FPT アルゴリズムを提案した.
定理 6 のアルゴリズムについて, 入力のグラフの連結成分がすべてサイクルである場合を考えると, 入力のグラフが path forest のときと同様に各サイクルの構造を考えることができるため, 各サイクルに存在する発火点が高々 2 点のとき定理 6 のアルゴリズムを拡張可能である. また, 入力のグラフが path forest であり, 各パスに存在する発火点の数が高々定数個かつ発火点が複数存在するパスが定数本のときにも拡張できる.
今後の課題としては, 最大次数 2 であるグラフ一般に対する BSRP の計算複雑性の解析や, BSRP において各連結成分に存在する発火点が定数個ではない場合が考えられる.

多項式時間アルゴリズム

入力のグラフの次数の最大次数に着目した結果, 入力が最大次数 2 である path forest の場合は BSRP に対する多項式時間アルゴリズムを構築できた.
入力のグラフの各パスに発火点が 1 点ずつ存在する
とき, 以下の定理が成り立つ.
定理 4. BSRP の入力として各パスに発火点が 1 点のみ存在するような path forest G と発火点の集合 B, 任
意の 2 つの実行可能なスケジュールが入力として与えられたとき, 2 つのスケジュールに関わらず常に遷移可能である.
またこのとき, 多項式時間で遷移可能か判定するだけでなく最短の遷移パスを求められることも示した.
系 5. BSRP の入力として発火点が各パスに 1 点ずつ存在するような path forest G, および実行可能なスケジュール s, t が与えられたとき, s から t への最短の遷移経路を O(n) 時間で求めることができる.
1 つのパスに発火点が 2 点存在する時はより複雑な状況となる. ある定数 c を用いて, G において c 本のパスに発火点が 2 点存在するとき, G を燃やし尽くすには発火点から端点までの距離ともう一つの発火点までの距離を考慮する必要がある. そのような複雑な状況を避けるため発火点が 1 点になるようにパスを分割することを考える. 分割したパスを組み合わせて再構成したグラフに対する構造を考えると以下の定理が得られた.
定理 6. 発火点が 2 点存在するパスが c 本であり， 各パスには高々 2 点の発火点が存在する path forest 上のBSRP を O(n2c ) 時間で解く多項式時間アルゴリズムが存在する.

5

まとめと今後の課題

参考文献[1] Anthony Bonato, Jeannette Janssen, and Elham
Roshanbin. How to burn a graph. Internet Mathematics, 12(1-2):85–100, 2016.
[2] Parikshit Gopalan, Phokion G Kolaitis, Elitza
Maneva, and Christos H Papadimitriou. The connectivity of boolean satisﬁability: computationaland structural dichotomies. SIAM Journal onComputing, 38(6):2330–2355, 2009.
[3] Takehiro Ito, Erik D Demaine, Nicholas JA Harvey, Christos H Papadimitriou, Martha Sideri,Ryuhei Uehara, and Yushi Uno. On the complexity of reconﬁguration problems. TheoreticalComputer Science, 412(12-14):1054–1065, 2011.
[4] Debajyoti Mondal, N Parthiban, V Kavitha, andIndra Rajasingh. Apx-hardness and approximation for the k-burning number problem. In International Workshop on Algorithms and Computation, pages 272–283. Springer, 2021.

FPT アルゴリズム

スケジュールに着目し, 発火点の部分集合の順列を用いて前節の多項式時間アルゴリズムよりも一般的な入力

2