EXTENDED FORMULATIONS FOR THE A-CUT PROBLEM

Let G = (V, E) be an undirected graph and A subset of or equal to V. W e consider the problem of finding a minimum cost set of edges whose de letion separates every pair of nodes in A. We consider two extended fo rmulations using both node and edge variables. An edge variable formul ation has previously been considered for this problem (Chopra and Rao (1991), Cunningham (1991)). We show that the LP-relaxations of the ext ended formulations are stronger than the LP-relaxation of the edge var iable formulation (even with an extra class of valid inequalities adde d). This is interesting because, while the LP-relaxations of the exten ded formulations can be solved in polynomial time, the LP-relaxation o f the edge variable formulation cannot. We also give a class of valid inequalities for one of the extended formulations. Computational resul ts using the extended formulations are performed.