Parameterized inapproximability of independent set in \(H\)-free graphs

DOI10.1007/s00453-022-01052-5OpenAlexW3036033298MaRDI QIDQ5925689

Pavel Dvořák, Andreas Emil Feldmann, Ashutosh Rai, Paweł Rzążewski

Publication date: 11 April 2023

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-022-01052-5

zbMATH Keywords

approximationindependent set\(H\)-free graphsparameterized approximation

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterized complexity of independent set in H-free graphs
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Complement reducible graphs
• Some simplified NP-complete graph problems
• The chromatic number and other functions of the lexicographic product
• Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes
• Approximation Resistance from Pairwise-Independent Subgroups
• Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
• Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion
• A simple proof of the Erdos-Gallai theorem on graph sequences
• Interactive proofs and the hardness of approximating cliques
• On the Lovász Theta Function for Independent Sets in Sparse Graphs
• Approximating Maximum Clique by Removing Subgraphs
• ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network
• Reducibility among Combinatorial Problems
• From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More
• Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)
• Parameterized Complexity and Approximability of Directed Odd Cycle Transversal
• Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
• Independent Set in P₅-Free Graphs in Polynomial Time
• Parameters of Two-Prover-One-Round Game and The Hardness of Connectivity Problems
• Parameterized Algorithms
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• Parameterized inapproximability of independent set in \(H\)-free graphs
• Polynomial-time Algorithm for Maximum Weight Independent Set on P ₆ -free Graphs

This page was built for publication: Parameterized inapproximability of independent set in \(H\)-free graphs