{"id":"arxiv/2604.24228","url":"https://arxiv.org/abs/2604.24228","tags":["cs.DS","math.CO"],"score":0,"title":"A Complexity Dichotomy for Edge Subdivision to $H$-Free Graphs","domain":"cs.DS","source":"arxiv","authors":["Marta Piecyk","R. B. Sandeep"],"reviews":0,"subject":"cs.DS","summary":"For a fixed graph $H$, \\HFS\\ asks whether at most $k$ edge subdivisions can make an input graph contain no induced copy of $H$. We establish a complexity dichotomy for every fixed nonempty $H$: the problem is polynomial-time solvable if every component of $H$ is a subdivided star or a subdivided bistar and at most one component is a subdivided bistar; it is NP-complete otherwise. In every NP-complete case, the Exponential Time Hypothesis rules out a $2^{o(k)}n^{O(1)}$-time algorithm. For every fixed $H$, the problem admits a $2^{O(k)}n^{O(1)}$-time algorithm.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-04-27","reactions":{}}