On the linear relaxation of the 2-node connected subgraph polytope

In this paper, we study the linear relaxation P(G) of the 2-node connected subgraph polytope of a graph G. We introduce an ordering on the fractional extreme points of P(C) and we give a characterization of the minimal extrem e points with respect to that ordering. This yields a polynomial method to separate a minimal extreme point of P(G) from the 2-node connected subgraph polytope. It also provides a new class of facet defining inequalities for this polytope. (C) 1999 Elsevier Science B.V. All rights reserved.