{"id":"arxiv/2610.16358","url":"https://arxiv.org/abs/2610.16358","tags":["cs.CC","math.CO"],"score":0,"title":"NP-hardness of additive approximation for generalized Turán problems","domain":"cs.CC","source":"arxiv","authors":["Yihan Chen","Jialin He","Xihe Li","Jie Ma","Tianying Xie"],"reviews":0,"subject":"cs.CC","summary":"For a fixed graph $T$ and a fixed nonempty family $\\mathcal{F}$ of graphs, let $\\operatorname{ex}(G, T, \\mathcal{F})$ denote the maximum number of copies of $T$ in an $\\mathcal{F}$-free subgraph of a graph $G$. Alon and Shikhelman~[Algorithmica, 2022] conjectured that if $e(T)> 0$ and no member of $\\mathcal{F}$ is a subgraph of a blow-up of $T$, then for every $\\varepsilon>0$, approximating $\\operatorname{ex}(G, T, \\mathcal{F})$ within an additive error $n^{v(T)-\\varepsilon}$ is NP-hard for an input graph $G$ on $n$ vertices. The previously established general cases for this conjecture…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-12","reactions":{}}