Integer points in the degree-sequence polytope
share
An integer vector b ∈ℤ^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 𝒵^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, the degree-sequence polytope 𝒵^d contains integer points that are not degree sequences. Furthermore, we prove that the linear optimization problem over 𝒵^d is NP-hard. This complements a recent result of Deza et al. (2018) who provide an algorithm that is polynomial in d and the number of hyperedges.
READ FULL TEXT
