Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View

DOI10.4230/LIPICS.IPEC.2020.16MaRDI QIDQ6068262zbMATH OpenOpenAlexFDO

Authors Radek Hušek, Dušan Knop, Tomáš Masařík

Publication date 13 November 2023

Full work available at URL https://arxiv.org/abs/2002.03583

zbMATH Keywords

approximationminimum spanning treestar contractionsSteiner tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Algorithms in computer science (68Wxx)

Abstract: In the Steiner Tree problem we are given an edge weighted undirected graph $G=(V,E)$ and a set of terminals $RsubseteqV$. The task is to find a connected subgraph of $G$ containing $R$ and minimizing the sum of weights of its edges. We observe that many approximation algorithms for Steiner Tree follow a similar scheme (meta-algorithm) and perform (exhaustively) a similar routine which we call star contraction. Here, by a star contraction, we mean finding a star-like subgraph in the input graph minimizing the ratio of its weight to the number of contained terminals minus one. It is not hard to see that the well-known MST-approximation seeks the best star to contract among those containing two terminals only. We perform an empirical study of star contractions with the relaxed condition on the number of terminals in each star contraction. Our experiments suggest the following: -- if the algorithm performs star contractions exhaustively, the quality of the solution is usually slightly better than Zelikovsky's 11/6-approximation algorithm, -- on average the quality of the solution returned by the MST-approximation algorithm improves with every star contraction, -- the same holds for iterated MST (MST+), which outperforms MST in every measurement while keeping very fast running time (on average $sim3imes$ slower than MST), -- on average the quality of the solution obtained by exhaustively performing star contraction is about 16% better than the initial MST-approximation, and -- we propose a more precise way to find the so-called improved stars which yield a slightly better solution within a comparable running time (on average $sim3imes$ slower). Furthermore, we propose two improvements of Zelikovsky's 11/6-approximation algorithm and we empirically confirm that the quality of the solution returned by any of these is better than the one returned by the former algorithm.

Cites work

• A fast algorithm for Steiner trees
• A faster approximation algorithm for the Steiner problem in graphs
• A note on two problems in connexion with graphs
• A practical greedy approximation for the directed Steiner tree problem
• An 11/6-approximation algorithm for the network Steiner problem
• Contraction-based Steiner tree approximations in practice
• Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm
• Dynamic programming for minimum Steiner trees
• scientific article; zbMATH DE number 1151379 (Why is no real title available?)
• scientific article; zbMATH DE number 1926656 (Why is no real title available?)
• scientific article; zbMATH DE number 1424551 (Why is no real title available?)
• Maintaining bridge-connected and biconnected components on-line
• Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
• Preprocessing Steiner problems from VLSI layout
• Reducibility among combinatorial problems
• SCIP-Jack -- a solver for STP and variants with parallelization extensions
• Solving Steiner tree problems in graphs to optimality
• Steiner tree approximation via iterative randomized rounding
• Strong Steiner tree approximations in practice
• The PACE 2018 parameterized algorithms and computational experiments challenge: the third iteration
• The steiner problem in graphs
• The Steiner tree problem
• Thek-Steiner Ratio in Graphs

Cited in

(1)

• Parameterized approximation schemes for Steiner trees with small number of Steiner vertices

This page was built for publication: Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6068262)