A Heuristic for the P-time Reconstruction of Unique 3-Uniform Hypergraphs from their Degree Sequences

One of the main problems in the wide area of graph theory is the so called reconstruction problem, that is the reconstruction of a (hyper)graph from its degree sequence. The problem remained open for many years, until in 2018 Deza et al. proved its NP hardness even for the simplest case of 3-uniform hypergraphs. As a consequence, the definition of classes of instances that allow a polynomial time reconstruction acquired relevance in order to restrict the NP-complete core of the problem. In this paper, we consider the class of instances 𝒟𝑒𝑥𝑡 defined by Ascolese et al. in 2021, and we provide some structural properties of the related 3-uniform hypergraphs. Then, we move the spotlight on its subclass 𝒟𝑒𝑥𝑡− including only those elements that are unique, i.e., two non-isomorphic 3-uniform hypergraphs sharing a degree sequence do not exist in 𝒟𝑒𝑥𝑡−. This property suggests the possibility of a polynomial time strategy for the reconstruction of its elements. We define an algorithm that allows a fast reconstruction of some instances in 𝒟𝑒𝑥𝑡−, and we further provide a heuristic to solve the same problem on the entire class. The heuristic relies on the uniqueness of the elements in 𝒟𝑒𝑥𝑡− and on geometric and algebraic features of the related 3-hypergraphs. Finally, statistics on the performance of the heuristic are provided.