NP-hardness of additive approximation for generalized Turán problems

Abstract

For a fixed graph $T$ and a fixed nonempty family $\mathcal{F}$ of graphs, let $\mathrm{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 $\epsilon >0$, approximating $\mathrm{ex}(G,T,\mathcal{F})$ within an additive error $n^{v(T)-\epsilon }$ is NP-hard for an input graph $G$ on $n$ vertices. The previously established general cases for this conjecture include $\mathrm{ex}(G,K_2,\mathcal{F})$ by Alon, Shapira and Sudakov~[Ann. of Math., 2009], and $\mathrm{ex}(G,K_m,K_k)$ by Alon and Shikhelman. In this paper, we confirm this conjecture for every bipartite graph $T$ and every clique $T$. Our reductions use iterative leaf additions, symmetric rooted extensions and random transversals to encode the maximum number of edges in a $(k-1)$-colorable subgraph of $G$, where $k={\min }_{F\in \mathcal{F}}\chi (F)$.

arXiv comment25 pages, 0 figures