NP-hardness of additive approximation for generalized Tur\'{a}n problems

Abstract

Given a graph $T$ and a 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 host 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 of $n^{v(T)-\varepsilon}$ is NP-hard for an input graph $G$ on $n$ vertices. Previous advances toward this conjecture include the resolution of the canonical case $T=K_2$ by Alon, Shapira, and Sudakov [Ann. of Math., 2009], as well as the case of $\operatorname{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 proof reductions combine several techniques, including iterative leaf additions, symmetric rooted extensions, and random transversals. Together, they encode the optimal value of the NP-hard Max $r$-Colorable Subgraph problem into the objectives $\operatorname{ex}(G, T, \mathcal{F})$ for a suitably constructed graph $G$.