Additive approximation for generalized Turán problems is NP-hard

NP-hardness of additive approximation for generalized Turán problems

Computational Complexity

Summary

This paper studies a problem in graph theory where you want to find the largest subgraph of a given graph without certain forbidden patterns, while counting specific smaller subgraphs inside it. The authors show that approximating this count closely is computationally very hard (NP-hard) for a wide range of cases involving bipartite graphs and cliques. They confirm a previous conjecture about the difficulty of this problem by building complex reductions based on coloring properties of graphs. Essentially, it means no efficient algorithm can guarantee near-exact solutions for these problems unless a major breakthrough in computer science occurs.

What this means in practice

  • For algorithm designers: Use this hardness result to understand limits of efficient approximation algorithms for network substructure optimization tasks involving forbidden patterns.
  • For graph software developers: Avoid investing in near-exact additive approximation algorithms for generalized Turán problems on bipartite or clique subgraphs, focusing instead on heuristics or special cases.

A theory result. No direct application yet.

Authors

Yihan Chen, Jialin He, Xihe Li, Jie Ma, Tianying Xie

Abstract

For a fixed graph $T$ and a fixed nonempty family $\mathcal{F}$ of graphs, let $\operatorname{ex}(G, T, \mathcal{F})$ denote the maximum number of copies of $T$ in an $\mathcal{F}$-free subgraph of a graph $G$. Alon and Shikhelman~[Algorithmica, 2022] conjectured that if $e(T)> 0$ and no member of $\mathcal{F}$ is a subgraph of a blow-up of $T$, then for every $\varepsilon>0$, approximating $\operatorname{ex}(G, T, \mathcal{F})$ within an additive error $n^{v(T)-\varepsilon}$ is NP-hard for an input graph $G$ on $n$ vertices. The previously established general cases for this conjecture include $\operatorname{ex}(G, K_2, \mathcal{F})$ by Alon, Shapira and Sudakov~[Ann. of Math., 2009], and $\operatorname{ex}(G, K_m, K_k)$ by Alon and Shikhelman. In this paper, we confirm this conjecture for every bipartite graph $T$ and every clique $T$. Our reductions use iterative leaf additions, symmetric rooted extensions and random transversals to encode the maximum number of edges in a $(k-1)$-colorable subgraph of $G$, where $k=\min_{F\in \mathcal{F}}χ(F)$.
View PDFOpen arXiv