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.
The characterization of graphs and hypergraphs from their degree sequences has been one of the most challenging problems in these last decades. In the simplest case of graphs, deciding if an integer sequence is the degree sequence of a graph was solved in 1960 by Erdős and Gallai [11]. Subsequently, a number of algorithms have been developed to provide constructive proofs of this result ( [15, 18, 24]). Moving to hypergraphs, the same decision problem has been widely studied (see [7, 10, 12, 20, 21]). Recently, starting from a general and non constructive characterization theorem in [8], some relevant subclasses of degree sequences have been considered (see [3]), whose elements allow a polynomial time algorithm to compute, say reconstruct, the related hypergraphs (see [1, 5, 13, 14]). In 2018 Deza et al. proved that deciding if an integer sequence is the degree sequence of a 3-uniform hypergraph is NP-complete [9]. As a consequence, the definition of classes of degree sequences that can be reconstructed in polynomial time acquires relevance in order to limit the NP-complete core of the problem.
In their proof Deza et al. defined as a gadget a class of degree sequences that show remarkable geometrical and algebraic properties. Relying on this, in [2] the authors provided a class of degree sequences of unique 3-hypergraphs that preserve these properties and whose incidence matrices have strong symmetrical and structural specific characteristics. In this paper (Section 3), we define a suitable poset on integer triplets and we provide a quite surprising connection between 3-hypergraphs having degree sequence in and a family of ideals of . This connection allows us to further extend the class to , defined as the degree sequences of the 3-hypergraphs which correspond to ideals of . We show that the properties of the elements in move to those in . Unfortunately, the elements of lose the uniqueness property. We get it back defining the subclass − such that ⊂ − ⊂ . In Section 4, we provide a polynomial time algorithm to reconstruct two subclasses of − , which we call maximal and minimal instances. We then provide a heuristic to solve the reconstruction problem for the entire class, that turns out to work perfectly for small-size degree sequences, and whose performance decreases on increasing the size of the sequence. Despite the algorithm does not always provide the reconstruction of the whole incidence matrix, it is important to point out that the obtained partially reconstructed hypergraph is free from wrong edge insertions. This property can lead to a new research line, concerning the study of error afected degree sequences reconstruction, together with the possibility of providing bounds to the number of (non-isomorphic) 3-hypergraphs sharing the same degree sequence.
We recall the basic definitions concerning hypergraphs and we fix the notation we are going to use. A hypergraph is defined as a pair of sets = (, ) such that = {1, . . . , } is the set of vertices and ⊂ ( ) ∖ {∅} is the multiset of hyperedges (briefly, edges), with ( ) the power set of . A hypergraph is simple if it does not contain either singleton or repeated edges, and it is called -uniform (briefly, -hypergraph) if every hyperedge has exactly vertices. Given a -hypergraph and one of its vertices , the link hypergraph of in , denoted (), is defined as the hypergraph obtained from after deleting all edges not containing , and then removing from all remaining edges. The residual of , indicated − , is defined as the -hypergraph obtained from after deleting all edges containing and the vertex itself. It is worthwhile noticing that the link hypergraph () is ( − 1)-uniform, while the residual hypergraph − is -uniform. The degree of a vertex is the number of hyperedges that contain , and the degree sequence of is the list of its vertex degrees, usually arranged in non-increasing order. A common representation of a hypergraph is using its incidence matrix, that is a × binary matrix where = || and , = 1 if and only if the vertex belongs to the edge . It is clear that the column sums of the incidence matrix of a hypergraph gives its degree sequence, while the row sums gives the sequence of the edge cardinalities. If is -uniform, then the row sums is the constant vector. We observe that the property of being simple implies that all rows of the incidence matrix are diferent. 3. The class We recall that the problem of reconstructing -hypergraphs from their degree sequences is, in general, NP-hard. In [9], the authors provided a proof that relies on a reduction involving the NP-complete problem 3-partition. In an intermediary step, they defined a class of 3-hypergraphs used as gadget in the reduction. A generalization of this class, denoted , shows interesting combinatorial properties illustrated in [2], such as the uniqueness of its elements. These remarks supported the idea that the elements of can be reconstructed in polynomial time from their degree sequences.
The class is defined starting from a weakly decreasing integer sequence = (1, . . . , ), with ≥ 3 and whose elements belong to Z. We define a 3-hypergraph () with vertices 1, . . . , and whose hyperedges are the triplets (, , ) such that + + > 0 (see Fig. 1 for an example). The class is the set of all degree sequences of hypergraphs generated from a sequence of length , and the class is the union of the classes for each ≥ 3. It is known that for each sequence ∈ there exists exactly one 3-hypergraph (up to isomorphism) that realizes it (see [2]), so we will equivalently refer to the elements of either as 3-hypergraphs or as degree sequences. The following property directly follows from the construction of . Property 1. Given the degree sequence obtained from = (1, . . . , ) and the related hypergraph, if (, , ) is an edge of and < ′ < , then (, , ′ ) is also an edge of . The way of generating the elements of suggests their representation as ideals of a partially ordered set (poset). The reader is addressed to the book of D. West [25] for the definitions, main properties and notation related to the algebraic structures introduced in the sequel. So, let us define the following poset: for each positive integer , Ω is the set of triplets (1, 2, 3) where ∈ {1, . . . , } and 1 ≤ 1 < 2 < 3 ≤ . The triplets in Ω can be regarded as the hyperedges of the complete 3-uniform hypergraph defined on vertices, 1, . . . , . Then, we define the following linear extension of the ≤ order on the elements in Ω:
(1, 2, 3) ⪯ (1, 2, 3) if and only if ≤ with ∈ {1, 2, 3}.
Let = (Ω, ⪯ ) be the partially ordered set thus obtained. Given ∈ , the principal ideal ↓ {} = { ∈ s.t. ⪯ } is the intersection of all ideals that contain the element . Since is a finite poset, the union of ideals is finite and it is still an ideal and, furthermore, an ideal ⊆ can always be obtained as the finite union of principal ideals, =↓ {1, . . . , } =↓ {1} ∪ · · · ∪ ↓ { } for some 1, . . . , ∈ .
An element ∈ is maximal if there is no ∈ such that ≺ . The maximal elements of an ideal form an antichain, that is a subset ⊆ in which no two distinct elements are comparable. It is known that the antichain of its maximal elements generates an ideal, i.e., =↓ {}, and every ideal of the poset is generated by the antichain of its maximal elements [25]. So, there is a bijective correspondence between ideals and antichains of .
Proposition 1. Let be a hypergraph in and its edge set. Then, is an ideal in .
Hπ :
Example 1. The degree sequence = (
D D D × L
Iπ
Example 2. Let us consider the degree sequence * = (
can be recursively split into block graphs, each The incidence matrix of a hypergraph ∈ of them corresponding to a vertex of : the first one is the link hypergraph related to the vertex 1, denoted by (1); its degree sequence will be indicated as 1. Recursively, we define the -th block graph of to be the link hypergraph of the ( − 1)-th residual hypergraph related to the vertex . By abuse of notation, we indicate both the block graph and its degree sequence as . We underline that the name block graph is due to the fact that since is 3-uniform, then each of its link hypergraphs is a graph. Moreover, by Property 1, we can see that the incidence matrix is such that each residual graph has a block structure, in the sense that if the edge (, ) is in , then (, ′) is in too, for each ′ s.t. < ′ < . We also note that the maximal number of block graphs is − 2, when is the complete 3-hypergraph on vertices. For each block graph we consider the Ferrers diagram of its degree sequence regarded as an integer partition (see Fig. 1, the three Ferrers diagrams on the right). We represent these diagrams both with a sequence of bars or with the associated binary matrix. So, in each diagram the height of the -th bar is the degree of the vertex + in the block graph . Piling up the Ferrers diagrams of the block graphs , matching the columns that refer to the same vertex and starting, on each layer, from the -th row on, we obtain a plane partition. We recall that a plane partition of the integer of dimension × is a two-dimensional integer × matrix such that = ∑︀, , , with 1 ≤ ≤ and 1 ≤ ≤ . An overview of these combinatorial structures together with their properties can be found in [23]. Obviously, each (unique) sequence ∈ − can be uniquely associated with a plane partition, so that the plane partition is actually an alternative representation of the hypergraph that realizes . A plane partition can be naturally visualized as a stack arrangement of unitary cubes of height , lying on the point (, ) of the plane, thus obtaining a three-dimensional object (see Fig. 2). Each Ferrers diagram is the plane of the plane partition, that is the set of unit cubes on varying of and for a fixed value of height, , whose lower left point is in position (, ) (we enumerate rows and columns from bottom to top and from left to right, respectively). The height of the plane partition on the point (, ) is given by the value , .
Figure 2 depicts the plane partition related to the hypergraph in Example 1. We stress that corresponds to the Ferrers diagram of .
It is important to underline that can be constructed up to the knowledge of the hypergraph
, and that the construction of starting from the degree sequence is equivalent to the
reconstruction of the incidence matrix of the hypergraph . It turns out that the representation
of as a plane partition allows us to uniquely detect the edges of the hypergraph : the
edge (, , ) ∈ is identified by the elements of the Ferrers diagram in positions
( − − 1, − ) and ( − , − ). As an example, in Fig. 1 the edge (
Inspecting the Ferrers diagram of an integer partition one can immediately detect if it is the degree sequence of a graph. Indeed, a Ferrers diagram associated with an integer partition can always be decomposed into three (possibly empty) partitions = ( ) + ( ) + ( ), where ( ) is the largest square entirely contained in , called Durfee square, ( ) is the set of cells over ( ) and ( ) is the set of cells placed on the right of ( ) after removing the first cell of every row [22], see Fig. 3. It is known that is graphical if and only if ( ) ≤ ( )′ holds (see [17, 22]), where ( )′ is the conjugate partition of ( ), i.e., the partition obtained from ( ) by exchanging rows and columns, and ≤ is the dominance order [6]. We recall that provided two integer partitions = ( 1, . . . , ) and = ( 1, . . . , ), ≤ holds if and only if ∑︀=1 ≤ ∑︀=1 for any 1 ≤ ≤ . If ( ) = ( )′ holds, the partition is a maximal graphical partition (see Fig. 3).
R D D × L D D × L L
R R D D × D D × L L
R R R D D × D D × L
and its block graphs, for all 1 ≤ ≤ − 2 the integer sequence Proposition 2. Given ∈ is a maximal graphical partition.
Proof. Let us proceed by contradiction assuming that there exists an index such that is
not maximal. Since is graphical, ( ) < ( )′ holds. By definition of dominance order,
the smallest point (, ) where they difer is such that (, ) ∈ ( ) and ( − 1, ) ̸∈ ( )
(keeping the rows and the columns indexing bottom-up and left-right, respectively). This means
that the edge (, + , + ) ̸∈ . Furthermore, (, ′, + ) ∈ for each < ′ < + , by
the minimality of (, ), so there exists an index ′′ > + such that (, ′′, + ) ∈ . This
leads to a contradiction since, by definition of , the edges of form an ideal of . □
Again, Figure 1 clarifies the above proof and provides a representation of the sequences
as Ferrers diagrams. A visual inspection shows that
obtained from = (
submatrix * of which is the plane partition of the complete 3-hypergraph on vertices, for some 3 ≤ ≤ .
Proof. Let be the number of planes of , i.e. the maximum entry of the matrix. By construction, the submatrix composed by the last rows and first + 1 columns is the plane partition related to the complete 3-hypergraph on = + 2 vertices. □ It directly follows that the incidence matrix of always contains a submatrix * (called the core of ) which is the matrix of a complete 3-hypergraph on its first ≤ vertices. We underline that the plane partition representing is composed of − 2 planes, and that the -th plane represents all those hyperedges whose first element is the vertex . For each sequence ∈ , we get the following standard decomposition of the related plane partition
= * + + , with * the core, given by the set of rows placed over the submatrix * and given by the set of columns on the right side of the submatrix of the core adding the row immediately over. By abuse of notation, we define ′ = ⋃︀=−12 ( )′.
Property 2. For each sequence ∈ , = ′ holds.
This property directly follows from the maximality of block graphs in and the symmetry properties of their Ferrers diagrams. 4. The reconstruction problem in the class − In this section we introduce the sets of maximal and minimal degree sequences in − , and we provide a polynomial time algorithm for their reconstruction. Then, we move the spotlight to the whole class and we provide a heuristic to determine the 3-hypergraphs related to its elements. 4.1. The reconstruction of maximal and minimal instances We first define the algorithm GColRec (Greedy Column Reconstruction), that reconstructs a subset of degree sequences of − called maximal instances. The inputs of GColRec are an element = ( 1, . . . , ) of − and its supposed core dimension , while its output is either a 3-uniform hypergraph consistent with or failure.
Algorithm 1. GColRec( ,c) Since the dimension of the core is not known in advance, we consider − 2 parallel computations, one for each possible value of . The subset of the maximal instances of − is indicated by ℳ.
= 1, . . . , − 2. If ∈ ℳ, then the partition ( ) is the maximum, w.r.t. dominance order, among all integer partitions of in which each part is less or equal than − . Proof. Immediate from the definition of the reconstruction strategy GColRec, that maximizes the height of the bars of each block graph, from left to right. According to the length of the sequence and the dimension of its core, it is clear that each value in ( ) can not exceed − . □ We underline that the class ℳ properly includes the class of maximal instances defined in [2], where the core computation is not present.
Example 3. The degree sequence = (
A second greedy strategy called GRowRec can be defined from GColRec, performing the construction of each ( ) row-by-row, from 1 to − 2. We define the class of minimal instances, ℳ, as the set of the sequences in − that are correctly reconstructed by GRowRec. The notion of minimality follows from the greedy choices of the strategy, similarly to Proposition 4. Theorem 1. GColRec (respectively, GRowRec) performs in (4) time.
The proof is immediate. A simple check shows that the union of the subclasses ℳ and ℳ is
strictly included in − . As a matter of fact, the sequence = (
We stress that the failures of the algorithms GColRec and GRowRec are due to the insertion of extra edges that do not belong to the (unique) final solution. Furthermore, wrong insertions may determine a reconstruction failure some steps ahead in the computation, so that, in general, they cannot be immediately detected, requiring an unbounded backtrack process to fix the errors. In the next section we describe a heuristic that avoids wrong edge insertions, but sometimes produces only a partial reconstruction of a 3-hypergraph in − . 4.2. A heuristic for the class − − . We introduce the notion of complemenLet us consider the reconstruction of the class tarity: given a 3-hypergraph on vertices, we denote = (︀ −2 1)︀ the maximum admitted degree of each vertex, that corresponds to the common degree in the complete 3-hypergraph on , we define its complementary sequence = ( , . . . , ) − . vertices H. For a given ∈ It is clear that is the degree sequence of the complementary 3-hypergraph with vertices and containing all edges not in . We underline that keeps all properties of the , in particular the strong block-structure of the incidence matrix hypergraphs of the class (and the uniqueness if we restrict to − ). Similarly, we define the degree sequences of the complementary block graphs in as = ( − − 1) − for = 1, . . . , − 2, and the related complementary plane partition as = P − , with P the plane partition associated to H. From now on, we will omit the subscript that identifies the degree sequence when no ambiguities may arise. − and requires a parallel reconstruction The heuristic we propose starts from a sequence ∈ of both and its complementary at the same time, avoiding the insertion of extra edges during the process. All edges of H are considered and assigned either to or to , if no ambiguities occur, otherwise are kept unassigned. The hypergraphs and are modelled by two three-dimensional matrices that represent their plane partitions and , respectively. Both matrices are initialized to the null matrix, and their elements are updated to the value 1 according to the detected edges in and . The heuristic, indicated as HeuRec, is composed by the following three steps: Step 1 The pseudo-code of the first step of the reconstruction is provided in Algorithm 2, Preprocessing, that computes from the input sequence of length an admitted dimension of the core and the complementary sequence . Then, it assigns to all hyperedges of the core, i.e., all hyperedges of H on the vertices 1, . . . , . After their insertion, the sequence is updated by subtracting the common degree value = (− 2)(− 1) of H from the first elements of the 2 input sequence, obtaining the sequence 0. Since the dimension of the core is not known in advance, we perform − 2 parallel computations, one for each possible value of . Property 3. Let be the dimension of the core of the degree sequence . An edge (, , ) in whose minimum vertex index is greater than − 2 does not exist.
It directly follows from the definition of core of a plane partition. As a consequence, all edges whose minimum vertex is , with > − 2, are assigned to , and they form the complete 3-hypergraph defined on the last − ( − 2) vertices. After their insertion in , Preprocessing creates the sequence 0 by subtracting the value = (− )(− +1) from the last − ( − 2) 2 elements of .
Theorem 2. Preprocessing performs in (3) time.
Proof. The plane partition related to the hypergraph can be represented as a three-dimensional matrix whose dimensions are ( − 2) × ( − 1) × ( − 2) for a hypergraph on vertices and with core dimension . The same for . The insertion of the edges of the core requires to iterate through the whole matrix, procedure that runs in (3). □ The reconstruction of each plane of and proceeds in Step 2, starting from the updated sequences 0 = ( 10, . . . , 0) and 0 = ( 01, . . . , 0).
Algorithm 2. Preprocessing( )
Input: 1 compute ; 2 assumed the dimension of the core, compute = (− 2)(− 1) and = (− )(− +1) ; 2 2 3 insert all edges of the complete hypergraph on the first vertices in and compute 0 by updating ; 4 insert all edges of the complete hypergraph on the last − ( − 2) vertices in and compute 0 by updating ; Output: , , 0, 0 Step 2 Now the heuristic inserts in and the edges that definitely belong to one of them. The insertions are performed either by checking the cardinalities of the possible positions or the values of the (supposed) degree sequences starting from 0 and 0. The reconstruction process proceeds plane by plane from 1 up to − 2, resp. from 1 up to − 2. The edges’ insertion in a generic plane is sketched in Algorithm 3, Insert-, and hereafter detailed. An analogous algorithm, Insert-, is also defined. A further definition is required: we call -area the set of positions in that are delimited by the upper row of the core, the -th column and the (discrete) diagonal line of (these two last included). In other words, the -area is the part of where the elements of ( ) may lie. Symmetrically, we can define the -area of that includes the elements of ( ), see Fig. 4.
Insert-H: starting from the sequence − 1, the algorithm computes the maximal and the minimal partition of the -th element − 1 of − 1 included in the -area of . Let these partitions be and , respectively. The algorithm inserts in the -area of the elements common to and , i.e. the partition ∩ . Accordingly, it inserts in the -area their symmetric elements. It is worthwhile noticing that each element added to the -area with its symmetric in the -area form an edge whose first vertex is , and which is common to all 3-hypergraphs sharing the same degree sequence , if any. Example 4 clarifies this construction.
Insert-: acts analogously to compute from the sequence − 1.
Algorithm 3. Insert-H(, − 1)
Input: , − 1 1 compute and ; 2 insert in the -area of the elements in ∩ ; 3 fill the -area of symmetrically with respect to the -area;
Output:
Example 4. Let us consider the sequence = (
Theorem 3. Insert-H (resp., Insert-) performs in (2) time.
Proof. In Insert-H the computation of both and can be performed by simple arithmetic operations, resulting in a constant time complexity. The update of both ( ) and ( ) requires (2) time, since is modelled by a matrix of dimension (2). □ ore ore
pmax pmax ∩ pmin
pmin Lae -ra
Finally, the update of − 1 into is performed. We compute the sequence = (0, . . . , 0, , . . . , ) where each , with + 1 ≤ ≤ , counts the number of the edges involving the vertices and that are inside the or -area of and that are not yet added in , while counts the number of edges inserted in . In other words, the vector counts the edges of that either belong to or still maintain their placement ambiguity. Then, we define = − 1 − . In general, can be diferent from − 1. Such a discrepancy is useful to keep possible all ways of inserting the edges in the +1 plane. A symmetric computation leads to the update of − 1 to . The following property is immediate.
adds the edge (, , ) to the plane of , with < < , then it also belongs to all 3-hypergraphs whose degree sequence is .
Step 3 As a final step, the heuristic considers the set of ambiguous edges, i.e. the edges that have not yet been inserted in or in , and the updated sequences = − 2 and = − 2 obtained after the performance of Step 2. In this final step the heuristic benefits of the membership of , in particular of the ideal (and filter) characterization w.r.t. the poset . in If (, , ) ⪯ (′, ′, ′) in then, for the related edges 1 and 2, respectively, it holds that if 2 ∈ then 1 ∈ (symmetrically, if 1 ∈ then 2 ∈ , as stated in Property 1). The procedure described in Algorithm 4, Poset, is iteratively repeated on each edge ∈ until no further edge insertions in and are possible. The heuristic produces a successful reconstruction if all edges of are inserted in or . The matrix is the final output. Theorem 4. performs in (3) time.
Proof. Both the check of the maximality and minimality of an element in , and the related computation of and , require a scan of the whole set, performed in (3) time. The update of the sequences * and * , together with the possible insertion of , run in () time. Summing up, the whole Poset procedure requires (3) steps. □ Algorithm 4. Poset(,, , ,,)
We stress again that Poset terminates in a finite number of iterations, at most ||, leading to the (unique) solution or to a partial reconstruction where no wrong insertions are performed. Theorem 5. HeuRec performs in polynomial time with a total cost of (10).
Proof. It directly follows from the previous analysis. In particular, Step 1 is performed in (3),
see Theorem 2. In Step 2, Insert-H and Insert- run on each of the − 2 planes of the partition,
for a total cost of (3), see Theorem 3. Finally, Step 3 requires a running time of (9), since
Poset can be performed || times at most, with || = (3), see Theorem 4. Then, we have
that the total cost of the three steps is (9). Since the three steps are required to be performed
for times at most (one for each value of ), the total running time is (10). □
Example 5. The sequences 1 = (
We checked the performance of HeuRec on randomly generated sequences ∈ , varying
their length. We underline that the computation of sequences in instead of − allows
to guarantee the uniqueness property without limiting or afecting the heuristic performance.
Table 1 shows the success rate according to the diferent lengths of up to = 30. The statistics
was obtained as the mean of several runs of 100 block trials for each length.
≤ 9
100%
= 20
71.28%
has an exponential growth rate (w.r.t. to
It is known that the cardinality of the class
the length of its elements), see [2]. From the obtained data, we observe a high success
rate for small degree sequences, while the performance drastically deteriorate when
increases (second line of Table 1), as expected. From Example 5, the possibility of running on
the same input sequence the three algorithms, HeuRec, GColRec and GRowRec, can be
considered to improve the set of instances that are fast reconstructable. Unfortunately, not all
sequences in − can be reconstructed by the three algorithms: as an example, consider
= (
The authors acknowledge support by the INdAM-GNCS Project 2023 (cod.
strings, hypergraphs and permutations".