Exact and Parameterized Algorithms for the Independent Cutset Problem

DOI10.1007/978-3-031-43587-4_27arXiv2307.02107MaRDI QIDQ6442663

Uéverton S. Souza, Johannes Rauch, Dieter Rautenbach

Publication date: 5 July 2023

Abstract: The Independent Cutset problem asks whether there is a set of vertices in a given graph that is both independent and a cutset. Such a problem is

e x t s f N P

-complete even when the input graph is planar and has maximum degree five. In this paper, we first present a

m a t h c a l O^{*} (1.442 3^{n})

-time algorithm for the problem. We also show how to compute a minimum independent cutset (if any) in the same running time. 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 that are not bounded by a function of the clique-width of the input. We present

e x t s f F P T

-time algorithms for the problem considering 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

a l p h a

-domination, which allows us to identify more fixed-parameter tractable and polynomial-time solvable cases.

Mathematics Subject Classification ID

Theory of computing (68Qxx)