2008/01/24 by Endre Boros, Khaled Elbassioni, Boros, Endre +5
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Markov Chains and Monte Carlo Methods #cs.CC #cs.DM
paper · pdf · doi:10.48550/arxiv.0801.3790
Title typo fixed
arxiv created 2008/04/28 · arxiv updated 2009/12/01
Given a graph G=(V,E) and a weight function on the edges w:E↦\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 \citeBL98 [Bussieck and Lübbecke (1998)].