Computing the vertices of tropical polyhedra using directed hypergraphs

Abstract

We establish a characterization of the vertices of a tropical polyhedron defined as the intersection of finitely many half-spaces. We show that a point is a vertex if, and only if, a directed hypergraph, constructed from the subdifferentials of the active constraints at this point, admits a unique strongly connected component that is maximal with respect to the reachability relation (all the other strongly connected components have access to it). This property can be checked in almost linear-time. This allows us to develop a tropical analogue of the classical double description method, which computes a minimal internal representation (in terms of vertices) of a polyhedron defined externally (by half-spaces or hyperplanes). We provide theoretical worst case complexity bounds and report extensive experimental tests performed using the library TPLib, showing that this method outperforms the other existing approaches.

29 pages (A4), 10 figures, 1 table; v2: Improved algorithm in section 5 (using directed hypergraphs), detailed appendix; v3: major revision of the article (adding tropical hyperplanes, alternative method by arrangements, etc); v4: minor revision

References in corpus (8)

• Duality and separation theorems in idempotent semimodules
• The Minkowski Theorem for Max-plus Convex Sets
• Minimal half-spaces and external representation of tropical polyhedra
• The number of extreme points of tropical polyhedra
• Tropical polar cones, hypergraph transversals, and mean payoff games
• The tropical double description method
• On the complexity of strongly connected components in directed hypergraphs
• An algorithm to describe the solution set of any tropical linear system $A\odot x=B\odot x$

Cited by in corpus (22)

• Tropicalizing the simplex algorithm
• The number of extreme points of tropical polyhedra
• Weighted digraphs and tropical cones
• Conditional Independence in Max-linear Bayesian Networks
• Tropical polar cones, hypergraph transversals, and mean payoff games
• On the complexity of strongly connected components in directed hypergraphs
• Tropical Fourier-Motzkin elimination, with an application to real-time verification
• On tropical Kleene star matrices and alcoved polytopes
• Minimal external representations of tropical polyhedra
• X-simple image eigencones of tropical matrices
• Linear programs and convex hulls over fields of Puiseux fractions
• On $2\times 2$ Tropical Commuting Matrices
• On the dimension of max-min convex sets
• Extremality criteria for the supereigenvector space in max-plus algebra
• Polytropes and Tropical Eigenspaces: Cones of Linearity
• Tropical analogues of a Dempe-Franke bilevel optimization problem
• Using matrix sparsification to solve tropical linear vector equations
• An algorithm for finding the scaled basis of the supereigenvector space in max-plus algebra
• Extreme rays of the ${\ell }^{\infty }$-nearest ultrametric tropical polytope
• On max-plus two-sided linear systems whose solution sets are min-plus linear
• Extremals of the supereigenvector cone in max algebra: a combinatorial description
• Matrices commuting with a given normal tropical matrix