Algorithms for some Steiner tree problems on Graphs
No Thumbnail Available
Date
2020
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
In this research work we study the Steiner tree (ST) problem in the distributed setting. Given a connected undirected graph with non-negative edge weights and a subset of terminal nodes, the goal of the ST problem is to find a minimum-cost tree spanning the terminals. The first contribution is a deterministic distributed algorithm for the ST problem (DST algorithm) in the CONGEST model which guarantees an approximation factor of 2(1 − 1/ℓ), where ℓ is the number of leaf nodes in the optimal ST. It has a round complexity of O(S + √nlog*(n)) and a message complexity of O(Sm + n3/2) for a graph of n nodes and m edges, where S is the shortest path diameter of the graph. The DST algorithm improves the round complexity of the best distributed ST algorithm known so far, which is Õ(S + √(min{St,n}), where t is the number of terminal nodes. We modify the DST algorithm and show that a 2(1 – 1/ℓ)-approximate ST can be deterministically computed using Õ(S+ √n) rounds and Õ(mS) messages in the CONGEST model.
The CONGESTED CLIQUE model (CCM) is a special case of the CONGEST model in distributed computing. In this model we propose two deterministic distributed algorithms for the ST problem: STCCM-A and STCCM-B. The first one computes an ST using Õ(n1/3) rounds and Õ(n7/3) messages. The second one computes an ST using O(S + loglog(n)) rounds and O(Sm+n2) messages. Both the algorithms achieve an approximation ratio of 2(1 − 1/ℓ). To the best of our knowledge, this is the first work to study the ST problem in the CCM till date.
We also study a generalized version of the ST problem called prize-collecting Steiner tree (PCST). Problems such as MST, ST, Steiner forest, etc. which are related to the PCST, have been widely studied in the distributed setting. However, PCST has seen very little progress in the distributed setting (the only attempt seems to be a manuscript due to Rossetti, an M.Sc. thesis, University of Iceland, Reykjavik, 2015). We present two deterministic distributed algorithms for the PCST problem in the CONGEST model: D-PCST and modified D-PCST. Both the algorithms are based on the primal-dual technique, preserve the dual constraints in a distributed manner, and achieve an approximation factor of (2 – 1/(n-1)). The D-PCST algorithm computes a PCST using O(n2) rounds and O(mn) messages. The modified one computes a PCST using O(Dn) rounds and O(mn) messages, where D is the unweighted diameter of the graph. Both the algorithms require O(Δlog(n)) bits of memory in each node, where Δ is the maximum degree of a node in the graph.
Description
Supervisor: Sushanta Kamakar
Keywords
COMPUTER SCIENCE AND ENGINEERING