## Abstract

For graphs G and T, and a family of graphs F let ex (G, T, F) denote the maximum possible number of copies of T in an 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 F and constant ϵ> 0 there is a polynomial time algorithm that approximates ex (G, T, F) for an input graph G on n vertices up to an additive error of ϵ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 F for which no significantly better approximation can be found in polynomial time unless P= NP.

Original language | English (US) |
---|---|

Pages (from-to) | 464-481 |

Number of pages | 18 |

Journal | Algorithmica |

Volume | 84 |

Issue number | 2 |

DOIs | |

State | Published - Feb 2022 |

## All Science Journal Classification (ASJC) codes

- General Computer Science
- Computer Science Applications
- Applied Mathematics

## Keywords

- Generalized Turan problems
- Graph approximation algorithms
- Graph modifications
- Regularity lemma