Hypergraphic degree sequences are hard

MaRDI QIDQ5207882zbMATH OpenFDO

Authors Antoine Deza, Asaf Levin, Shmuel Onn, S. M. Meesum

Publication date 13 January 2020

Full work available at URL https://arxiv.org/abs/1901.02272, http://bulletin.eatcs.org/index.php/beatcs/article/view/573/572

Mathematics Subject Classification ID

Hypergraphs (05C65) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We show that deciding if a given vector is the degree sequence of a 3-hypergraph is NP-complete.

Recommendations

• Some NP-complete problems for hypergraph degree sequences
• On the Degree Sequence of 3-Uniform Hypergraph: A New Sufficient Condition
• An efficiently recognisable subset of hypergraphic sequences
• New sufficient conditions on the degree sequences of uniform hypergraphs
• On graphic and 3-hypergraphic sequences

Cited in

(13)

• Some NP-complete problems for hypergraph degree sequences
• Not all simple looking degree sequence problems are easy
• An efficiently recognisable subset of hypergraphic sequences
• Sampling hypergraphs with given degrees
• On null 3-hypergraphs
• Properties of unique degree sequences of 3-uniform hypergraphs
• Optimization over degree sequences
• On 3-hypergraphs with equal degree sequences.
• Integer points in the degree-sequence polytope
• Dense, irregular, yet always-graphic 3-uniform hypergraph degree sequences
• Does subset sum admit short proofs?
• On graphic and 3-hypergraphic sequences
• Multigraph realizations of degree sequences: Maximization is easy, minimization is hard

This page was built for publication: Hypergraphic degree sequences are hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5207882)