Algorithms for 2-connected network design and flexible Steiner trees with a constant number of terminals
share
The k-Steiner-2NCS problem is as follows: Given a constant k, and an undirected connected graph G = (V,E), non-negative costs c on E, and a partition (T, V-T) of V into a set of terminals, T, and a set of non-terminals (or, Steiner nodes), where |T|=k, find a minimum-cost two-node connected subgraph that contains the terminals. We present a randomized polynomial-time algorithm for the unweighted problem, and a randomized PTAS for the weighted problem. We obtain similar results for the k-Steiner-2ECS problem, where the input is the same, and the algorithmic goal is to find a minimum-cost two-edge connected subgraph that contains the terminals. Our methods build on results by Björklund, Husfeldt, and Taslaman (ACM-SIAM SODA 2012) that give a randomized polynomial-time algorithm for the unweighted k-Steiner-cycle problem; this problem has the same inputs as the unweighted k-Steiner-2NCS problem, and the algorithmic goal is to find a minimum-size simple cycle C that contains the terminals (C may contain any number of Steiner nodes).
READ FULL TEXT