On the Reconstruction of 3-Uniform Hypergraphs from Step-Two Degree Sequences

A nonnegative integer sequence is k-graphic if it is the degree sequence of a k-uniform simple hypergraph. The problem of deciding whether a given sequence π admits a 3-uniform simple hypergraph has recently been proved to be NP-complete, after long years of research. Thus, it is helpful to find which classes of instances are polynomially solvable in order to restrict the NP-hard core of the problem and design algorithms for real-life applications. Several necessary and few sufficient conditions for π to be k-graphic, with k≥ 3, appear in the literature. Frosini et al. defined a polynomial time algorithm to reconstruct k-uniform hypergraphs having regular or almost regular degree sequences. Our study fits in this research line defining some conditions and a polynomial time algorithm to reconstruct 3-uniform hypergraphs having step-two degree sequences, i.e., π= (d, ⋯, d, d- 2, ⋯, d- 2 ). Our results are likely to be easily generalized to k≥ 4 and to other families of similar degree sequences.