Exact and parameterized algorithms for the independent cutset problem
Johannes Rauch, Dieter Rautenbach, Uéverton S. Souza · Journal of Computer and System Sciences · 2024
The Independent Cutset problem asks whether there is a set of vertices in a given graph that is both independent and a cutset. This problem is -complete even when the input graph is planar and has maximum degree five. We first present a O ⁎ ( 1.4423 n ) -time algorithm to compute a minimum independent cutset (if any). Since the property of having an independent cutset is MSO 1 -expressible, our main results are concerned with structural parameterizations for the problem considering parameters incomparable with clique-width. We present -time algorithms under the following parameters: the dual of the maximum degree, the dual of the solution size, the size of a dominating set (where a dominating set is given as an additional input), the size of an odd cycle transversal, the distance to chordal graphs, and the distance to P 5 -free graphs. We close by introducing the notion of α -domination, which generalizes key ideas of this article.