Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time

We show that the Maximum Weight Independent Set problem (MWIS) can be solved in quasi-polynomial time on H -free graphs (graphs excluding a fixed graph H as an induced subgraph) for every H whose every connected component is a path or a subdivided claw (i.e., a tree with at most three leaves). This completes the dichotomy of the complexity of MWIS in F -free graphs for any finite set F of graphs into NP-hard cases and cases solvable in quasi-polynomial time, and corroborates the conjecture that the cases not known to be NP-hard are actually polynomial-time solvable. The key graph-theoretic ingredient in our result is as follows. Fix an integer t ≥ 1. Let S t , t , t be the graph created from three paths on t edges by identifying one endpoint of each path into a single vertex. We show that, given a graph G , one can in polynomial time find either an induced S t , t , t in G , or a balanced separator consisting of O (log| V ( G )|) vertex neighborhoods in G , or an extended strip decomposition of G (a decomposition almost as useful for recursion for MWIS as a partition into connected components) with each particle of weight multiplicatively smaller than the weight of G . This is a strengthening of a result of Majewski, Masařík, Novotná, Okrasa, Pilipczuk, Rzążewski, and Sokołowski [Transactions on Computation Theory ‍2024] which provided such an extended strip decomposition only after the deletion of O (log| V ( G )|) vertex neighborhoods. To reach the final result, we employ an involved branching strategy that relies on the structural lemma presented above.

Authors

• Peter Gartland
• Daniel Lokshtanov
• Tomás Masarík
• Marcin Pilipczuk
• Michal Pilipczuk
• Pawel Rzazewski

Keywords

• Max independent set
• quasipolynomial algorithm
• subdivided claw