2022/06/23 by Bansal, Ishan, Cheriyan, Joe, Grout, Logan +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2206.11807
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).