A dichotomy theorem on the complexity of 3-uniform hypergraphic degree sequence graphicality

Abstract

We present a dichotomy theorem on the parameterized complexity of the 3-uniform hypergraphicality problem. Given $0<c_1\le c_2<1$, the parameterized 3-uniform Hypergraphic Degree Sequence problem, $3uni-HD{S}_{c_1,c_2}$, considers degree sequences $D$ of length $n$ such that all degrees are between $c_1\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)$ and $c_2\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)$ and it asks if there is a 3-uniform hypergraph with degree sequence $D$. We prove that for any $0<c_2<1$, there exists a unique, polynomial-time computable $c_1^{\ast }$ with the following properties. For any $c_1\in (c_1^{\ast },c_2]$, $3uni-HD{S}_{c_1,c_2}$ can be solved in linear time. In fact, for any $c_1\in (c_1^{\ast },c_2]$ there exists an easy-to-compute $n_0$ such that any degree sequence $D$ of length $n\ge n_0$ and all degrees between $c_1\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)$ and $c_2\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)$ has a 3-uniform hypergraph realization if and only if the sum of the degrees can be divided by $3$. Further, $n_0$ grows polynomially with the inverse of $c_1-c_1^{\ast }$. On the other hand, we prove that for all $c_1<c_1^{\ast }$, $3uni-HD{S}_{c_1,c_2}$ is NP-complete. Finally, we briefly consider an extension of the hypergraphicality problem to arbitrary $t$-uniformity. We show that the interval where degree sequences (satisfying divisibility conditions) always have $t$-uniform hypergraph realizations must become increasingly narrow, with interval width tending to $0$ as $t\to \infty$.

27 pages, 1 figure