Parameterized complexity of independent set in H-free graphs

DOI10.1007/s00453-020-00730-6zbMath1452.68090arXiv1810.04620OpenAlexW3036315659MaRDI QIDQ786045

Pierre Charbit, Édouard Bonnet, Rémi Watrigant, Nicolas Bousquet, Steé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 theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (5)

1-extendability of independent sets ⋮ Token sliding on graphs of girth five ⋮ 1-extendability of independent sets ⋮ Parameterized inapproximability of independent set in \(H\)-free graphs ⋮ Few induced disjoint paths for \(H\)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum weight independent sets in classes related to claw-free graphs
• Fundamentals of parameterized complexity
• Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
• Parameterized complexity of induced graph matching on claw-free graphs
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• Finding odd cycle transversals.
• On maximal independent sets of vertices in claw-free graphs
• Improved FPT algorithms for weighted independent set in bull-free 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
• Iterative Expansion and Color Coding
• Parameterized Complexity of Independence and Domination on Geometric Graphs
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• A Linear Recognition Algorithm for Cographs
• Kernelization Lower Bounds by Cross-Composition
• Polynomial-time algorithm for Maximum Weight Independent Set on P₆-free graphs
• Independent Set in P₅-Free Graphs in Polynomial Time
• Parameterized Algorithms

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