二分木のライングラフにおける Fireﬁghter 問題の貪欲アルゴリズム
鈴木亜希

1(指導教員：長尾篤樹)近似アルゴリズムが研究されている. 近似アルゴリズムとは，常に最適解を出力するわけではなく，最適解からある程度理論的に精度の保証された解を高速に出力するアルゴリズムのことを差す．入力 σ に対しての最適解を OP T (σ)，アルゴリズムの出す解を ALG(σ) としたとき，ALG(σ)/OP T (σ) の上界を近似比と呼び，近似アルゴリズムの示す精度とされる．
例えば，入力を木に制限した Fireﬁghter 問題に対して近似比 2 の近似アルゴリズムが知られており [3]，この近似比は延焼した頂点に隣接する頂点のうち子孫の数が最も多いものを保護するという貪欲アルゴリズムで実現されている．一方で，同様の制限を持つ Fireﬁghter問題には近似比が 2 を下回るアルゴリズムが存在しないことが知られており [3]，貪欲アルゴリズムが最良の近似アルゴリズムであることがわかる．

はじめに現実の問題を解決するためにモデルとして定式化することがある．たとえば，伝染病の感染モデルは人を頂点，感染リスクを持つ人同士の関係を辺で表現するグラフを用いて定式化できる．感染モデルは火災発生時の延焼モデルと同様に扱う事ができ，そのモデル上で被害を最小に食い止める問題として”Fireﬁghter 問題”が多く研究されている [1]．FireFighter 問題は入力として与えられるグラフが木である場合, 多項式時間で解ける条件と NP 困難となる条件とが存在することが知られている．[2] これらの問題が NP 困難である場合には多項式時間で解を求めることが難しく，ある比での誤差を認める近似解を求めるアルゴリズムである近似アルゴリズムが研究されている [3]．本研究では Fireﬁghter
問題の入力を二分木のライングラフに制限した場合の近似アルゴリズムの構成を目指し，その結果として貪欲アルゴリズムでは近似比が発散してしまうことを確認した．

24

本章では本稿の解析対象である，入力を木のライングラフに制限した Fireﬁghter 問題を考える. ライングラフとは元のグラフの辺を頂点とし, 元のグラフで隣接する辺同士を結んだ線を辺とするグラフである.Fireﬁghter
問題の発火点は左上の頂点とし, 延焼した頂点の総数を最小化する最適化問題を考える.

Fireﬁghter 問題

Fireﬁghter 問題とは, 火災の延焼をモデル化した問題であり, 伝染病, コンピュータウイルスの拡散を表すモデル等として, 以下のような問題として扱われる. 入力
グラフ G = (V, E) で時刻 t = 0 のときにある頂点から出火する. 各時刻ごとに消防士が点を保護し, 出火している頂点に隣接する頂点に延焼する. 延焼と保護は同時に起こらず, 延焼した頂点には延焼のラベル, 保護された頂点には保護のラベルをつける. 隣接している頂点に延焼した頂点がない場合, その頂点は延焼しない. 一度保護された頂点, 延焼した頂点はその状態を維持し, 延焼する頂点に隣接する頂点がなくなるまで繰り返す. 保
護された頂点と延焼しない頂点の総数を保存された点といい, 保存された頂点の総数を出力する. 入力グラフを木に限定した場合, 保存された頂点の総数を最大化す
る最適化問題，すなわち延焼した頂点の総数を最小化する最適化問題は NP 困難であることが知られており，このことから多項式時間で最適解を求めることは非常に難しいとされている．

図1

3

元のグラフ

図2

二 分 木 の ラ イ ン グ ラ フ に お け る Fireﬁghter 問題の貪欲アルゴリズム

4.1

頂点数のみを考慮した貪欲アルゴリズム

本節では，最も単純な貪欲アルゴリズムとして，頂点数のみを考慮した貪欲アルゴリズムの近似比解析を行う．対象とするアルゴリズムの詳細は次の通りである.

1. 頂点 1 つあたりの重さを 1 とし, 親の重み wv を子の重みの和とする

2. 各ステップで延焼した点に隣接する頂点のうち重みが一番大きい頂点を保護する

3. 隣接する頂点に等しい重みをもつ頂点が存在する
場合, より深さが浅い頂点を保護する
4. 延焼した頂点に隣接する頂点がなくなるまで 1,2,3を繰り返す.
以上のアルゴリズムの近似比を解析したところ，以下の定理を得た．
定理 1. 二分木のライングラフにおける Fireﬁghter 問
題を解く頂点数のみを考慮した貪欲アルゴリズムの近似値は発散する

Proof. 近似比は ALG/OP T の解の最大値であるので,最適解と貪欲アルゴリズムによる解の比が大きくなるようなグラフを探す. まずは小さいグラフで ALG がOP T より大きくなるものをみつけ, それを無限に拡張していく. 図 3 のグラフを例に考える. 最適解と貪欲アルゴリズムの実行結果は以下のようになる. ×がつけられた頂点は延焼した頂点を表しており, □で囲まれた頂点は保護された頂点を表している. 発火点に隣接する頂点を左から順に v1 ,v2 ,v3 とする. 最適解は一手目に v1 ,二手目に v4 を保護し, 保護される頂点の総数は 18 個でライングラフ近似アルゴリズム

Fireﬁghter 問題の最適化問題の多くは NP 困難であり，多項式時間で最適解を求めることは難しいとされている. そこで, 多項式時間で妥当な解をもとめるために43認するため，各頂点 v1 ,v2 ,v3 の重み wv1 ,wv2 ,wv3 を求める.

ある. 一方で貪欲アルゴリズムによる解は, 発火点に隣接する各頂点の重みは wv1 = wv2 < wv3 となり, 一番
重みが大きい v3 を保護し, 保存される頂点の総数は 13個となる.

242x++α α2α242xw v2 = 1 + + 2 +α α
α224wv3 = 1 + + 2 + 3 + 2xα ααw v1 = 1 +以上の式より α の値によってアルゴリズムの挙動が変わることがわかる.α の値を場合分して考える.
図3

図 4 貪欲アルゴリズムに最適解

1. 1 < α < 2 のとき
wv1 = wv2 < wv3 となり v3 を先に保護するため近よる解

似比は発散する
2. 2 ≤ α のときこのグラフを元に近似比 ALG/OP T が発散する例
を作る. 元の木にアルゴリズムの挙動が変わらないよう深さ n の完全二分木となる足を付け加える. 拡張したグラフに貪欲アルゴリズムを適用すると延焼した頂点の総数は 11 + 2n+1 + n 個, 保存された頂点の総数は5 × 2n+1 − n + 1 個となる. 一方で最適解では, 延焼した頂点の総数は 9 + n 個であり保存された頂点の総数は 6 × 2n+1 − n + 3 個である.

wv1 = wv2 ≥ wv3 となりこのライングラフにおいては最適解と一致する

定理 1 の証明と同様に延焼した頂点と保存した頂点の総数を比較することにより以下の式が得られる.

11 + 2n+1 + n
ALG=→∞n→∞ OP T9+nlim

これにより，以下の定理が示される．
定理 2. 各頂点の重みを発火点の距離を r として (1/α)rとした貪欲アルゴリズムの近似比は α ≤ 2 の場合においては発散する.

5

図5

本研究では入力グラフを二分木のライングラフに限定した Fireﬁghter 問題を解くアルゴリズムを解析した.
その結果, 頂点数のみを考慮した貪欲アルゴリズムと深さに対して指数的な重みを考慮した貪欲アルゴリズ
ムでは α < 2 であるとき近似比は発散することが得られた. 一方で 2 ≤ α の場合には同じ手法では OP T とALG の挙動が一致する例しか見つからなかった. この
結果,ALG/OP T の最悪値を出したい一方でそのような例を作ることができず,2 ≤ α の場合は解析が終わっていない. 定理 2 を任意の α で成り立たせるため以下の予想が証明されることが期待される.
予想 3.
各頂点の重みを発火点の距離を r として(1/α)r とした貪欲アルゴリズムの近似比は α > 2 の場合においても発散する

拡張したグラフ

したがって求める近似比はALG
11 + 2n+1 + n=→∞n→∞ OP T9+nlimとなりこのアルゴリズムの近似比は発散する。
以上のことから, 延焼した頂点の総数を最小化する最適化問題を解く近似アルゴリズムを設計するためには頂点数以外のパラメータを持つアルゴリズム設計が必要となる.

4.2

まとめと今後の課題

参考文献[1] Elliot Anshelevich, Deeparnab Chakrabarty,
Ameya Hate, and Chaitanya Swamy. Approximability of the ﬁreﬁghter problem. Algorithmica,
62(1):520–536, 2012.
[2] Stephen Finbow and Gary MacGillivray. The ﬁreﬁghter problem: a survey of results, directions
and questions. Australas. J Comb., 43:57–78,2009.
[3] Bert Hartnell. Fireﬁghting on trees: how bad is
the greedy algorithm? Congressus Numerantium,
145:187–192, 2000.

深さに対して指数的な重みを考慮した貪欲アルゴリズム

本節では, 重み関数付きの貪欲アルゴリズムを提案する. 延焼した頂点からの距離を n とし, その頂点の重みを α を 1 以上の定数として (1/α)n−1 とする. 4.1 節と同様にグラフを拡張して解析を行う. アルゴリズムの挙動が変わらないように頂点の総数が同じで重みの総和x の二分木を接続させる. 右側の二分木が接続される頂点は発火点からの距離が相対的に一段深いため重みは1/α 倍となる. このような処理を行った場合でも最適解の挙動は変化しない. よってアルゴリズムの挙動を確44