The minimum degree Group Steiner problem

The DB-GST problem is given an undirected graph G(V, E), and a collection of groups S = {S-i}(i=1)(q), S-i subset of V, find a tree that contains at least one vertex from every group S-i, so that the maximum degree is minimal. This problem was motivated by On-Line algorithms Hajiaghayi (2016), and has applications in VLSI design and fast Broadcasting. In the WDB-GST problem, every vertex v has individual degree bound d(v), and every e is an element of E has a cost c(e) > 0. The goal is, to find a tree that contains at least one terminal from every group, so that for every v, deg(T) (v) <= d(v), and among such trees, find the one with minimum cost. We give the first approximation for this problem, an (O(log(2) n), O(log(2) n)) bicriteria approximation ratio the WDB-GST problem on trees inputs. This implies an O(log(2) n) approximation for DB-GST on tree inputs. The previously best known ratio for the WDB-GST problem on trees was a bicriterion (O(log(2) n), O(log(3) n)) (the approximation for the degrees is O(log(3) n)) ratio which is folklore. Getting O(log(2) n) approximation requires careful case analysis and was not known. Our result for WDB-GST generalizes the classic result of Garg et al. (2016) that approximated the cost within O(log(2) n), but did not approximate the degree. Our main result is an O(log(3) n) approximation for BD-GST on Bounded Treewidth graphs. The DB-Steiner k-tree problem is given an undirected graph G(V, E), a collection of terminals S subset of V, and a number k, find a tree T (V', E') that contains at least k terminals, of minimum maximum degree. We prove that if the DB-GST problem admits a rho ratio approximation, then the DB-Steiner k-tree problem, admits an O(log(2) k . rho) expected approximation. We also show that if there are k groups, there exists an algorithm that is able to coverk/4 of the groups with minimum maximal degree, then there is a deterministic O(log n . rho) approximation for DB-Steiner k-tree problem. Using the work of Guo et al. (2020) we derive an O(log(3) n) approximation for DB-Steiner k-tree problem on general graphs, that runs in quasi-polynomial time. (C) 2021 Elsevier B.V. All rights reserved.