{"id":"arxiv/2611.11513","url":"https://arxiv.org/abs/2611.11513","tags":["cs.DS","math.CO"],"score":0,"title":"Induced-Minor-Free Graphs Admit a Star-Based Separator of Size $\\tilde{O}(\\sqrt{n})$","domain":"cs.DS","source":"arxiv","authors":["Arnold Filtser","Nikolai Karol","Hung Le","Florian Lehner"],"reviews":0,"subject":"cs.DS","summary":"Given an $H$-induced-minor-free graph $G$ with $n$ vertices, we construct a balanced separator of $G$ consisting of $\\tilde{O}(|V(H)|\\sqrt{n})$ star subgraphs. Our result is an induced-minor-free analog of the famous separator theorem for $H$-minor-free graphs by Alon, Seymour, and Thomas [J. Amer. Math. Soc., 1990]. A key idea in our construction is a new decomposition of $H$-induced-minor-free graphs, analogous to the cop decomposition for $H$-minor-free graphs by Andreae [J. Combin. Theory Ser. B, 1986]. We also discuss several algorithmic applications of our result.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-08","reactions":{}}