{"id":"arxiv/2610.30654","url":"https://arxiv.org/abs/2610.30654","tags":["math.CO"],"score":0,"title":"NP-Hardness of Generalized-Turán Graph Modification Problems","domain":"math.CO","source":"arxiv","authors":["Lior Gishboliner","Yevgeny Levanzov","Asaf Shapira"],"reviews":0,"subject":"math.CO","summary":"For graphs $G, T$ and a graph-family $\\mathcal{H}$, let $ex(G,T,\\mathcal{H})$ denote the maximum possible number of copies of $T$ in an $\\mathcal{H}$-free subgraph of $G$. Alon and Shikhelman conjectured that for every family of graphs $\\mathcal{H}$ with $χ(H) > s$ for every $H \\in \\mathcal{H}$, it is NP-hard to compute $ex(G,K_s,\\mathcal{H})$, 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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-22","reactions":{}}