A Complexity Dichotomy for Edge Subdivision to $H$-Free Graphs

Abstract

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.

arXiv comment26 pages