### Abstract

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_{5}, P_{6}, the claw, or the fork. We prove that for every such “possibly tractable” graph H there exists an algorithm that, given an Hfree 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 log |V (G)| and ε^{−}^{1}. That is, we show that for every graph H for which Maximum Independent Set is not known to be APX-hard in H-free graphs, the problem admits a quasi-polynomial time approximation scheme in this graph class. Our algorithm works also 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.

Original language | English (US) |
---|---|

Title of host publication | 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 |

Editors | Shuchi Chawla |

Publisher | Association for Computing Machinery |

Pages | 2260-2278 |

Number of pages | 19 |

ISBN (Electronic) | 9781611975994 |

State | Published - Jan 1 2020 |

Event | 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 - Salt Lake City, United States Duration: Jan 5 2020 → Jan 8 2020 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Volume | 2020-January |

### Conference

Conference | 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 |
---|---|

Country | United States |

City | Salt Lake City |

Period | 1/5/20 → 1/8/20 |

### All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)

## Fingerprint Dive into the research topics of 'Quasi-polynomial time approximation schemes for the maximum weight independent set problem in h-free graphs'. Together they form a unique fingerprint.

## Cite this

*31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020*(pp. 2260-2278). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 2020-January). Association for Computing Machinery.