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

arXiv: https://arxiv.org/abs/2305.15738 · HTML: https://mlsanity.com/paper/2305.15738/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 May 2023.

## Built on by (most cited first, 2 of 2)

- [TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability](https://mlsanity.com/paper/2608.09538/) (2026)
- [Dynamic Location Search for Identifying Maximum Weighted Independent Sets in Complex Networks](https://mlsanity.com/paper/2505.04674/) (2025)

## Abstract (arXiv)

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 St,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 St,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, Masavr'ik, Novotn'a, Okrasa, Pilipczuk, Rzka.zewski, and Sokolowski [ICALP 2022] 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.