POLYHEDRA OF THE EQUIVALENT SUBGRAPH PROBLEM AND SOME EDGE CONNECTIVITY PROBLEMS

In this paper the problem of finding a minimum weight equivalent subgraph of a directed graph is considered. The associated equivalent subgraph polyhedron P(G) is studied. Several families of facet-defining inequalities are described for this polyhedron. A related problem of designing networks that satisfy certain survivability conditions, as introduced in [M. Grotschel and C. L. Monma, SIAM Journal on Discrete Mathematics, 3 (1990), pp. 502-523] is also studied. The low connectivity case is formulated on directed graphs, and the directed formulation is shown to give a better LP-relaxation than the undirected one. It is shown how facet-defining inequalities of P(G) give facet-defining inequalities in this case. Computational results are presented for some randomly generated problems.