2026-07-23T20:07:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18839 2024-03-06T11:02:42Z ddc:004 open_access

Algorithms for 2-Connected Network Design and Flexible Steiner Trees with a Constant Number of Terminals Bansal, Ishan Cheriyan, Joe Grout, Logan Ibrahimpur, Sharat Approximation algorithms Capacitated network design Network design Parametrized algorithms Steiner cycle problem Steiner 2-edge connected subgraphs Steiner 2-node connected subgraphs The k-Steiner-2NCS problem is as follows: Given a constant (positive integer) k, and an undirected connected graph G = (V,E), non-negative costs c on the edges, 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 min-cost two-node connected subgraph that contains the terminals. The k-Steiner-2ECS problem has the same inputs; the algorithmic goal is to find a min-cost two-edge connected subgraph that contains the terminals. We present a randomized polynomial-time algorithm for the unweighted k-Steiner-2NCS problem, and a randomized FPTAS for the weighted k-Steiner-2NCS problem. We obtain similar results for a capacitated generalization of the k-Steiner-2ECS problem. Our methods build on results by Björklund, Husfeldt, and Taslaman (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 min-cost simple cycle C that contains the terminals (C may contain any number of Steiner nodes). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ishan Bansal and Joe Cheriyan and Logan Grout and Sharat Ibrahimpur 2023 Is Part Of LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2023.14 urn:nbn:de:0030-drops-188396 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.14 eng https://creativecommons.org/licenses/by/4.0/legalcode