{"id":"arxiv/2610.16025","url":"https://arxiv.org/abs/2610.16025","tags":["cs.DS","cs.DM","cs.LO","math.CO"],"score":0,"title":"QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators","domain":"cs.DS","source":"arxiv","authors":["Édouard Bonnet","Yeonsu Chang"],"reviews":0,"subject":"cs.DS","summary":"A hereditary graph class has strongly edge-sublinear separators if, for some constant $0 \\leqslant b < 1$, every graph in the class with $m$ edges admits a balanced separator of size $\\mathcal O(m^b)$. We show that Max Weight Independent Set (MWIS) admits a deterministic quasipolynomial-time approximation scheme (QPTAS) on every such class. In particular, this applies to graphs excluding any fixed graph as an induced minor, by a separator theorem of Korhonen and Lokshtanov [SODA 2024]. Our theorem generalizes the QPTASes for axis-parallel rectangles [Adamaszek and Wiese, FOCS 2013] and…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-12","reactions":{}}