Characterization of the Vertices and Extreme Directions of the Negative Cycles Polyhedron and Hardness of Generating Vertices of 0/1-Polyhedra
| dc.creator | Boros, Endre | |
| dc.creator | Elbassioni, Khaled | |
| dc.creator | Gurvich, Vladimir | |
| dc.creator | Tiwary, Hans Raj | |
| dc.date | 2008-01-24 | |
| dc.date | 2008-04-28 | |
| dc.date.accessioned | 2026-07-07T09:35:13Z | |
| dc.date.available | 2026-07-07T09:35:13Z | |
| dc.description | 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übbecke (1998)]. | |
| dc.description | Title typo fixed | |
| dc.identifier | https://arxiv.org/abs/0801.3790 | |
| dc.identifier | http://arxiv.org/abs/0801.3790 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/159763 | |
| dc.subject | Computational Complexity | |
| dc.subject | Discrete Mathematics | |
| dc.subject | F.2.2 | |
| dc.title | Characterization of the Vertices and Extreme Directions of the Negative Cycles Polyhedron and Hardness of Generating Vertices of 0/1-Polyhedra | |
| dc.type | text |