The negative cycles polyhedron and hardness of checking some polyhedral properties

Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Hans Raj Tiwary

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

Given a graph G = (V,E) and a weight function on the edges w:E→ℝ, we consider the polyhedron P(G,w) of negative-weight flows on G, and get a complete characterization of the vertices and extreme directions of P(G,w). Based on this characterization, and using a construction developed in Khachiyan et al. (Discrete Comput. Geom. 39(1-3):174-190, 2008), we show that, unless P=NP, there is no output polynomial-time algorithm to generate all the vertices of a 0/1-polyhedron. This strengthens the NP-hardness result of Khachiyan et al. (Discrete Comput. Geom. 39(1-3):174-190, 2008) for non 0/1-polyhedra, and comes in contrast with the polynomiality of vertex enumeration for 0/1-polytopes (Bussiech and Lübbecke in Comput. Geom., Theory Appl. 11(2):103-109, 1998). As further applications, we show that it is NP-hard to check if a given integral polyhedron is 0/1, or if a given polyhedron is half-integral. Finally, we also show that it is NP-hard to approximate the maximum support of a vertex of a polyhedron in ℝn within a factor of 12/n.

Original languageBritish English
Pages (from-to)63-76
Number of pages14
JournalAnnals of Operations Research
Volume188
Issue number1
DOIs
StatePublished - Aug 2011

Keywords

  • 0/1-polyhedron
  • Directed graph
  • Enumeration problem
  • Extreme direction
  • Flow polytope
  • Half-integral polyhedra
  • Hardness of approximation
  • Maximum support
  • Negative cycles
  • Vertex

Fingerprint

Dive into the research topics of 'The negative cycles polyhedron and hardness of checking some polyhedral properties'. Together they form a unique fingerprint.

Cite this