Answers are grounded in this paper and cite their sources.
An integer vector b ∈ Z d is a degree sequence if there exists a hypergraph with vertices { 1 , … , d } such that each b i is the number of hyperedges containing i . The degree-sequence polytope Z d is the convex hull of all degree sequences. We show that all but a 2 − Ω ( d ) fraction of integer vectors in the degree sequence polytope are degree sequences. Furthermore, the corresponding hypergraph of these points can be computed in time 2 O ( d ) via linear programming techniques. This is substantially faster than the 2 O ( d 2 ) running time of the current-best algorithm for the degree-sequence problem. We also show that for d ⩾ 98 , Z d contains integer points that are not degree sequences. Furthermore, we prove that both the degree sequence problem itself and the linear optimization problem over Z d are NP -hard. The latter complements a recent result of Deza et al. (2018) who provide an algorithm that is polynomial in d and the number of hyperedges.
No takes yet. Share an insight, caveat, or question.
Bach et al. (2024) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: