PreprintarXiv licencearXiv
NP-Hardness of the H-Free Edge-Deletion Problem
Abstract
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.
Related
- Claw-Free and Line Graph Edge Deletion on Block Graphs
- Edge complexity of weighted graphs: involutory symmetries and NP-hardness
- Acyclic 2-edge-coloured graphs: polynomial-time linkages and colouring hardness
- A Note on the NP-Hardness on Quadratic Optimization over Doubly Stochastic Matrices and the Gromov-Wasserstein Problem
- Minimizing cumulative infections in SIS epidemic models over networks via an edge deletion algorithm
BibTeX
@misc{gishboliner2026nphardness,
title = {{NP-Hardness of the $H$-Free Edge-Deletion Problem}},
author = {Lior Gishboliner and Ethan Honest},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.09715},
eprint = {2609.09715},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.09715},
}
RIS
TY - UNPB
TI - NP-Hardness of the H-Free Edge-Deletion Problem
AU - Lior Gishboliner
AU - Ethan Honest
PY - 2026
DA - 2026/09/09
PB - arXiv
DO - 10.48550/arxiv.2609.09715
UR - https://arxiv.org/abs/2609.09715
AB - 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.
ER -