2020/06/18 by Pavel Dvořák, Andreas Emil Feldmann, Dvořák, Pavel +5 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #F.2 #FOS: Computer and information sciences #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2006.10444
openalex publication_date 2020/06/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the Independent Set (IS) problem in H-free graphs, i.e., graphs excluding some fixed graph H as an induced subgraph. We prove several inapproximability results both for polynomial-time and parameterized algorithms. Halldórsson [SODA 1995] showed that for every δ>0 IS has a polynomial-time ((d-1)/(2)+δ)-approximation in K1,d-free graphs. We extend this result by showing that Ka,b-free graphs admit a polynomial-time O(α(G)1-1/a)-approximation, where α(G) is the size of a maximum independent set in G. Furthermore, we complement the result of Halldórsson by showing that for some γ=Θ(d/log d), there is no polynomial-time γ-approximation for these graphs, unless NP = ZPP. Bonnet et al. [IPEC 2018] showed that IS parameterized by the size k of the independent set is W[1]-hard on graphs which do not contain (1) a cycle of constant length at least 4, (2) the star K1,4, and (3) any tree with two vertices of degree at least 3 at constant distance. We strengthen this result by proving three inapproximability results under different complexity assumptions for almost the same class of graphs (we weaken condition (2) that G does not contain K1,5). First, under the ETH, there is no f(k)⋅ no(k/log k) algorithm for any computable function f. Then, under the deterministic Gap-ETH, there is a constant δ>0 such that no δ-approximation can be computed in f(k) ⋅ nO(1) time. Also, under the stronger randomized Gap-ETH there is no such approximation algorithm with runtime f(k)⋅ no(√(k)). Finally, we consider the parameterization by the excluded graph H, and show that under the ETH, IS has no no(α(H)) algorithm in H-free graphs and under Gap-ETH there is no d/ko(1)-approximation for K1,d-free graphs with runtime f(d,k) nO(1).