NP-hardness of generalized Turán approximation

Conjecture 1.8 · arXiv:1811.08750

arXiv Conjecture high confidence— first stated 2018-11-21

Authors: Noga Alon, Clara Shikhelman

Status open medium confidence

Conjecture 1.8 from arXiv:1811.08750 posits that whenever no member of the forbidden family F is a subgraph of a blow-up of T, it is NP-hard to approximate ex(G,T,F) within additive error n^{v(T)-epsilon}. The paper proves the special case T=K_m, F={K_k} with k >= m+2 (Theorem 1.7), but the general conjecture remains open. The paper was published in Algorithmica in 2022, and a 2025 survey on generalized Turán problems (arXiv:2506.03418) exists, but no follow-up resolving the full conjecture was found in the indexed literature.

Reviewer notes. The conjecture is from 2018 and no resolution was found after 5 web calls. The paper appeared in Algorithmica (2021, online; 2022 in print). A 2025 survey arXiv:2506.03418 covers generalized Turán counting problems but its full text was not accessible, so it may or may not discuss the conjecture's current status. Confidence is medium rather than high because the conjecture is 7+ years old, making absence of evidence somewhat less conclusive.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. For every graph $T$, family of graphs $\mathcal{F}$ such that no $F \in \mathcal{F}$ is a subgraph of a blow-up of $T$, and $\epsilon > 0$, it is NP-hard to approximate $\mathrm{ex}(G, T, \mathcal{F})$ up to additive error of $n^{v(T)-\epsilon}$ for a given input graph $G$ on $n$ vertices.

Context

The authors prove Theorem 1.7 as a special case (for $T = K_m$, $\mathcal{F} = \{K_k\}$ with $k \geq m+2$) and note that Proposition 1.5 covers the complementary easy regime (when some $F \in \mathcal{F}$ is a subgraph of a blow-up of $T$). They believe that excluding those easy cases no significantly better approximation than $\epsilon n^{v(T)}$ is achievable in polynomial time, leading to this conjecture. Section 6 of the paper contains further remarks on this conjecture and related open problems.

Source paper

Additive Approximation of Generalized Turán Questions
Noga Alon, Clara Shikhelman · 2018-11-21
https://arxiv.org/abs/1811.08750 PDF source