{"ID":2857611,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.09432","arxiv_id":"2510.09432","title":"On Stable Cutsets in General and Minimum Degree Constrained Graphs","abstract":"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 \u003e 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.","short_abstract":"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 gra...","url_abs":"https://arxiv.org/abs/2510.09432","url_pdf":"https://arxiv.org/pdf/2510.09432v1","authors":"[\"Mats Vroon\",\"Hans L. Bodlaender\"]","published":"2025-10-10T14:41:20Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CC\",\"cs.DM\"]","methods":"[]","has_code":false}