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 thesis, we present a new exact algorithm for the Stable Cutset problem. 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 two variants of the \scs problem based on degree constraints. For graphs with minimum degree δ = c * n, where c < 1, we derive an upper bound for c such that no stable cutset exists when c exceeds this bound. Furthermore, we provide a polynomial-time algorithm for graphs where δ ≤ 1/2 * n, and a similar kernelization algorithm for graphs where δ = 1/2 * n - k. Finally, we prove that the Stable Cutset problem 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-Coloring problem with the same minimum degree constraint, leading to an improved exact algorithm as well.