A complete dichotomy theorem on the sparse t-uniform hypergraphicality problem
Discrete Mathematics · 2027-02 · 350 (2) · 115435
DOI: 10.1016/j.disc.2026.115435 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Mathematics, 2027-02. Verfasst von István Miklós und 2 weiteren Autor:innen. Die Arbeit nennt 19 Literaturangaben. Gefördert von: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, European Commission, ERC.
Abstract (Originalsprache)
We prove a complete dichotomy theorem for the parameterized sparse $t$-uniform hypergraphic degree sequence problem, $\mathrm{sparse}\text{-}t\text{-}\mathrm{uni}\text{-}\mathrm{HDS}_{\alpha',\alpha}$. For any fixed $t \ge 3$, given parameters $0 \le \alpha'\le \alpha \frac{t(\alpha - 1) + 1}{t - 1}$. This establishes a sharp boundary between polynomial-time solvable and NP-complete instances, thereby characterizing the computational complexity across all degree exponent regimes. The result extends the earlier NP-completeness of dense hypergraphicality to a unified framework covering both sparse and dense regimes, revealing that even extremely sparse instances (with maximum degree $o(n)$ but $\Omega(n^{\frac{t-1}{t}})$) remain NP-complete. On the other hand, the $t$-uniform hypergraphicality solvable in linear time when the maximum degree is $o(n^{\frac{t-1}{t}})$. This dichotomy provides a comprehensive classification of the complexity landscape for hypergraphic degree sequences.
Förderung
- Nemzeti Kutatási Fejlesztési és Innovációs Hivatal
- European Commission
- ERC
Zitieren
APA
Miklós, I., Ruszinkó, M., & Zavalnij, B. (2027). A complete dichotomy theorem on the sparse t-uniform hypergraphicality problem. Discrete Mathematics, 350(2), 115435. https://doi.org/10.1016/j.disc.2026.115435
Vancouver
Miklós I, Ruszinkó M, Zavalnij B. A complete dichotomy theorem on the sparse t-uniform hypergraphicality problem. Discrete Mathematics. 2027;350(2):115435. doi:10.1016/j.disc.2026.115435
BibTeX
@article{Mikls2027,
author = {Miklós, István and Ruszinkó, Miklós and Zavalnij, Bogdán},
title = {A complete dichotomy theorem on the sparse t-uniform hypergraphicality problem},
journal = {Discrete Mathematics},
year = {2027},
volume = {350},
number = {2},
pages = {115435},
doi = {10.1016/j.disc.2026.115435}
}
EUVIMED