Parameterized complexity of independent set in H-free graphs

DOI10.1007/S00453-020-00730-6zbMATH Open1452.68090arXiv1810.04620OpenAlexW3036315659MaRDI QIDQ786045FDOQ786045

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)

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$.

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• 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)