2025/10/10 by Mats Vroon, Vroon, Mats, Hans L. Bodlaender +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2510.09432
openalex publication_date 2025/10/10 · openalex created_date 2025/10/14 · openalex updated_date 2026/07/28
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.2972n). 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 (2)/(3)(n-1), then G does not contain a stable cutset. Furthermore, we provide a polynomial-time algorithm for graphs where δ≥ \tfrac12n, and a similar kernelisation algorithm for graphs where δ= \tfrac12n - 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 3-Colouring problem with the same minimum degree constraint, leading to an improved exact algorithm as well.