2025-11-25T13:28:17.606015

On Stable Cutsets in General and Minimum Degree Constrained Graphs

Vroon, Bodlaender

A stable cutset is a set of vertices $S$ of a connected graph, that is pairwise non-adjacent and when deleting $S$, the graph becomes disconnected. Determining the existence of a stable cutset in a graph is known to be NP-complete. In this paper, we introduce a new exact algorithm for Stable Cutset. By branching on graph configurations and using the $O^*(1.3645)$ algorithm for the (3,2)-Constraint Satisfaction Problem presented by Beigel and Eppstein, we achieve an improved running time of $O^*(1.2972^n)$. In addition, we investigate the Stable Cutset problem for graphs with a bound on the minimum degree $Î´$. First, we show that if the minimum degree of a graph $G$ is at least $\frac{2}{3}(n-1)$, then $G$ does not contain a stable cutset. Furthermore, we provide a polynomial-time algorithm for graphs where $Î´\geq \tfrac{1}{2}n$, and a similar kernelisation algorithm for graphs where $Î´= \tfrac{1}{2}n - k$. Finally, we prove that Stable Cutset remains NP-complete for graphs with minimum degree $c$, where $c > 1$. We design an exact algorithm for this problem that runs in $O^*(Î»^n)$ time, where $Î»$ is the positive root of $x^{Î´+ 2} - x^{Î´+ 1} + 6$. This algorithm can also be applied to the \textsc{3-Colouring} problem with the same minimum degree constraint, leading to an improved exact algorithm as well.

academic

一般グラフおよび最小次数制約グラフにおける安定カットセットについて

基本情報

論文ID: 2510.09432
タイトル: On Stable Cutsets in General and Minimum Degree Constrained Graphs
著者: Mats Vroon (ユトレヒト大学), Hans L. Bodlaender (ユトレヒト大学)
分類: cs.DS (データ構造とアルゴリズム), cs.CC (計算複雑性), cs.DM (離散数学)
発表日: 2025年10月10日 (arXiv プレプリント)
論文リンク: https://arxiv.org/abs/2510.09432

概要

安定カットセット(Stable Cutset)は、連結グラフにおける頂点集合Sであり、任意の2つの頂点が隣接していない(安定性)かつSを削除するとグラフが非連結になる(カットセット性)という性質を持つ。グラフに安定カットセットが存在するかどうかを判定することはNP完全問題である。本論文は、グラフの配置に対する分岐を通じて、Beigel と Eppstein が提案した O*(1.3645) 時間複雑度の (3,2)-制約充足問題アルゴリズムを利用することで、O*(1.2972^n) の改善された実行時間を実現する新しい安定カットセット精確アルゴリズムを提案している。

さらに、本論文は最小次数δが有界なグラフ上の安定カットセット問題を研究している。グラフGの最小次数が少なくとも 2/3(n-1) である場合、G は安定カットセットを含まないことを証明している。さらに、δ≥n/2 の場合の多項式時間アルゴリズムおよび δ=n/2-k の場合の同様なカーネル化アルゴリズムを提供している。最後に、最小次数 c>1 の場合でも安定カットセット問題が NP 完全であることを証明し、O*(λ^n) 時間のアルゴリズムを設計している。ここで λ は x^(δ+2)-x^(δ+1)-6 の正根である。このアルゴリズムは同じ最小次数制約を持つ3-着色問題にも適用可能である。

研究背景と動機

問題定義と重要性

安定カットセット問題はグラフ理論における基本的な問題である。連結グラフ G=(V,E) が与えられたとき、安定カットセットは頂点部分集合 S⊆V であり、以下を満たす:

S 内の任意の2つの頂点が隣接していない(安定性)
S を削除するとグラフが非連結になる(カットセット性)

この問題は完全グラフ理論において重要な応用を持つ。Tucker は、グラフ G が k-着色可能であることと、すべての Gi∪S が k-着色可能であることが同値であることを証明した。ここで Gi は G\S の連結成分であり、S はいかなる穴上の頂点も含まない安定カットセットである。

既存手法の限界

複雑性: Chvátal が安定カットセット問題が NP 完全であることを最初に証明した
アルゴリズム効率: 既存の最良の精確アルゴリズムは Rauch らによって提案され、時間複雑度は O*(3^(n/3)) である
特殊グラフ類の研究不足: 最小次数制約グラフに関する研究は相対的に少ない

研究動機

一般グラフ上の安定カットセット問題の精確アルゴリズムを改善する
最小次数制約が問題の複雑性に与える影響を深く研究する
安定カットセットと他の問題(3-着色など)との関連性を確立する

核心的貢献

改善された精確アルゴリズム: 時間複雑度 O*(1.2972^n) の新しいアルゴリズムを提案し、以前の O*(3^(n/3)) の結果を大幅に改善した
最小次数の理論的界: 最小次数が 2/3(n-1) を超えるグラフは安定カットセットを含まないことを証明した
多項式時間アルゴリズム: δ≥n/2 のグラフに対して多項式時間アルゴリズムを提供した
カーネル化アルゴリズム: δ=n/2-k のグラフに対して、カーネルサイズが O(k) のカーネル化アルゴリズムを提供した
NP完全性結果: 最小次数 c>1 の場合でも問題が NP 完全であることを証明した
最小次数制約の精確アルゴリズム: O*(λ^n) 時間アルゴリズムを提案した。ここで λ は特定の多項式の正根である
3-着色問題への応用: アルゴリズムを3-着色問題に拡張し、改善された結果を得た