Skip to content
DraconiticResearch
Search Sources API
194,220 studies31 sourcesUpdated 27 min ago
PreprintCC BY 4.0arXiv

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

  • Yihan Chen
  • Jialin He
  • Xihe Li
  • Jie Ma
  • Tianying Xie
Open at sourcePDFDOICite

Abstract

For a fixed graph T and a fixed nonempty family ℱ of graphs, let ex(G, T, ℱ) denote the maximum number of copies of T in an ℱ-free subgraph of a graph G. Alon and Shikhelman~[Algorithmica, 2022] conjectured that if e(T)> 0 and no member of ℱ is a subgraph of a blow-up of T, then for every ε>0, approximating ex(G, T, ℱ) within an additive error nv(T)−ε is NP-hard for an input graph G on n vertices. The previously established general cases for this conjecture include ex(G, K2, ℱ) by Alon, Shapira and Sudakov~[Ann. of Math., 2009], and ex(G, Km, Kk) 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=minF∈ ℱχ(F).

Related

  1. NP-Hardness of Generalized-Turán Graph Modification Problems
    Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Generalized Turán problems for shorter even cycles
    Zhen Liu, Chuanshu Wu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Spectral Generalized Turán Problems for Expansion Hypergraphs
    Zijuan Cheng, Yongchun Lu, Liying Kang
    The Electronic Journal of CombinatoricsPeer-reviewedCC BY 4.0Full textCombinatorics & discrete mathematicsCrossref
  4. Metric Self-Dual Completion and Optimal Additive Hardness for Quantum and Graph-State Distance
    Rafail Ostrovsky
    arXivPreprintarXiv licenceFull textGeneral mathematicsQuantum physics & quantum informationarXiv
  5. Turán-type extremal problems for unbalanced signed graphs
    Linfeng Xie, Keheng Zhu, Xiaogang Liu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{chen2026nphardness,
  title = {{NP-hardness of additive approximation for generalized Turán problems}},
  author = {Yihan Chen and Jialin He and Xihe Li and Jie Ma and Tianying Xie},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.16358},
  eprint = {2610.16358},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.16358},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - NP-hardness of additive approximation for generalized Turán problems
AU  - Yihan Chen
AU  - Jialin He
AU  - Xihe Li
AU  - Jie Ma
AU  - Tianying Xie
PY  - 2026
DA  - 2026/10/12
PB  - arXiv
DO  - 10.48550/arxiv.2610.16358
UR  - https://arxiv.org/abs/2610.16358
AB  - For a fixed graph T and a fixed nonempty family ℱ of graphs, let ex(G, T, ℱ) denote the maximum number of copies of T in an ℱ-free subgraph of a graph G. Alon and Shikhelman~[Algorithmica, 2022] conjectured that if e(T)> 0 and no member of ℱ is a subgraph of a blow-up of T, then for every ε>0, approximating ex(G, T, ℱ) within an additive error n^v(T)−ε is NP-hard for an input graph G on n vertices. The previously established general cases for this conjecture include ex(G, K_2, ℱ) by Alon, Shapira and Sudakov~[Ann. of Math., 2009], and 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∈ ℱχ(F).
ER  -