Jie Ma

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

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 sub...