情報処理学会研究報告
IPSJ SIG Technical Report

疎グラフにおけるサイズ制約付きグラフ分割問題の固定パラメータ容易アルゴリズム
山田 秀流1,a)

土中 哲秀2,b)

概要：無向重み付きグラフ G = (V, E) において，頂点部分集合 S ⊆ V で定まる関数を φG (S) :=(1 − α) · m(S) + α · m(S, V (G)\S) で定義する．ただし，α は α ∈ [0, 1] を満たす実数，m(S) は S に両端点が含まれる辺の重みの総和，m(S, V (G)\S) は S に含まれる端点を 1 つだけ持つ辺の重みの総和である．このとき，最大（最小）α-固定サイズグラフ分割問題は，無向重み付きグラフ G = (V, E) と正整数 kを入力とし，φG (S) を最大（最小）にするようなサイズ k の頂点部分集合 S を求める問題である．本研究では，α ∈ [1/3, 1] のときの最大 α-固定サイズグラフ分割問題と α ∈ [0, 1/3] のときの最小 α-固定サイズグラフ分割問題に対して，解サイズ k と縮退数 d に関する 2kd+k (kd)O(log(kd)) nO(1) -時間アルゴリズムを与える．
キーワード：グラフ分割, グラフアルゴリズム, 固定パラメータ容易アルゴリズム, 縮退数

Fixed-parameter algorithms for Cardinality-constrained Graph
Partitioning Problems on Sparse Graphs
Abstract: For an undirected weighted graph G = (V, E) and a vertex subset S ⊆ V , we deﬁne a function
φG (S) := (1 − α) · m(S) + α · m(S, V \ S), where α ∈ [0, 1] is a real number, m(S) is the sum of weights ofedges having two endpoints in S, and m(S, V \ S) is the sum of weights of edges having one endpoint in S
and the other in V \ S. Then, given an undirected weighted graph G = (V, E) and a positive integer k, Max(Min) α-Fixed Cardinality Graph Partitioning is the problem to ﬁnd a vertex subset S ⊆ V of size kthat maximizes (minimizes) φG (S). In this paper, we ﬁrst show that Max α-Fixed Cardinality Graph
Partitioning with α ∈ [1/3, 1] and Min α-Fixed Cardinality Graph Partitioning with α ∈ [0, 1/3]
can be solved in time 2kd+k (kd)O(log(kd)) nO(1) .
Keywords: graph partitioning, graph algorithm, ﬁxed-parameter algorithm, degeneracy

1. はじめにみの総和である．このとき，最大（最小）α-固定サイズグラ
フ分割問題 (α-Fixed-cardinality Graph Partition-

無向重み付きグラフ G = (V, E) において，頂点部分集ing; α-FCGP) は，無向重み付きグラフ G = (V, E) と正整合 S ⊆ V で定まる関数を φG (S) := (1 − α) · m(S) + α ·数 k を入力とし，φG (S) を最大（最小）にするようなサイm(S, V (G)\S) で定義する．ただし，α は α ∈ [0, 1] を満たズ k の頂点部分集合 S を求める問題である．最大（最小）す実数，m(S) は S に両端点が含まれる辺の重みの総和，α-固定サイズグラフ分割問題は，最密（最疎）k-部分グラm(S, V (G)\S) は S に含まれる端点を 1 つだけ持つ辺の重フ問題，最大（最小）k-次数和問題，最大（最小）k-部分頂点被覆問題，最大（最小）(k, n − k)-カット問題など様々な

12a)b)

九州大学理学部物理学科
Department of Physics, Kyushu University
九州大学大学院システム情報科学研究院
Graduate School of Information Science and Electrical Engineering, Kyushu University
yamada.suguru.896@s.kyushu-u.ac.jp
hanaka@inf.kyushu-u.ac.jp

c 2023 Information Processing Society of Japan⃝

重要問題を一般化したものとなっている．実際，最密（最疎）k-部分グラフ問題は α = 0，最大（最小）k-次数和問題
は α = 1/2，最大（最小）k-部分頂点被覆問題は α = 1/2，最大（最小）(k, n − k)-カット問題は α = 1 のときに対応する（表 1）．

1情報処理学会研究報告
IPSJ SIG Technical Report
表 1

最大（最小）α-固定サイズグラフ分割問題に含まれる問題
α問題

0最密（最疎）k-部分グラフ問題

1/3

最大（最小）k-次数和問題

1/2

最大（最小）k-部分頂点被覆問題

1

最大（最小）(k, n − k)-カット問題

グラフ頂点をある順序で一列に並べるとき，各頂点 v の順序を λ(v) で表すとする．このとき任意の頂点 v に対して，λ(v) < λ(u) を満たすような v の隣接頂点 u の個数が高々 d となるような頂点順序 λ を d-後順序（d-posteriororder ）という．また，d-後順序を持つグラフのことを d縮退グラフという．
定義 2.1 (縮退数). あるグラフに対して d-後順序を考えた

1.1 先行研究
本節では，最大（最小）α-固定サイズグラフ分割問題にとき，最小となる d をそのグラフの縮退数という．
また，平面グラフの縮退数は高々 5 となることが知られ関する先行研究を紹介する．Bonnet ら [1] は，重みなし最√大（最小）α-FCGP が (2k ∆)2k nO(1) -時間で解けることている [3]．更に，縮退数が d であるようなグラフに対し，を示した．ただし，∆ は入力グラフの最大次数である．更d-後順序は線形時間で求めることが可能である [4]．次に，に，α ∈ [0, 1/3) を満たす最大 α-FCGP，及び α ∈ (1/3, 1]

d-後順序 λ に関する右側隣接集合を定義する．

k O(1)を満たす最小 α-FCGP について，∆ n-時間アルゴリズムが存在することも示した．

定義 2.2 (右側隣接集合). 縮退数 d のグラフに対して d後順序を考えたとき，ある頂点 v に対して右側隣接集合Shachnai と Zehavi [7] は，任意の α ∈ [0, 1] に対して，PNλ (v) を PNλ (v) := {u ∈ N (v) | λ(v) < λ(u)} と表す．

重みなし最大（最小）α-FCGP が 4k+o(k) ∆k nO(1) -時間ですなわち，λ(v) が小さい順に左から頂点を並べたとき，解けることを示し，[1] の結果を改善した．

PNλ (v) は v の右へ隣接する頂点の頂点部分集合である．

Koana ら [2] は，重みなし最大 α-FCGP に対して，解サイズ k と縮退数 d をパラメータとしたときに，α ∈ [0, 1/3) で最後に，(n, l)-台集合を以下で定義する．

W[1]-困難であること，α ∈ [1/3, 1] のとき (kd)O(k) nO(1) -定義 2.3 ((n, l)-台集合 ((n, l)-universal set)). 要素数 l の時間アルゴリズムが存在することを示した．また，最小任意の A ⊆ [n] に対し，{U ∩ A : U ∈ U } が A の 2l 個の部

α-FCGP について，α ∈ [0, 1/3) では kd

分集合をすべて含むような [n] の部分集合の族 U を (n, l)-O(k)-時間アルゴリ

ズム，α ∈ (1/3, 1] では (kd)O(k) nO(1) -時間アルゴリズムが存在することも示した．

Panolan ら [6] は，α = 1/2 のときの最大 α-FCGP，すなわち最大 k-部分頂点被覆問題に対して，解のサイズ k ，縮退数を d に関する 2kd+k (kd)O(log(kd)) nO(1) -時間アルゴリズムが存在することを示した．

1.2 本研究結果
本研究では，Panolan ら [6] のアルゴリズムを一般化し，

α ∈ [1/3, 1] を満たす最大 α-固定サイズグラフ分割問題とα ∈ [0, 1/3] を満たす最小 α-固定サイズグラフ分割問題に対して，2kd+k (kd)O(log(kd)) nO(1) -時間アルゴリズムを与える．平面グラフにおける縮退数 d は 5 以下であることが知られていることから，本研究結果は，最大（最小）α-固定サイズグラフ分割問題，及び最大（最小）連結 α-固定サイズグラフ分割問題は平面グラフにおいて 2O(k) nO(1) -時間で解けることも示している．

2. 準備無向グラフを G = (V, E) とし，n = |V |，m = |E|とする．グラフ G = (V, E) の各辺 {u, v} ∈ E が重み台集合 ((n, l)-universal set ) という．
なお任意の n, l ≥ 1 に対し，サイズ 2l lO(log l) log n の(n, l)-台集合を 2l lO(log l) n log n-時間で構成可能であることが知られている [5]．

3. 解サイズと縮退数に関する固定パラメータ容易アルゴリズム
本節では，最大（最小）α-固定サイズグラフ分割問題に対して，解サイズと縮退数に関する固定パラメータ容易アルゴリズムを設計する．本論文では，α ∈ [1/3, 1] の場合における最大 α-FCGP に対する 2kd+k (kd)O(log(kd)) nO(1) -時間アルゴリズムのみ述べる．
まず，NG (v) を頂点 v の隣接頂点の頂点部分集合，PNλ (v)を右側隣接集合とする．次に，l := min{n, k + kd} として(n, l)-台集合 U を構成する．サイズ k 以上の各 U ∈ U に対し，v の価値 valU (v) を以下で定義する．

valU (v) := α∑u∈NG (v)k 個の頂点からなる集合を以下で定義する．
sol(U ) := arg maxS ∗ ⊆U,|S ∗ |=kc 2023 Information Processing Society of Japan⃝∑valU (s)s∈S ∗す．また，頂点 v ∈ V に対する隣接頂点集合を NG (v) とする．

wuvu∈PNλ (v)∩U

また，U ∈ U に関して，valU (v) の和が最も大きくなる

wuv : E → R+ を持つグラフを重み付きグラフという．頂点部分集合 S ⊆ V に誘導される部分グラフを G[S] で表∑

wuv + (1 − 3α)

さらに，val(U ) :=∑v∈sol(U ) valU (v) と定義する．

2

情報処理学会研究報告
IPSJ SIG Technical Report

最適解 S ∗ に対して，S˜∗ を S̃ := S ∗ ∪ (∪s∈S ∗ PNλ (s)) と( 2 ) 両端点を S ∗ に持つ辺 e = {u, v}∑する．このとき，(n, l)-台集合の定義より，S̃ ⊆ T となる

補題 3.1 と同様にして，(1 − α) · wuv がようなサイズ l の部分集合 T ⊆ V に対して S ∗ = Ũ ∩ T とにちょうど 1 回カウントされる．
∑
従って，φG (S ∗ ) = s∈S ∗ valŨ (s) が成り立つ．

なるような集合 Ũ ∈ U が存在する．

s∈S ∗ valŨ (s)補題 3.1. α ≥ 1/3 のとき，任意の U ⊆ V と A ⊆ U に対∑して a∈A valU (a) ≤ φG (A) が成り立つ．

定 理 3.1. d-縮 退 グ ラ フ に お け る 最 大 α-FCGP に は ，Proof. 辺の端点に関して場合分けして考える．

リズムが存在する．

(1) u ∈/ A, v ∈ A となる辺 e = {u, v}u ∈/ U ∩ PNλ (v) で あ れ ば ，valU (v) に よ っ て∑/Aa∈A valU (a) に α · wuv がカウントされる一方，u ∈であるため，u からカウントされることはない．故に，∑a∈A valU (a) に α · wuv がちょうど 1 回カウントされα ∈ [1/3, 1] のとき 2kd+k (kd)O(log(kd)) nO(1) -時間アルゴ

Proof. 補題 3.1 と，最適解 S ∗ が φG (S ∗ ) を最大化するサ
イズ k = |sol(U )| の集合であることから，サイズ k 以上のU ∈ U に対し，val(U ) =る．一方，u ∈ U ∩PNλ (v) であるとき，valU (v) によって∑a∈A valU (a) に α·wu,v +(1−3α)·wuv = (1−2α)·wuv∑valU (v) ≤ φG (sol(U )) ≤ φG (S)v∈sol(U )がカウントされ，u ∈/ A から，u からカウントされる∑ことはない．故に， a∈A valU (a) に (1 − 2α) · wuv がが成り立つ．また特に Ũ について，sol(Ũ ) がちょうど 1 回カウントされる．

より，一般性を失うことなく，d-後順序 λ において，u は vカウントされる．一方 v ∈/ PNλ (u) であるので，valU (u)に α · wuv がちょうど 1 回カウントされる．よって，∑a∈A valU (a) に (1−2α)·wuv +α ·wuv = (1−α)·wuv
がちょうど 1 回カウントされる．
従って，u, v ∈ A である辺 e = {u, v} に関して，(1−α)wuv∑
だけ a∈A valU (a) に計上され，ちょうど 1 つの端点が Aに含まれる辺 e = {u, v} の重みは高々 max{α, 1 − 2α}wuv
だけ計上される．このとき，α ≥ 1/3 であれば α ≥ 1 − 2αであるため，α ≥ 1/3 について

∑valU (a) ≤ (1 − α) · m(A) + α · m(A, V (G) \ A)v∈sol(Ũ )valŨ (v) ≥∑valŨ (s) = φG (S ∗ )s∈S ∗と な る ．以 上 か ら ，val(U ) が 最 大 と な る U に つ いて ，val(U ) = φG (S ∗ ) が 成 り 立 つ ．ま た ，val(U ) ≤φG (sol(U )) ≤ φG (S ∗ ) から sol(U ) は最適解 S ∗ に一致し，φG (sol(U )) = val(U ) が言える．故に，最も価値の大きい
U ∈ U について，sol(U ) を返せばよい．
最後に計算時間について述べる．[5] より，(n, l)-台集合はl O(log l)

2ln log n-時間で構成可能である．各 U ∈ U に対して，valU (v) は多項式時間で計算できる．l := min{n, k+kd}であることに注意すると，アルゴリズム全体の計算時間は2kd+k (kd)O(log(kd)) nO(1) となる．
α ∈ [0, 1/3] である最小 α-FCGP についても同様の議論で 2kd+k (kd)O(log(kd)) nO(1) -時間アルゴリズムが設計でa∈Aきる．

= φG (A)定理 3.2. α ∈ [0, 1/3] である最小 α-FCGP に対して，が成り立つ．

2kd+k (kd)O(log(kd)) nO(1) -時間アルゴリズムが存在する．

補題 3.2. 最大 α-FCGP の最適解 S ∗ に対し，φG (S ∗ ) =∑s∈S ∗ valŨ (s) となる．

Proof.

∑val(Ũ ) =の右側にある，すなわち λ(v) < λ(u) であるとする．に α·wu,v +(1−3α)·wuv = (1−2α)·wuv がちょうど 1 回valŨ (v)を最大化するような U 上の k 頂点であることと，補題 3.2( 2 ) 両端点を A に持つ辺 e = {u, v}u ∈ A ⊆ U より，u ∈ PNλ (v)∩U である．故に，valU (v)∑∑s∈S ∗ valŨ (s) について，ちょうど 1 つの S∗に含まれる端点を持つ辺 e に関して αwe が計上され，両端点がS ∗ に含まれる辺 e に関して (1 − α)we が計上されることを示せば十分である．

(1) u ∈/ S ∗ , v ∈ S ∗ となる辺 e = {u, v}u∈/ (PNλ (v) ∩ Ũ ) より，α · wuv が valU (v) にちょう
ど 1 回カウントされる．u ∈/ S ∗ より，結局 α · wuv が∑s∈S ∗ valŨ (s) にもちょうど 1 回カウントされる．
c 2023 Information Processing Society of Japan⃝4. まとめ
本論文では，Panolan ら [6] の最大 k-部分頂点被覆問題に対するアルゴリズムを一般化することによって，最大（最小）α-FCGP に対する解サイズ k と縮退数 d に関する固定パラメータ容易アルゴリズムを設計した．今後の研究として，アルゴリズムの高速化，および他のグラフパラメータに関するパラメータ化計算量などが挙げられる．
謝辞 本研究は JSPS 科研費 JP21H05852，JP21K17707，

JP22H00513 の助成を受けたものです．

3情報処理学会研究報告
IPSJ SIG Technical Report

参考文献
[1]

[2]

[3]

[4]

[5]

[6]

[7]

Edouard Bonnet, Bruno Escoﬃer, Vangelis Th. Paschos,and Emeric Tourniaire. Multi-parameter analysis for local
graph partitioning problems: Using greediness for parameterization. Algorithmica, 71(3):566–580, 2015.
Tomohiro Koana, Christian Komusiewicz, André Nichterlein, and Frank Sommer. Covering many (or few) edges
with k vertices in sparse graphs. In Petra Berenbrink andBenjamin Monmege, editors, 39th International Symposium on Theoretical Aspects of Computer Science,STACS 2022, March 15-18, 2022, Marseille, France(Virtual Conference), volume 219 of LIPIcs, pages 42:1–42:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2022.
Don R. Lick and Arthur T. White. k-degenerate graphs.
Canadian Journal of Mathematics, 22(5):1082–1096,
1970.
David W. Matula and Leland L. Beck. Smallest-last ordering and clustering and graph coloring algorithms. J.
ACM, 30(3):417–427, 1983.
Moni Naor, Leonard J. Schulman, and Aravind Srinivasan. Splitters and near-optimal derandomization. In36th Annual Symposium on Foundations of Computer
Science, Milwaukee, Wisconsin, USA, 23-25 October
1995, pages 182–191. IEEE Computer Society, 1995.
Fahad Panolan and Hannane Yaghoubizade. Partial vertex cover on graphs of bounded degeneracy. In Alexander S. Kulikov and Sofya Raskhodnikova, editors, Computer Science - Theory and Applications - 17th International Computer Science Symposium in Russia, CSR
2022, Virtual Event, June 29 - July 1, 2022, Proceedings, volume 13296 of Lecture Notes in Computer Science, pages 289–301. Springer, 2022.
Hadas Shachnai and Meirav Zehavi. Parameterized algorithms for graph partitioning problems. Theory Comput.
Syst., 61(3):721–738, 2017.

c 2023 Information Processing Society of Japan⃝4