PaperlayerView exact revision on arXiv

Source-linked AI summary

NP-hardness of additive approximation for generalized Tur\'{a}n problems

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

arXiv:2610.16358v1cs.CCmath.CO

TL;DR

Generalized Turán hardness was conjectured for pairs (T, F) where no forbidden graph is a subgraph of a blow-up of T. This paper uses reductions from colorable-subgraph problems and proves additive-error NP-hardness for bipartite T and several further classes, including clique T.

  • Problem

    The conjecture asks whether approximating ex(G, T, F) within n^v(T)-ε is NP-hard when e(T) > 0 and no F in F is a subgraph of a blow-up of T.

    Source: §1 · p. 2

  • Method

    The reductions encode a hard colorable-subgraph value in an auxiliary graph’s T-count, using leaf additions and blow-ups or symmetric rooted extensions.

    Source: §3.2 · p. 11, §4 · p. 15, §4.1 · p. 18

  • Results

    The conjectured additive-error hardness holds for every bipartite T and for further classes including complete multipartite T and pairs with min_F χ(F) > ω(T).

    Source: §1 · p. 3

  • Takeaways & Limitations

    The results apply to both arbitrary-subgraph and spanning-subgraph parameters, and the bipartite theorem permits finite or infinite F.

    Source: §1 · p. 3

    The complexity statements fix T, F, and ε; only the host graph G is part of the input.

    Source: §1 · p. 2

Abstract

from arXiv · show

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}}\chi(F)$.

1 Introduction

The paper confirms the generalized Turán hardness conjecture for bipartite T and proves it for several further classes, including clique T. Its results cover both arbitrary and spanning subgraphs, with finite or infinite forbidden families.

1 Introduction

  • The conjecture had previously been established in general for T = K_2 and for T = K_m with F = {K_k}, while a further result covered 3-connected T and forbidden graphs.The cited 3-connected case gives hardness at additive error n^v(T)-2-ε.Source: §1 · p. 2
  • For every bipartite T with e(T) > 0 and admissible nonempty F, approximating either ex(G, T, F) or ex′(G, T, F) within n^v(T)-ε is NP-hard.The family F may be finite or infinite.Source: §1 · p. 3
  • For complete r-partite T with r ≥ 3, positive part sizes, and no F in F contained in a blow-up of T, both parameters are NP-hard to approximate within n^v(T)-ε.Source: §1 · p. 3
  • If min_F χ(F) = k > ω(T) and every F contains K_k, then both parameters are NP-hard to approximate within n^v(T)-ε.Source: §1 · p. 3
  • If k = min_F χ(F) ≥ 3 and T has an edge e with χ(T) ≤ k − 1 and χ(T/e) ≤ k − 1, both parameters are NP-hard to approximate within n^v(T)-ε.Source: §1 · p. 3
  • When min_F χ(F) ≥ χ(T) + 2, both parameters are NP-hard to approximate within n^v(T)-ε.The paper derives this corollary from Theorem 1.8 and χ(T/e) ≤ χ(T) + 1.Source: §1 · p. 3

2 Proof sketch and preliminaries

The proof reduces a hard colorable-subgraph problem to generalized Turán approximation by constructing an auxiliary graph whose T-count tracks the source optimum. Preliminaries establish the transfer and rounding tools, along with conditions relating the two parameter conventions.

2 Proof sketch and preliminaries

  • The reduction encodes the NP-hard Max r-Colorable Subgraph problem, using z = cut_{k−1}(G) for k = min_F χ(F), in the T-count of a constructed graph Z.Source: §2 · pp. 3–4
  • The construction bounds the two target parameters between L + Sz − a and L + Sz + b, using iterative leaf additions and blow-ups for Theorem 1.5 and symmetric rooted extensions for Theorems 1.6–1.8.Source: §2 · p. 4
  • A source subgraph attaining z yields the lower bound, while a random-transversal argument bounds arbitrary F-free subgraphs by relating their T-copies to expected edges in a random spanning subgraph of G.Source: §2 · p. 4
  • Choosing parameters so the total error is less than S/2 lets an additive n^v(T)-ε approximation determine the integer z exactly.Source: §2 · p. 4

2.1 Preliminaries

  • For finite F, ex(G, T, F) − ex′(G, T, F) is O_T,F(1) for sufficiently large G; if every forbidden graph has no isolated vertices, the parameters are equal for every G.Source: §2.1 · p. 5
  • Theorem 2.2 transfers additive-error hardness from a source parameter z when ex′(Z, T, F) and ex(Z, T, F) are bounded around L + Sz with sufficiently small combined error.Source: §2.1 · p. 5
  • For k = min_F χ(F) ≥ 3, the cut_{k−1} corollary uses integer rounding: an error below 1/2 determines the source value exactly and transfers hardness to both target parameters.Source: §2.1 · p. 6
  • On sufficiently large graphs of minimum degree at least (1 − μ)n, cut_{k−1}(G) equals ex(G, K_2, K_k), and computing it exactly is NP-hard on that restricted class.Source: §2.1 · p. 6

3 Proof of Theorem 1.5

The section proves the conjecture for bipartite graphs T with at least one edge, using iterative leaf additions, blow-ups, and random transversals. These relate the target counts to the maximum size of a (k−1)-colorable subgraph and yield NP-hard approximation problems.

3 Proof of Theorem 1.5

  • The forbidden-family condition is equivalent to min_F∈F χ(F) ≥ 3 for bipartite T.Any forbidden graph with chromatic number at most 2 embeds in a sufficiently large blow-up of an edge of T; blow-ups of bipartite T remain bipartite.Source: §3 · p. 7

3.1 Iterative leaf additions

  • Iterative leaf additions expand hom(T, Lx(G)) over independent-set sequences, and a lexicographically maximal sequence retaining an edge ends at K2 ∪ qK1.The quotient construction preserves bipartiteness and does not increase vertex count; among edge-retaining sequences, the terminal graph has exactly two nonisolated vertices.Source: §3.1 · pp. 7–9
  • The expansion separates homomorphisms by whether their terminal graph has zero, two, or at least three nonisolated vertices, with the two-vertex contribution equal to S(x,n) · e(G).The proof controls the contribution from terminal graphs with at least three nonisolated vertices using a lexicographically maximal exponent vector.Source: §3.1 · pp. 10–11

3.2 Blow-up operation and the random-transversal argument

  • A B-blow-up Z of the leaf-augmented graph supports a random-transversal argument that bounds hom(T,J) using E[e(RJ)], A0(x,G), and S(x,n).The transversal independently selects one vertex from each cluster corresponding to V(G), retaining an edge of G when the selected pair is an edge of J.Source: §3.2 · pp. 11–12
  • For every F-free J ⊆ Z, the random transversal has expected edge count at most z + O(n^(k−η)B^−η), with z = cut_{k−1}(G).The argument bounds excess edges by the number of K_k copies, which are controlled using the F-free subgraph induced by the original clusters.Source: §3.2 · p. 13

3.3 Finishing the proof

  • The bounds give L + Sz − a ≤ ex′(Z, T, F) ≤ ex(Z, T, F) ≤ L + Sz + b, and the combined error a + b + v(Z)^(v(T)−ε) is o(S).Source: §3.3 · pp. 14–15
  • The reduction constructs Z in polynomial time and makes L and S polynomial-time computable, so Corollary 2.3 yields NP-hardness of both approximation problems.The hardness already holds when inputs are restricted to the constructed graphs Z(G), and therefore also for arbitrary host graphs.Source: §3.3 · p. 15

4 Proofs of Theorems 1.6, 1.7 and 1.8

The section develops reductions and random-transversal bounds for the proofs of Theorems 1.6, 1.7, and 1.8, relating generalized Turán counts to computing cut_{k-1}(G). It bounds clique counts in RJ by counting copies of W in the F0-free graph J and using edge deletion, and begins a separate construction for complete multipartite T.

4 Proofs of Theorems 1.6, 1.7 and 1.8

  • For an added source-edge subgraph H, the rooted construction counts L+Xe(H) copies of T, with only an O_T error from copies using at least three source vertices.Here L counts copies in Z0, and X is the number of copies using a specified edge and exactly its two endpoints as source vertices.Source: §4 · p. 16
  • For fixed nonempty F whose minimum chromatic number is k≥3, some η=η(T,F)>0 ensures every F-free J⊆Z satisfies e(J−)≤B²z+cn^(k−η)B^(2−η).Source: §4 · pp. 16–17
  • Under Lemma 4.3’s freeness condition, approximating ex(Z,T,F) or ex′(Z,T,F) within additive error v(Z)^(v(T)-ε) is NP-hard.The reduction uses Z(G) with parameters chosen as functions of n, T, F, and ε; the constructed graphs have polynomial size.Source: §4 · p. 17

4.1 Proofs of Theorems 1.7 and 1.8

  • Theorem 1.7’s construction is F-free because it is K_k-free when ω(T)<k and every member of F contains K_k.The source-edge graph H has chromatic number at most k−1, so its blow-up contributes no K_k.Source: §4.1 · p. 18
  • Theorem 1.8’s construction is F-free when χ(T) and χ(T/e) are at most k−1 for an edge e, enabling a (k−1)-coloring of Z0+H(B).The coloring extends over auxiliary vertices by using a coloring of T when endpoint clusters differ in color, and T/e when they match.Source: §4.1 · p. 18

4.2 Proof of Theorem 1.6

  • For complete multipartite T=K_{s1,...,sr}, the construction gives each copy at most q=s3+...+sr auxiliary vertices; copies with exactly q use one edge’s auxiliary set and number S per edge.The section also bounds copies with fewer than q auxiliary vertices, then starts a random-transversal argument for the upper bound; its conclusion is not included in this part.Source: §4.2 · pp. 18–20
  • Uniformly sampled representatives from the chosen subsets are independent and uniform in their respective vertex sets, so a chosen copy of T in J yields a copy of Kr in J.This gives the proof’s link between |Yuv,a(J)| and the random graph RJ.Source: §4.2 · p. 20
  • Deleting one edge from each Kk in RJ gives ex(G, K2, Kk) ≥ e(RJ) − N(RJ, Kk), yielding an expected edge-count bound.The passage combines this inequality with Equality (4.7) and then takes expectations.Source: §4.2 · p. 21
  • Because J is F0-free and F0 is a subgraph of a sufficiently large blow-up of W, Lemma 2.5 bounds N(J, W) by c1v(Z)^(w−η).Here F0 has chromatic number k, W contains Kk, and w = v(W).Source: §4.2 · p. 21
  • For each Kk in G, its probability of appearing in RJ is bounded by counting choices of w vertices that form W in J.Each such choice occurs with probability 1/(Aw−kBw), and each copy of W in J can arise from at most cr,k choices.Source: §4.2 · p. 21

K MK. Thus P

The proof brackets both extremal quantities around L+Sz and constructs an F-free subgraph whose copies of T encode edges of a (k−1)-colorable subgraph.

K MK. Thus P

  • A spanning (k−1)-colorable H with z edges yields an F-free subgraph containing at least Sz copies of T via Z0 + H(B).Each edge of H contributes S copies of T.Source: K MK. Thus P · p. 21
  • The construction sets A := n^{v(T)+q} and B := n^β, choosing β as a fixed integer depending on T, F, and ε to satisfy (4.11).Source: K MK. Thus P · pp. 21–22
  • L+Sz−a ≤ ex′(Z, T, F) ≤ ex(Z, T, F) ≤ L+Sz+b brackets both optima around L+Sz.Source: K MK. Thus P · p. 22
  • For n ≥ N*, Z can be constructed in polynomial time, and the reduction uses a polynomial-time computable positive integer S.Source: K MK. Thus P · p. 22
  • The two approximation problems are NP-hard for arbitrary host graphs after the reduction is restricted to polynomial-time constructible graphs Z(G).The proof first establishes hardness on the restricted host class.Source: K MK. Thus P · p. 22

5 Concluding remarks

The paper establishes the conjectured hardness for several classes of graph pairs and describes the reduction framework, while identifying broader cases that remain open.

5 Concluding remarks

  • The conjecture is established for every bipartite T, every complete multipartite T, and additional pairs covered by Theorems 1.7 and 1.8.Source: §5 · p. 22
  • For any T with e(T) > 0, the conjectured hardness holds when min_{F∈F} χ(F) ≥ χ(T) + 2.Source: §5 · p. 22
  • The results apply to both ex(G, T, F) and ex′(G, T, F), extending results for ex(G, K2, F) and ex(G, Km, Kk).Source: §5 · p. 22
  • The reductions encode cut_{k−1}(G) in the T-copy maximum on an auxiliary graph Z, requiring both a feasible lower-bound construction and a matching upper bound.Source: §5 · p. 22
  • Iterative leaf additions, symmetric rooted extensions, suitable blow-ups, and random transversals provide the constructions and upper bounds in the studied cases.Source: §5 · p. 23
  • Extending the approach to the full conjecture would require constructions exploiting the absence of homomorphisms F → T, including cases with min_{F∈F} χ(F) ≤ χ(T).Source: §5 · p. 23

Declaration of generative AI use

The authors describe ChatGPT's auxiliary role and state that they developed and verified the paper's mathematical work.

Declaration of generative AI use

Related papers

Loading 2610.16358v1…