Hypergraphic Degree Sequences are Hard

Authors :: Deza, Antoine
Levin, Asaf
Meesum, Syed M.
Onn, Shmuel
Source :: Bulletin of the European Association for Theoretical Computer Science, 127:63-64, 2019
Publication Year :: 2019
Abstract: We show that deciding if a given vector is the degree sequence of a 3-hypergraph is NP-complete.

Subjects :: Mathematics - Combinatorics
Computer Science - Computational Complexity
Computer Science - Discrete Mathematics
05A, 15A, 51M, 52A, 52B, 52C, 62H, 68Q, 68R, 68U, 68W, 90B, 90C

Database :: arXiv
Journal :: Bulletin of the European Association for Theoretical Computer Science, 127:63-64, 2019
Publication Type :: Report
Accession number :: edsarx.1901.02272
Document Type :: Working Paper

Tools