{"id":"arxiv/2609.09715","url":"https://arxiv.org/abs/2609.09715","tags":["math.CO","cs.CC"],"score":0,"title":"NP-Hardness of the $H$-Free Edge-Deletion Problem","domain":"math.CO","source":"arxiv","authors":["Lior Gishboliner","Ethan Honest"],"reviews":0,"subject":"math.CO","summary":"For a graph $H$, the $H$-freeness edge-deletion problem is the algorithmic problem of finding, for an input graph $G$, the minimum number of edges of $G$ whose deletion turns $G$ into an $H$-free graph. We show that for every graph $H$ containing a cycle, this problem is NP-hard. This proves a conjecture of Gishboliner, Levanzov and Shapira, and completes the characterization of the complexity of the $H$-freeness edge-deletion problem, answering a question of Alon, Shapira and Sudakov.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-09","reactions":{}}