Delphi.science

Induced-Minor-Free Graphs Admit a Star-Based Separator of Size $\tilde{O}(\sqrt{n})$

Source: arxiv.org/abs/2611.11513

Arnold Filtser, Nikolai Karol, Hung Le, Florian Lehner

arXivarxiv/2611.11513Nov 8, 2026cs.DSscore 0

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.

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.11513
curl -X POST /api/v1/records/arxiv/2611.11513/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.11513/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'