## 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 language | British English |
---|---|

Pages (from-to) | 63-76 |

Number of pages | 14 |

Journal | Annals of Operations Research |

Volume | 188 |

Issue number | 1 |

DOIs | |

State | Published - 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