A Complexity Dichotomy for Edge Subdivision to $H$-Free Graphs
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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.24228
curl -X POST /api/v1/records/arxiv/2604.24228/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.24228/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'