Additive Approximation of Generalized Turan Questions

被引：3

作者：

Alon, Noga ^{[1
,2
]}

Shikhelman, Clara ^{[3
]}

机构：

[1] Princeton Univ, Dept Math, Princeton, NJ 08544 USA

[2] Tel Aviv Univ, Sch Math, Tel Aviv, Israel

[3] Tel Aviv Univ, Sackler Sch Math, Tel Aviv, Israel

来源：

ALGORITHMICA | 2022年 / 84卷 / 02期

基金：

以色列科学基金会;

关键词：

Graph approximation algorithms; Generalized Turan problems; Graph modifications; Regularity lemma; COMPLEXITY; GRAPH; SUBGRAPHS;

D O I：

10.1007/s00453-021-00899-4

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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 epsilon > 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 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 F for which no significantly better approximation can be found in polynomial time unless P = NP.

引用

页码：464 / 481

页数：18