Additive Approximation of Generalized Turán Questions

Noga Alon, Clara ShikhelmanAlgorithmica 2018

TL;DR

This paper tackles the problem of approximating the maximum number of copies of a fixed graph $T$ within an $F$-free subgraph of a larger graph $G$. The authors present a polynomial-time algorithm that provides an additive approximation, proving that for many graph classes, significantly better approximations are NP-hard.

What Problem Does This Paper Address?

The paper delves into a generalization of the classical Turán problem, which asks for the maximum number of edges in a graph that does not contain a specific subgraph. Here, the problem is extended to counting copies of a fixed graph $T$ within a subgraph of $G$ that is "free" from a family of forbidden graphs $F$. This is framed as a graph modification problem: given $G$, $T$, and $F$, we want to find an $F$-free subgraph of $G$ that maximizes the number of $T$ copies. The core questions are: can we efficiently approximate this maximum number, and if so, how good can that approximation be?

Methods

The authors leverage Szemerédi's Regularity Lemma as a cornerstone of their approach. This powerful combinatorial tool allows them to decompose large graphs into "regular" pairs of vertex sets, simplifying the graph structure. They then translate the problem of counting $T$ copies in the original graph $G$ to a problem of counting homomorphisms in a smaller "partition graph" derived from the regularity lemma. This reduction, combined with techniques from extremal graph theory and the concept of graph blow-ups, allows them to establish their main results on additive approximation and NP-hardness.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The Power of Regularity: Szemerédi's Regularity Lemma is not just a theoretical tool; it's the algorithmic engine that enables the approximation. By breaking down the graph, the problem becomes manageable.
  • Bridging Graph Counting and Homomorphisms: The clever reduction from counting subgraph copies to counting homomorphisms in a partition graph is a key insight. This allows the use of existing results and techniques for homomorphism problems.
  • Additive vs. Multiplicative Approximation: The paper distinguishes between additive and multiplicative approximations. While multiplicative approximations are often hard to achieve, they show that a constant additive error is achievable for a broad class of problems.
  • Blow-ups as a Barrier: The concept of "blow-ups" of graphs plays a crucial role in identifying when better-than-additive approximations are NP-hard. If the forbidden family $F$ contains a subgraph that is a blow-up of $T$, then better approximations are possible. Otherwise, NP-hardness emerges.

Key Results

  • Theorem 1.4: For any fixed graph $T$, finite family of forbidden graphs $F$, and constant $\epsilon > 0$, there exists a polynomial-time algorithm that approximates $ex(G, T, F)$ (the maximum number of $T$ copies in an $F$-free subgraph of $G$) within an additive error of $n^{\nu(T)-\epsilon}$.
  • Conjecture 1.8: For graphs $T$ and $F$ where no graph in $F$ is a subgraph of a blow-up of $T$, approximating $ex(G, T, F)$ within an additive error of $n^{\nu(T)-\epsilon}$ is NP-hard. This conjecture is supported by several specific results.
  • Theorem 1.7: Demonstrates NP-hardness for approximating $ex(G, K_m, K_k)$ with a specific additive error, providing a concrete instance of the conjecture.

Limitations and Future Work

The paper focuses on additive approximations and the conditions under which better approximations are NP-hard. The full assertion of Conjecture 1.8 remains open. Future work could explore:

  • Improving the Additive Error: Can the additive error term be further reduced or characterized more precisely?
  • Exact Calculation: Identifying more general conditions under which $ex(G, T, F)$ can be computed exactly in polynomial time.
  • Specific Graph Classes: Investigating the approximation complexity for specific families of graphs $T$ and $F$, particularly those not covered by the current NP-hardness results.
  • Algorithmic Improvements: While polynomial time is achieved, exploring more efficient algorithms or tighter bounds on the polynomial degree would be valuable.

Summary updated

Abstract

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 $ε>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 $ε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$.
BibTeX
@article{alon2018additive,
  author = {Noga Alon and Clara Shikhelman},
  title = {{Additive Approximation of Generalized Turán Questions}},
  journal = {Algorithmica},
  year = {2018},
}
Figure