閉路検出問題の計算複雑性

グラフ $H$ を固定し, $H$-Detection という問題を考えます. この問題はグラフ $G$ が入力で与えられたときに $G$ が $H$ を部分グラフとして含むかどうかを判定する問題です.

例えば, $H$ が長さ$|V(G)|$ の閉路だとするとこれはハミルトン閉路問題になるのでNP-困難です. 一方で $H$ が辺数 $|V(G)|/2$ のマッチングならば完全マッチングを含むかどうかの判定問題になるので, 多項式時間で解けます. それでは, どのような$H$に対して $H$-Detection は多項式時間で解けるのでしょうか？

この話はグラフアルゴリズムの分野でよく研究されている分野であり, 結論から言うと未解決なのですが, $H$のサイズをパラメータとしたときに$H$-Detectionは「木幅がunbounded ならばW[1]-困難である」という予想が有ります[1] (逆に木幅がboundedならばcolor codingでFPT時間で解けます). 本記事では $H$を様々な長さの閉路としたときどのような結果が知られているかについてまとめていきます. 基本的に$n=|V(G)|$, $m=|E(G)|$ とします.

$k$-cycle

一般の$k$に対しては color coding というアルゴリズムによって, $2^{O(k)}\cdot n^{\omega}$時間で解けます ($n\times n$の行列積が$O(n^{\omega})$ 時間でできるとします. 2019年6月1日現在では, $\omega\approx 2.373$ です).

$k$が定数だとしましょう. 実は, 現状では$k$の偶奇によって計算量が変わります. $k$が奇数のときはこれまで知られている最速のアルゴリズムは $O(n^{\omega})$ 時間です. 例えば $k=3$ の場合は隣接行列の3乗を計算して体格成分だけを見れば良いですね. 一方で$k$が偶数のときは, $O(n^2)$で解くアルゴリズムが知られています[2]. 例えば$k=4$の時は以下の単純なアルゴリズムで四角形を見つけることができます. ただし $N(u)$は頂点$u$の隣接頂点の集合とします.

このアルゴリズムでは配列 $\mathrm{T}[i][j]$ は二頂点$ij$間の長さ2のパスをカウントしていて, もし$\mathrm{T}[i][j]\geq 2$ なる$ij$が見つかったらその瞬間に四角形が有ると判定してアルゴリズムを終了します. 配列$\mathrm{T}$の各要素は高々2回しかアクセスされないはず (2回アクセスしたらその瞬間にアルゴリズムはtrueを返して終了する) なので, 計算時間は$O(n^2)$になるわけです.

また, 辺数$m$に関しては近年にもう少し早いアルゴリズムが知られていたり[2]して, 自分が把握する限りをまとめるとこんな感じになります.

ハミルトン閉路

ハミルトン閉路はTSPで使うDPを考えると$O(2^n n^2)$時間で解くことができるのですが, それでは$O(1.99^n)$時間で解けるのでしょうか？ (乱択を許せば)できることが知られています[4]. アルゴリズムではまず, 入力のグラフ$G$を使ってある多変数多項式 $P$ を構成し, $P$が恒等的に$0$かどうかを乱択で判定するというものです. ここで構成する多項式$P$は, 「$P$が恒等的に0 iff グラフがハミルトン閉路を持つ」という性質を満たすようなものを上手く構成します. したがって多項式が恒等的に0かどうかの判定が出来る決定的アルゴリズムがあればハミルトン閉路の検出も決定的に出来るようになります. CyganらによるFPT algorithmの本[5]の10.4.2に分かりやすく解説されているので興味のある方はどうぞ.

[1]. M. Grohe, The complexity of homomorphism and constraint satisfaction problems seen from the other side, J. ACM, 2007.

[2]. R. Yuster and U. Zwick, Finding even cycles even faster, SIAM J. Discrete Math, (1997).

[3] S. Dahlgaard, M. B. T. Knudsen, M. Stöckel, Finding even cycles faster via capped k-walks, In Proc. of STOC2017.

[4]. A Björklund, Determinant sums for undirected Hamiltonicity, SIAM J. COMPUT., 2014.

[5]. M. Cygan, F. V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, S. Saurabh, Parameterized Algorithms, Springer Publishing Company, 2015.