EUVIMEDEUVIMED entdecken
Crossref

A complete dichotomy theorem on the sparse t-uniform hypergraphicality problem

István Miklós, Miklós Ruszinkó, Bogdán Zavalnij

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →