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

Peter Gartland, Daniel Lokshtanov, Tomáš Masařík +3

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)…