Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \ (H\) -Free Graphs

. 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 \ (n^1- \) for any \ (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 \ (P₅\), \ (P₆\), 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 \ (0\), finds an independent set in \ (G\) of cardinality within a factor of \ ( (1-) \) of the optimum in time exponential in a polynomial of \ (|V (G) |\) and \ (^-1\). Furthermore, an independent set of maximum size can be found in subexponential time \ (2^O (|V (G) |^{8/9 |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. Keywordsmaximum weight independent sethereditary graph classesapproximation schemethree-in-a-treeMSC codes68R1005C6905C85