Exact and parameterized algorithms for the independent cutset problem

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 NP-complete even when the input graph is planar and has maximum degree five. We first present a O & lowast;(1.4423n)time algorithm to compute a minimum independent cutset (if any). Since the property of having an independent cutset is MSO1-expressible, our main results are concerned with structural parameterizations for the problem considering parameters incomparable with clique-width. We present FPT-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 P5-free graphs. We close by introducing the notion of alpha-domination, which generalizes key ideas of this article. (c) 2024 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).