Additive Approximation of Generalized Tur\'an Questions

DOI10.1007/S00453-021-00899-4arXiv1811.08750MaRDI QIDQ6310041FDOQ6310041

Authors: Noga Alon, Clara Shikhelman 

Publication date: 21 November 2018

Abstract: For graphs $G$ and $T$, and a family of graphs $mathcalF$ let $mathrmex(G,T,mathcalF)$ denote the maximum possible number of copies of $T$ in an $mathcalF$-free subgraph of $G$. We investigate the algorithmic aspects of calculating and estimating this function. We show that for every graph $T$, finite family $mathcalF$ and constant $epsilon>0$ there is a polynomial time algorithm that approximates $mathrmex(G,T,mathcalF)$ 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 $mathcalF$ for which no significantly better approximation can be found in polynomial time unless $P=NP$.

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

This page was built for publication: Additive Approximation of Generalized Tur\'an Questions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6310041)