Disjoint フィードバック点集合の近似アルゴリズム
小川佐和子

1(指導教員：長尾篤樹)

はじめに理論計算機科学の分野においては多項式時間で解くことが難しいとされる問題に対してさまざまなアプローチがある. そのアプローチの一つとして近似アルゴリズムがある. 例えばフィードバック点集合問題は NP困難であるが近似比 2 が保証される多項式時間の近似アルゴリズムが存在する [1]. また既存の近似アルゴリズムを利用することで別の問題の近似アルゴリズムを構築するという手法が知られている [3]. 本稿では既存のフィードバック点集合問題の近似アルゴリズムを用いた Disjoint フィードバック点集合問題の近似アルゴリズムを提案する.

2

図 3 DFVS の近似アルゴリズム

る. N (v) を点 v の近傍とする. ただし v ̸∈ N (v). 閉路は単純な閉路とする.
以下, 以上の用語を用いてアルゴリズムの存在を示すための定理を証明していく.
定理 1. G に対する DFVS の近似比 ∆ の近似アルゴリズムが存在する.

フィードバック点集合Proof. 図 3 のような DFVS の近似アルゴリズムを構築する. 定理 1 を証明するために補題 2, 3, 4 を導入する.

グラフは無向, 重みなしの単純グラフとする.
グラフ G のフィードバック点集合 F は G(V ) \ F で誘導される部分グラフが森になるような G の点部分集合である (図 1). フィードバック点集合問題は入力としてグラフ G が与えられたとき, G における最小サイズのフィードバック点集合を求める.
以下, フィードバック点集合問題を FVS と表記する.

3

補題 2. G, F から以下の条件を満たす G′ を構成できる.
・G の閉路から G′ の閉路への写像が存在する.

Proof. 以下のように G′ を構成する. 閉路の探索は幅優先探索を行う. i, j, k, t を整数とする.
(1) 任意の点 v ∈ F について以下を行う. グラフ Gにおいて v と v に隣接する 2 点 ui , uj ∈ V \ F を含む,|C \ F | ≥ 3 となるような任意の閉路 C を探す. そのような C が存在し, C において F ∩ C の前後の点をつなぐ辺が存在しない場合は辺を追加する.
(2) 任意の 2 点 ui , uj ∈ V \ F に対して以下を行う.
ui , uj と F の複数の点を含む, |C \ F | = 2 となるような閉路 C を探す. そのような C が存在すれば, 点 wi 及
び ui , uj と wi をつなぐ辺を追加する. ui , uj 間に辺がない場合, その 2 点をつなぐ辺も追加する.
(3) 任意の点 u ∈ V \ F に対して以下を行う. u とF の複数の点を含む, |C \ F | = 1 となるような閉路 Cを探す. そのような C が存在すれば, 点 wj , wj+1 , 辺(wj , wj+1 ) 及び u とこの 2 点をつなぐ辺を追加する.
(4) F の 点 の み か ら 成 り 立 つ 閉 路 が 存 在 す れ ば,グ ラ フ H を H(V ) = {wk , wk+1 , wk+2 }, H(E) ={(wk , wk+1 ), (wk+1 , wk+2 ), (wk+2 , wk )} として, G =G ∪ H とする.
以上を行い, G から F の点を除去し G′ を構成する.
G の閉路から G′ の閉路への写像が存在することを示す. G の閉路 C1 , C2 , · · · , Ct について C1 \ F =C2 \ F = · · · = Ct \ F が成り立つとする. (1), (2), (3)より, G′ には C1 , C2 , · · · , Ct に対応する閉路が一つ存在する. F の内部に閉路が存在する場合, (4) よりそれらに対応する U の点のみから成り立つ閉路が G′ に一つ存在する. よって G の閉路から G′ の閉路への写像が存在する.

Disjoint フィードバック点集合

Disjoint フィードバック点集合問題は入力としてグ
ラフ G, G のフィードバック点集合 F が与えられたとき, G のフィードバック点集合 F ′ ⊆ G(V ) \ F が存在する場合は最小サイズの F ′ , 存在しない場合は解なしを求める (図 2). Disjoint フィードバック点集合問題はNP 困難であり, FPT アルゴリズムが存在する [2].
以下, Disjoint フィードバック点集合問題を DFVSと表記する.

4

DFVS の近似アルゴリズム

本稿では既存の FVS を解く近似アルゴリズムを用いて DFVS を解く近似アルゴリズムを提案する. そのために以下のような用語を用いる. DFVS の近似アルゴリズムの入力として与えられるグラフを G = (V, E),アルゴリズムの解と背反であるべき点集合を F ⊆ V と′する. アルゴリズムの解を F ′ , F ′ の最適解を FOPTとする. G と F から構成される, FVS の近似アルゴリズ
ムに与えられるグラフを G′ = (V ∪ U \ F, E ′ ) とする.
出力される G′ のフィードバック点集合を S とする. Gは全ての点の次数が 2 以上である二部グラフとする. Gにおける最大次数を ∆ とおく. d(v) を点 v の次数とす

図 1

グラフ G のフィードバック点集合

F (黒丸)

図 2 F に対する Disjoint フィードバック点集合 F ′ (灰色の丸)補題 3. 任意の O(f (n)) 時間で挙動する FVS の近似アルゴリズムを用いて, O(f (n) + n4 ) 時間で挙動する
DFVS の近似アルゴリズムを構成できる.

41

点集合を出力するため, S は G′ における極小なフィードバック点集合である. S ⊂ V のとき F ′ = S より
F ′ も極小なフィードバック点集合である. S ̸⊂ V のとき, w ∈ U を満たす w は高々一つの閉路にしか属さない. また S は極小なフィードバック点集合であるため
w ∈ S ならば u ∈ N (w) ∩ V は u ∈/ S である. よって(b) を行っても F ′ は G′ の極小なフィードバック点集合である. G の閉路から G′ の閉路への写像が存在すること, F ′ ⊂ V であることより F ′ は G の極小なフィードバック点集合である.
′G は全ての点について次数 2 以上である. FOPTは′G のフィードバック点集合, F は G の極小なフィードバック点集合である. よって式 (1) より

Proof. G′ と S から F ′ を構成する.
S ⊂ V のとき, F ′ = S とし F ′ を出力する.
S ̸⊂ V のとき, すなわち w ∈ U である点 w ∈ S が存在するとき以下のように F ′ または解なしを出力する.
(a) N (w) ∩ V =øとなる w が存在するとき, 解なしを出力する.
(b) 全ての w について N (w) ∩ V ̸=øが成り立つとき,F ′ = S と初期化する. 任意の点 u ∈ N (w) ∩ V を選び
F ′ = (F ′ ∪ {u}) \ {w} とする. これを F ′ ⊂ V となるまで繰り返し, F ′ を出力する.
以上を行い F ′ , または解なしを出力する.
このアルゴリズムの健全性を示す. 解が存在しないとき正確に解なしを出力すること, また解 F ′ が存在する
とき F ′ ∩ F =øを満たし, F ′ が G のフィードバック点集合であることを示す.

∑2|F ′ | ≤v∈Fm

∑d(v)

∑d(v)

(3)v∈F ′が成り立つ. また各点の次数は ∆ で押さえられるので∑′d(v) ≤ ∆|FOPT|(4)′v∈FOPTが成り立つ. 式 (2), (3), (4) より′|F ′ | ≤ ∆|FOPT|(5)が成り立つ. よって近似比は ∆ となる.
補題 2, 3, 4 を利用して定理 1 を証明する. 補題 2, 3より DFVS の近似アルゴリズムを構築できる. 補題 4より近似比は ∆ である. したがって G に対する DFVSの近似比 ∆ の近似アルゴリズムが存在する.

5

まとめと今後の課題

全ての点の次数が 2 以上の二部グラフに対するDFVS の O(f (n) + n4 ) 時間で挙動する ∆-近似アルゴリズムを提案した. 今後は入力が一般のグラフでもDFVS の近似アルゴリズムを構築できるか, より良い近似比で挙動するアルゴリズムは存在するか検討したい.

参考文献[1] Ann Becker and Dan Geiger. Optimization ofpearl’s method of conditioning and greedy-likeapproximation algorithms for the vertex feedback
set problem. Artiﬁcial Intelligence, 83(1):167–188, 1996.
[2] Yixin Cao, Jianer Chen, and Yang Liu. On feedback vertex set: New measure and new structures.
Algorithmica, 73(1):63–86, 2015.
[3] Yuma Tamura, Takehiro Ito, and Xiao Zhou. Approximability of the independent feedback vertex
set problem for bipartite graphs. In International
Workshop on Algorithms and Computation, pages
286–295. Springer, 2020.

Proof. 以下のような定理が存在する [1]. グラフ G の全ての点について次数が 1 より大きいとき, F ∗ を G の任意のフィードバック点集合, Fm を G の極小なフィードバック点集合とするとd(v) ≤ 2(2)が成り立つ. G の全ての点が次数 2 以上であることから

補題 4. DFVS の ∆-近似アルゴリズムが存在する.

∑d(v)′v∈FOPTv∈F ′解が存在しないとき正確に解なしを出力することを示す. DFVS の解が存在しないとき G は F の内部に閉路を持つ. G が F の内部に閉路を持つとき w ∈ Uである w ∈ S において N (w) ∩ V =øとなる w が存在するため, (a) より解なしが出力される. 逆に解なしを出力するとき, (a) より w ∈ U である w ∈ S においてN (w) ∩ V =øとなる w が存在するため, G′ は U の点のみから成り立つ閉路を持つ. すなわち G は F の内部に閉路を持つので F ′ ⊆ V \ F を満たす F ′ は存在しない.
よって解が存在しないとき正確に解なしを出力する.
F ′ ∩ F =øを示す. G′ の点集合は V ∪ U \ F なのでS ∩ F =øである. S ⊂ V のとき F ′ = S とするので
F ′ ∩ F =øである. S ̸⊂ V のとき w ∈ U である w ∈ Sについて, G′ の点集合が V ∪ U \ F であることより
N (w) ∩ F =øなので, F ′ に (b) を行っても F ′ ∩ F =øである. よって F ′ ∩ F =øが成り立つ.
F ′ が G のフィードバック点集合であることを示す.
w ∈ U である全ての w ∈ S について N (w) ∩ V ̸=øが成り立つとき, U の点のみからなる閉路は G′ に存在しない. よって w ∈ U が含まれて u ∈ N (w) ∩ V が含まれない閉路は G′ に存在しないので, S ̸⊂ V のとき(b) を行っても F ′ は G′ のフィードバック点集合である. G の閉路に対応する閉路が G′ に存在すること, F ′は G′ のフィードバック点集合であること, F ′ ⊂ V であることから F ′ は G のフィードバック点集合である.
計算時間は G′ の構成は任意の頂点対に対して閉路の探索を行うため O(|V |2 |E|) 時間, F ′ の構成は O(|V |)時間となる. よって n = |V | とすると FVS のアルゴリズムの計算時間が O(f (n)) であれば全体の計算時間はO(f (n) + n4 ) となる.

∑d(v) ≤ 2(1)v∈F ∗F ′ が存在するとき, F ′ は G の極小なフィードバック点集合であることを示す. [1] のように FVS の近似
アルゴリズムは入力のグラフの極小なフィードバック

42