TY - JOUR

T1 - QUASI-POLYNOMIAL TIME APPROXIMATION SCHEMES FOR THE MAXIMUM WEIGHT INDEPENDENT SET PROBLEM IN H-FREE GRAPHS

AU - Chudnovsky, Maria

AU - Pilipczuk, Marcin

AU - Pilipczuk, Micha L.

AU - Thomasse, Stephan

N1 - Publisher Copyright:
© 2024 Society for Industrial and Applied Mathematics Publications. All rights reserved.

PY - 2024

Y1 - 2024

N2 - In the Maximum Independent Set problem we are asked to find a set of pairwise nonadjacent vertices in a given graph with the maximum possible cardinality. In general graphs, this classical problem is known to be NP-hard and hard to approximate within a factor of n1-\varepsilon for any \varepsilon > 0. Due to this, investigating the complexity of Maximum Independent Set in various graph classes in hope of finding better tractability results is an active research direction. In H-free graphs, that is, graphs not containing a fixed graph H as an induced subgraph, the problem is known to remain NP-hard and APX-hard whenever H contains a cycle, a vertex of degree at least four, or two vertices of degree at least three in one connected component. For the remaining cases, where every component of H is a path or a subdivided claw, the complexity of Maximum Independent Set remains widely open, with only a handful of polynomial-time solvability results for small graphs H such as P5, P6, the claw, or the fork. We prove that for every such ``possibly tractable"" graph H there exists an algorithm that, given an H-free graph G and an accuracy parameter \varepsilon > 0, finds an independent set in G of cardinality within a factor of (1-\varepsilon) of the optimum in time exponential in a polynomial of log |V (G)| and \varepsilon-1. Furthermore, an independent set of maximum size can be found in subexponential time 2\scrO(|V (G)|8/9 \mathrm{l}\mathrm{o}\mathrm{g} |V (G)|). That is, we show that for every graph H for which Maximum Independent Set is not known to be APX-hard and SUBEXP-hard in H-free graphs, the problem admits a quasi-polynomial time approximation scheme and a subexponential-time exact algorithm in this graph class. Our algorithms also work in the more general weighted setting, where the input graph is supplied with a weight function on vertices and we are maximizing the total weight of an independent set.

AB - In the Maximum Independent Set problem we are asked to find a set of pairwise nonadjacent vertices in a given graph with the maximum possible cardinality. In general graphs, this classical problem is known to be NP-hard and hard to approximate within a factor of n1-\varepsilon for any \varepsilon > 0. Due to this, investigating the complexity of Maximum Independent Set in various graph classes in hope of finding better tractability results is an active research direction. In H-free graphs, that is, graphs not containing a fixed graph H as an induced subgraph, the problem is known to remain NP-hard and APX-hard whenever H contains a cycle, a vertex of degree at least four, or two vertices of degree at least three in one connected component. For the remaining cases, where every component of H is a path or a subdivided claw, the complexity of Maximum Independent Set remains widely open, with only a handful of polynomial-time solvability results for small graphs H such as P5, P6, the claw, or the fork. We prove that for every such ``possibly tractable"" graph H there exists an algorithm that, given an H-free graph G and an accuracy parameter \varepsilon > 0, finds an independent set in G of cardinality within a factor of (1-\varepsilon) of the optimum in time exponential in a polynomial of log |V (G)| and \varepsilon-1. Furthermore, an independent set of maximum size can be found in subexponential time 2\scrO(|V (G)|8/9 \mathrm{l}\mathrm{o}\mathrm{g} |V (G)|). That is, we show that for every graph H for which Maximum Independent Set is not known to be APX-hard and SUBEXP-hard in H-free graphs, the problem admits a quasi-polynomial time approximation scheme and a subexponential-time exact algorithm in this graph class. Our algorithms also work in the more general weighted setting, where the input graph is supplied with a weight function on vertices and we are maximizing the total weight of an independent set.

KW - approximation scheme

KW - hereditary graph classes

KW - maximum weight independent set

KW - three-in-a-tree

UR - http://www.scopus.com/inward/record.url?scp=85190593068&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85190593068&partnerID=8YFLogxK

U2 - 10.1137/20M1333778

DO - 10.1137/20M1333778

M3 - Article

AN - SCOPUS:85190593068

SN - 0097-5397

VL - 53

SP - 47

EP - 86

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 1

ER -