2025-11-10T03:13:00.108521

The Complexity of Contracting Bipartite Graphs into Small Cycles

Krithika, Sharma, Tale

For a positive integer $\ell \geq 3$, the $C_\ell$-Contractibility problem takes as input an undirected simple graph $G$ and determines whether $G$ can be transformed into a graph isomorphic to $C_\ell$ (the induced cycle on $\ell$ vertices) using only edge contractions. Brouwer and Veldman [JGT 1987] showed that $C_4$-Contractibility is NP-complete in general graphs. It is easy to verify that $C_3$-Contractibility is polynomial-time solvable. Dabrowski and Paulusma [IPL 2017] showed that $C_{\ell}$-Contractibility is \NP-complete\ on bipartite graphs for $\ell = 6$ and posed as open problems the status of the problem when $\ell$ is 4 or 5. In this paper, we show that both $C_5$-Contractibility and $C_4$-Contractibility are NP-complete on bipartite graphs.

academic

二部グラフを小さい閉路に縮約する問題の計算複雑性

基本情報

論文ID: 2206.07358
タイトル: The Complexity of Contracting Bipartite Graphs into Small Cycles
著者: R. Krithika、Roohani Sharma、Prafullkumar Tale
分類: cs.CC（計算複雑性理論）
発表時期/会議: 第48回グラフ理論的概念に関する国際ワークショップ（WG2022）
論文リンク: https://arxiv.org/abs/2206.07358

要約

正整数 $\ell \geq 3$ に対して、 $C_\ell$ -Contractibility 問題は、無向単純グラフ $G$ を入力として、辺の縮約操作を通じて $G$ を $C_\ell$ （ $\ell$ 個の頂点からなる誘導閉路）と同型のグラフに変換できるかどうかを判定する問題である。Brouwer と Veldman は 1987 年に、 $C_4$ -Contractibility が一般グラフ上で NP-完全であることを証明した。 $C_3$ -Contractibility は多項式時間で解くことができる。Dabrowski と Paulusma は 2017 年に、 $\ell = 6$ のとき $C_\ell$ -Contractibility が二部グラフ上で NP-完全であることを証明し、 $\ell = 4$ または $5$ のときの問題の複雑性について未解決問題を提起した。本論文は、 $C_5$ -Contractibility と $C_4$ -Contractibility の両方が二部グラフ上で NP-完全であることを証明する。

研究背景と動機

問題の背景

グラフ縮約操作：辺の縮約は、グラフ理論における基本的な操作であり、辺の両端点を削除し、新しい頂点を元の端点のすべての隣接点と接続することによってグラフを簡略化する。この操作はクラスタリング、圧縮、スパース化、およびコンピュータグラフィックスにおいて重要な応用を持つ。
閉路縮約問題： $C_\ell$ -Contractibility 問題は、与えられたグラフが辺の縮約操作を通じて $\ell$ -閉路に変換できるかどうかを判定することを要求する。この問題はグラフの「閉路性」（cyclicity）パラメータと密接に関連しており、閉路性はグラフが縮約可能な最大閉路の長さとして定義される。
複雑性研究の現状：
- $C_3$ -Contractibility：多項式時間で解可能
- $C_4$ -Contractibility：一般グラフ上で NP-完全
- $C_\ell$ -Contractibility（ $\ell \geq 5$ ）：一般グラフ上で NP-完全
- $C_6$ -Contractibility：二部グラフ上で NP-完全

研究の動機

理論的完全性： $C_4$ と $C_5$ の二部グラフ上での複雑性は、この分野における重要な未解決問題である
構造制限の影響：グラフ構造制限（二部性など）が計算複雑性に与える影響の研究
アルゴリズム設計への指針：関連するアルゴリズム設計と最適化のための理論的基礎の提供

核心的貢献

主要な理論的結果： $C_5$ -Contractibility と $C_4$ -Contractibility の両方が二部グラフ上で NP-完全であることを証明した
構成的証明：Positive NAE-SAT 問題からの多項式時間帰約を通じた構成的証明を提供した
技術的革新：
- $C_5$ 問題に対しては、二段階構成法を設計：まず非二部グラフ $H$ を構成し、その後辺の細分を通じて二部グラフ $G$ を得る
- $C_4$ 問題に対しては、二部グラフを直接構成し、その等価性を証明する
拡張結果： $C_4$ -Contractibility が直径 2 の $K_4$ -free グラフ上でも NP-完全であることを証明した

方法の詳細

タスク定義

入力：二部グラフ $G = (V, E)$ 出力：辺の縮約操作の列を通じて $G$ を $C_\ell$ （ $\ell \in \{4,5\}$ ）に変換できるかどうかを判定する制約：辺の縮約操作のみを使用でき、頂点の削除や辺の追加はできない

証明戦略

$C_5$ -Contractibility の証明

第一段階：非二部グラフ $H$ の構成 Positive NAE-SAT インスタンス $\psi$ （ $N$ 個の変数、 $M$ 個の節）が与えられたとき：

基本閉路：5 個の頂点 $V_\alpha = \{\alpha_0, \alpha_1, \alpha_2, \alpha_3, \alpha_4\}$ を追加して 5-閉路を構成する
変数装置：各変数 $X_i$ に対して、5-閉路 $C_i = (x_0^i, x_1^i, x_2^i, x_3^i, x_4^i)$ を追加し、基本閉路に接続する
節装置：各節 $C_j$ に対して、頂点 $c_j, b_j$ を追加し、適切に辺を接続する
関係の符号化：辺 $x_1^i c_j$ と $x_2^i b_j$ を通じて変数-節関係を符号化する

第二段階：二部グラフ $G$ の構成 $H$ の特定の辺集合を細分することによって二部グラフ $G$ を構成する：

辺 $\alpha_0\alpha_4$ を細分する
各 $i$ に対して、辺 $x_0^i x_4^i, x_0^i \alpha_1, x_1^i \alpha_2, x_2^i \alpha_3, x_3^i \alpha_4$ を細分する
特定の変数-節接続辺を細分する

$C_4$ -Contractibility の証明

二部グラフ $G$ の直接構成：

基本構造：頂点 $t, f \in V$ と $t', f' \in V'$ を追加し、辺 $tt', ff'$ を接続する
変数装置：各変数 $X_i$ に対して、頂点集合を追加し、適切な接続を確立する
節装置：各節 $C_j$ に対して、対応する頂点と辺を追加する
強制構造：補助頂点集合 $D$ と $D'$ を追加することによって、特定の頂点対が証拠構造内での位置関係を確保する

技術的革新点

二段階構成法： $C_5$ 問題に対して、まず非二部グラフ上で等価性を確立し、その後二部グラフに変換することで、二部グラフ上での直接構成の複雑性を回避する
証拠構造分析：「nice witness structure」概念を導入し、 $C_4$ -証拠構造の性質を体系的に分析する
帰約の正確性証明：
- 構成グラフの二部性を証明する
- 元の問題と構成グラフの等価性を証明する
- SAT 問題の解との全単射関係を確立する