The 2-Connected Steiner Subgraph Problem

Given a 2-connected graph with edge weights and a subset of distinguished vertices, the 2-Connected Steiner Subgraph Problem is to find a minimum weight 2-connected subgraph that spans all of the distinguished vertices. Many survivable network design problems having applications in communications networks, water- and electric-supply networks, transportation networks, and networks arising in the routing of AGV and VLSI designs can be modeled as 2-Connected Steiner Subgraph Problem. The 2-Connected Steiner Subgraph Problem is NP-hard. The well-known Traveling Salesman Problem is a closely related problem in which all the vertices of the graph are distinguished, and the desired subgraphs are restricted to be cycles. This dissertation presents new polyhedral as well as algorithmic results for the 2-Connected Steiner Subgraph Problem posed on special classes of graphs. The 2-connected-spanning-subgraph polyhedra for series-parallel and $W\sb4$-free graphs are given, and the 2-connected-Steiner-subgraph polytope is described for series-parallel graphs. The dominant of the 2-connected-Steiner-subgraph polytope for $W\sb4$-free graphs has also been described. As related results, polyhedra for the Traveling-Salesman Problem on series-parallel and $W\sb4$-free graphs have been found. Moreover, the 2-connected-spanning-subgraph polytope and the Traveling-Salesman polytope for series-parallel graphs are shown to require only a polynomial number of constraints and variables. Necessary and sufficient conditions have also been provided under which a polytope is related to its dominant and submissive in a simple way. Finally, linear-time algorithms are presented for solving the 2-Connected Steiner Subgraph Problem on $W\sb4$-free and Halin graphs