NP-Hardness of Generalized-Turán Graph Modification Problems

Source abstract

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 $\mathcal{H}$. In particular, we obtain an elementary proof of the Alon-Shapira-Sudakov result when $\mathcal{H}$ is finite.