English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

Characterization of the Vertices and Extreme Directions of the Negative Cycles Polyhedron and Hardness of Generating Vertices of 0/1-Polyhedra

MPS-Authors
/persons/resource/persons44374

Elbassioni,  Khaled
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45623

Tiwary,  Hans Raj
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

0801.3790.pdf
(Preprint), 215KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Boros, E., Elbassioni, K., Gurvich, V., & Tiwary, H. R. (2008). Characterization of the Vertices and Extreme Directions of the Negative Cycles Polyhedron and Hardness of Generating Vertices of 0/1-Polyhedra. Retrieved from http://arxiv.org/abs/0801.3790.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0028-5819-4
Abstract
Given a graph $G=(V,E)$ and a weight function on the edges $w:E\mapsto\RR$, 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)$. As a corollary, 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. (2006) for non 0/1-polyhedra, and comes in contrast with the polynomiality of vertex enumeration for 0/1-polytopes \cite{BL98} [Bussieck and L\"ubbecke (1998)].