For graphs $G$ and $T$, and a family of graphs $\mathcal{ F}$ let $\mathrm{ ex}(G,T,\mathcal{ F})$ denote the maximum possible number of copies of $T$ in an $\mathcal{ F}$-free subgraph of $G$. We investigate the algorithmic aspects of calculating and estimating this function. We show that for every graph $T$, finite family $\mathcal{ F}$ and constant $\epsilon>0$ there is a polynomial time algorithm that approximates $\mathrm{ ex}(G,T,\mathcal{ F})$ for an input graph $G$ on $n$ vertices up to an additive error of $\epsilon n^{ v(T)}$. We also consider the possibility of a better approximation, proving several positive and negative results, and suggesting a conjecture on the exact relation between $T$ and $\mathcal{ F}$ for which no significantly better approximation can be found in polynomial time unless $P=NP$.
Categories: math.CO