On Stable Cutsets in General and Minimum Degree Constrained Graphs

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.