Counting vertices of integral polytopes defined by facets

2021/05/04 by Guo, Heng, Jerrum, Mark
#68Q17 (Primary) 52B05 #68W25 (Secondary) #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2105.01469

Abstract

We present a number of complexity results concerning the problem of counting vertices of an integral polytope defined by a system of linear inequalities. The focus is on polytopes with small integer vertices, particularly 0/1 polytopes and half-integral polytopes.

Related

• Polytopes with few vertices and few facets
• A bound for the number of vertices of a polytope with applications
• The lower bound for the number of facets of a k-neighborly d-polytope with d+3 vertices
• Lectures on 0/1-polytopes
• Forbidden vertices