A complete dichotomy theorem on the sparse $t$-Uniform Hypergraphicality Problem

Abstract

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}}_{\hat{I}{\pm }^{\prime },\hat{I}\pm }$. For any fixed $t\ge 3$, given parameters $0\le \hat{I}{\pm }^{\prime }\le \hat{I}\pm <t-1$, the input consists of degree sequences $D$ of length $n$ with degrees between $n^{\hat{I}{\pm }^{\prime }}$ and $6n^{\hat{I}}\pm$. We show that the problem is NP-complete whenever $\hat{I}{\pm }^{\prime }\le \frac{t(\hat{I}\pm -1)+1}{t-1}$, and solvable in linear time when $\hat{I}{\pm }^{\prime }>\frac{t(\hat{I}\pm -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 $\hat{I}\text{c◯}(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.

18 pages