Options
Dense Steiner problems: approximation algorithms and inapproximability
Publikationstyp
Preprint
Date Issued
2020
Sprache
English
Institut
TORE-URI
The Steiner Tree problem is a classical problem in combinatorial optimization: the goal is to connect a set T of terminals in a graph G by a tree of minimum size. Karpinski and Zelikovsky (1996) studied the δ-dense version of Steiner Tree, where each terminal has at least δ |V(G)∖ T| neighbours outside T, for a fixed δ > 0. They gave a PTAS for this problem. We study a generalization of pairwise δ-dense Steiner Forest, which asks for a minimum-size forest in G in which the nodes in each terminal set T₁,…,Tk are connected, and every terminal in Tᵢ has at least δ |Tⱼ| neighbours in Tⱼ, and at least δ|S| nodes in S = V(G)∖ (T₁∪…∪ Tk), for each i, j in {1,…, k} with i≠ j. Our first result is a polynomial-time approximation scheme for all δ > 1/2. Then, we show a ((13/12)+ε)-approximation algorithm for δ = 1/2 and any ε > 0. We also consider the δ-dense Group Steiner Tree problem as defined by Hauptmann and show that the problem is APX-hard.
DDC Class
510: Mathematik