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 pi is 3-graphic has recently been proved to be NP-complete, after years of studies. Thus, it acquires primary relevance to detect classes of degree sequences whose graphicality can be tested in polynomial time in order to restrict the NP-hard core of the problem and design algorithms that can also be useful in different research areas. Several necessary and few sufficient conditions for pi 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 providing a combinatorial characterization of span-two sequences, i.e., sequences of the form pi = (d, ..., d, d - 1, ..., d - 1, d - 2, ..., d - 2), d >= 2, which are degree sequences of some 3-uniform hypergraphs. Then, we define a polynomial time algorithm to reconstruct one of the related 3-uniform hypergraphs. Our results are likely to be easily generalized to k >= 4 and to other families of degree sequences having simple characterization, such as gap-free sequences.
On the Reconstruction of 3-Uniform Hypergraphs from Degree Sequences of Span-Two / Giulia Palma; Andrea Frosini; Simone Rinaldi. - In: JOURNAL OF MATHEMATICAL IMAGING AND VISION. - ISSN 0924-9907. - ELETTRONICO. - 64:(2022), pp. 693-704. [10.1007/s10851-022-01074-2]
On the Reconstruction of 3-Uniform Hypergraphs from Degree Sequences of Span-Two
Andrea Frosini
;
2022
Abstract
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 pi is 3-graphic has recently been proved to be NP-complete, after years of studies. Thus, it acquires primary relevance to detect classes of degree sequences whose graphicality can be tested in polynomial time in order to restrict the NP-hard core of the problem and design algorithms that can also be useful in different research areas. Several necessary and few sufficient conditions for pi 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 providing a combinatorial characterization of span-two sequences, i.e., sequences of the form pi = (d, ..., d, d - 1, ..., d - 1, d - 2, ..., d - 2), d >= 2, which are degree sequences of some 3-uniform hypergraphs. Then, we define a polynomial time algorithm to reconstruct one of the related 3-uniform hypergraphs. Our results are likely to be easily generalized to k >= 4 and to other families of degree sequences having simple characterization, such as gap-free sequences.File | Dimensione | Formato | |
---|---|---|---|
span two.pdf
Accesso chiuso
Tipologia:
Pdf editoriale (Version of record)
Licenza:
Tutti i diritti riservati
Dimensione
1 MB
Formato
Adobe PDF
|
1 MB | Adobe PDF | Richiedi una copia |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.