Algorithms & LPs for k-edge connected spanning subgraphs

David Pritchard

Dec 2, 2009

We study the "k-edge-connected spanning subgraph problem" in network design, motivated e.g. by guaranteeing the existence of flows of value k, or reliability against k-1 edge failures. Gabow, Goemans, Tardos & Williamson gave an elegant and simple LP-based algorithm for this problem with approximation ratio 1+2/k if all edges have the same cost. We show that the case of arbitrary costs behaves differently: the best possible approximation ratio is at least a fixed 1+epsilon, independent of k. We then discuss the multisubgraph version of the problem with arbitrary costs: we conjecture a 1+constant/k approximation based on LPs. The natural LP is (up to scaling) also known as the Held-Karp TSP relaxation, and we give a new intricate extreme point family with exponentially small values and maximum degree |V|/2.