Polyhedra of the Equivalent Subgraph Problem and Some Edge Connectivity Problems
Sunil Chopra · SIAM Journal on Discrete Mathematics · 1992
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. Grötschel 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.