PreprintarXiv licencearXiv
NP-Hardness of Generalized-Turán Graph Modification Problems
Abstract
For graphs $G, T$ and a graph-family ℋ, let ex(G,T,ℋ) denote the maximum possible number of copies of T in an ℋ-free subgraph of G. Alon and Shikhelman conjectured that for every family of graphs ℋ with χ(H) > s for every H ∈ ℋ, it is NP-hard to compute ex(G,Ks,ℋ), and even to approximate it up to additive error ns−δ on n-vertex graphs, for any fixed δ> 0. The case s=2 was established in a breakthrough result of Alon, Shapira and Sudakov. We prove the Alon-Shikhelman conjecture for finite families ℋ. In particular, we obtain an elementary proof of the Alon-Shapira-Sudakov result when ℋ is finite.
Related
BibTeX
@misc{gishboliner2026nphardness,
title = {{NP-Hardness of Generalized-Turán Graph Modification Problems}},
author = {Lior Gishboliner and Yevgeny Levanzov and Asaf Shapira},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.30654},
eprint = {2610.30654},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.30654},
}
RIS
TY - UNPB
TI - NP-Hardness of Generalized-Turán Graph Modification Problems
AU - Lior Gishboliner
AU - Yevgeny Levanzov
AU - Asaf Shapira
PY - 2026
DA - 2026/10/22
PB - arXiv
DO - 10.48550/arxiv.2610.30654
UR - https://arxiv.org/abs/2610.30654
AB - For graphs $G, T$ and a graph-family ℋ, let ex(G,T,ℋ) denote the maximum possible number of copies of T in an ℋ-free subgraph of G. Alon and Shikhelman conjectured that for every family of graphs ℋ with χ(H) > s for every H ∈ ℋ, it is NP-hard to compute ex(G,K_s,ℋ), and even to approximate it up to additive error n^s−δ on n-vertex graphs, for any fixed δ> 0. The case s=2 was established in a breakthrough result of Alon, Shapira and Sudakov. We prove the Alon-Shikhelman conjecture for finite families ℋ. In particular, we obtain an elementary proof of the Alon-Shapira-Sudakov result when ℋ is finite.
ER -