Leonid Khachiyan
ABSTRACT
We show that generating all negative cycles of a weighted graph is a hard enumeration problem, in both the directed and undirected cases. More precisely, given a family of negative (directed) cycles, it is an NP-complete problem to decide whether this family can be extended or there are no other negative (directed) cycles in the graph, implying that (directed) negative cycles cannot be generated in polynomial output time, unless P=NP. As a corollary, we solve in the negative two well-known generating problems from linear programming: (i) Given an infeasible system of linear inequalities, generating all minimal infeasible subsystems is hard. Yet, for generating maximal feasible subsystems the complexity remains open. (ii) Given a feasible system of linear inequalities, generating all vertices of the corresponding polyhedron is hard. Yet, in the case of bounded polyhedra the complexity remains open
Index Terms
- Generating all vertices of a polyhedron is hard
Recommendations
Lifting facets of the cut polytope
The cut polytope P"c(G) of a graph G is the convex hull of the incidence vectors of the edge sets of all cuts of G. We give a sufficient condition for an inequality defining a facet of P"c(G) to define a facet of the cut polytope of a graph containing G ...
The Binested Inequalities for the Symmetric Traveling Salesman Polytope
In this paper we define a family of valid inequalities for the Symmetric Travelling Salesman Polytope which are defined on two nested sets of vertices of the graph. These inequalities generalize the comb inequalities of Chvítal, Grötschel and Padberg, ...
Generating All Vertices of a Polyhedron Is Hard
We show that generating all negative cycles of a weighted graph is a hard enumeration problem, in both the directed and undirected cases. More precisely, given a family of negative (directed) cycles, it is an NP-complete problem to decide whether this ...
Comments