Exact and Parameterized Algorithms for the Independent Cutset Problem

DOI10.1007/978-3-031-43587-4_27MaRDI QIDQ6442663zbMATH OpenFDO

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

Publication date 5 July 2023

Full work available at URL https://doi.org/10.1007/978-3-031-43587-4_27

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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 $extsfNP$-complete even when the input graph is planar and has maximum degree five. In this paper, we first present a $mathcal{O}^{\ast }(1.4423^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 $extsfFPT$-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 $alpha$-domination, which allows us to identify more fixed-parameter tractable and polynomial-time solvable cases.

Recommendations

• Exact and parameterized algorithms for the independent cutset problem
• \((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel
• \((k,n-k)\)-max-cut: an \({\mathcal O}^*(2^p)\)-time algorithm and a polynomial kernel
• Fragile graphs with small independent cuts
• An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs

Cited in

(5)

• On conflict-free cuts: algorithms and complexity
• Exact and parameterized algorithms for the independent cutset problem
• Revisiting extremal graphs having no stable cutsets
• Forest cuts in sparse graphs
• On polynomial kernelization for stable cutset

This page was built for publication: Exact and Parameterized Algorithms for the Independent Cutset Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6442663)