2020/04/29 by Karpinski, Marek, Lewandowski, Mateusz, Meesum, Syed Mohammad +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2004.14102
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 \sc 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 \sc Steiner Forest, which asks for a minimum-size forest in G in which the nodes in each terminal set T1,…,Tk are connected, and every terminal in Ti has at least δ|Tj| neighbours in Tj, and at least δ|S| nodes in S = V(G)∖ (T1∪…∪ 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.