Parameterized complexity of independent set in H-free graphs

DOI10.1007/S00453-020-00730-6MaRDI QIDQ786045zbMATH OpenOpenAlexFDO

Authors Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Rémi Watrigant, Stéphan Thomassé

Publication date 12 August 2020

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.04620

zbMATH Keywords

independent setparameterized algorithmsH-free graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parameterized complexity, tractability and kernelization (68Q27)

Abstract: In this paper, we investigate the complexity of Maximum Independent Set (MIS) in the class of $H$-free graphs, that is, graphs excluding a fixed graph as an induced subgraph. Given that the problem remains $NP$-hard for most graphs $H$, we study its fixed-parameter tractability and make progress towards a dichotomy between $FPT$ and $W[1]$-hard cases. We first show that MIS remains $W[1]$-hard in graphs forbidding simultaneously $K_{1,4}$, any finite set of cycles of length at least $4$, and any finite set of trees with at least two branching vertices. In particular, this answers an open question of Dabrowski et al. concerning $C_4$-free graphs. Then we extend the polynomial algorithm of Alekseev when $H$ is a disjoint union of edges to an $FPT$ algorithm when $H$ is a disjoint union of cliques. We also provide a framework for solving several other cases, which is a generalization of the concept of emph{iterative expansion} accompanied by the extraction of a particular structure using Ramsey's theorem. Iterative expansion is a maximization version of the so-called emph{iterative compression}. We believe that our framework can be of independent interest for solving other similar graph problems. Finally, we present positive and negative results on the existence of polynomial (Turing) kernels for several graphs $H$.

Recommendations

• Parameterized complexity of independent set in \(H\)-free graphs
• Parameterized complexity of induced \(H\)-matching on claw-free graphs
• Parameterized algorithms for the independent set problem in some hereditary graph classes
• The maximum independent set problem in subclasses of \(S_{i, j, k}\)-free graphs
• Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• scientific article; zbMATH DE number 3445275 (Why is no real title available?)
• scientific article; zbMATH DE number 7650282 (Why is no real title available?)
• A Linear Recognition Algorithm for Cographs
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• Finding odd cycle transversals.
• Fundamentals of parameterized complexity
• Improved FPT algorithms for weighted independent set in bull-free graphs
• Independent set in \(P_5\)-free graphs in polynomial time
• Independent sets in some classes of \(S_{i,j,k}\)-free graphs
• Iterative Expansion and Color Coding
• Kernelization Lower Bounds by Cross-Composition
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Maximum weight independent sets in classes related to claw-free graphs
• On maximal independent sets of vertices in claw-free graphs
• Parameterized Complexity of Independence and Domination on Geometric Graphs
• Parameterized algorithms
• Parameterized complexity of induced graph matching on claw-free graphs
• Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
• Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs

Cited in

(12)

• Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
• Few induced disjoint paths for \(H\)-free graphs
• scientific article; zbMATH DE number 7650229 (Why is no real title available?)
• 1-extendability of independent sets
• Parameterized inapproximability of independent set in \(H\)-free graphs
• Token sliding on graphs of girth five
• 1-extendability of independent sets
• Parameterized Complexity of Independence and Domination on Geometric Graphs
• Parameterized algorithms for the independent set problem in some hereditary graph classes
• H-free graphs, independent sets, and subexponential-time algorithms
• Parameterized complexity of independent set in \(H\)-free graphs
• Parameterized complexity of the maximum independent set problem and the speed of hereditary properties

This page was built for publication: Parameterized complexity of independent set in H-free graphs

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