Search

The \emph{Steiner tree} problem is one of the fundamental and classical problems in combinatorial optimization. In this paper, we study this problem in the $\mathcal{CONGESTED}$ $\mathcal{CLIQUE}$ model of distributed computing and present two deterministic distributed approximation algorithms for the same. The first algorithm computes a Steiner tree in $\tilde{O}(n^{1/3})$ rounds and $\tilde{O}(n^{7/3})$ messages for a given connected undirected weighted graph of $n$ nodes. Note here that $\tilde{O}(\cdot)$ notation hides polylogarithmic factors in $n$. The second one computes a Steiner tree in $O(S + \log\log n)$ rounds and $O(S (n - t)^2 + n^2)$ messages, where $S$ and $t$ are the \emph{shortest path diameter} and the number of \emph{terminal} nodes respectively in the given input graph. Both the algorithms admit an approximation factor of $2(1 - 1/\ell)$, where $\ell$ is the number of terminal leaf nodes in the optimal Steiner tree. For graphs with $S = \omega(n^{1/3} \log n)$, the first algorithm exhibits better performance than the second one in terms of the round complexity. On the other hand, for graphs with $S = \tilde{o}(n^{1/3})$, the second algorithm outperforms the first one in terms of the round complexity. In fact when $S = O(\log\log n)$ then the second algorithm admits a round complexity of $O(\log\log n)$ and message complexity of $\tilde{O}(n^2)$. To the best of our knowledge, this is the first work to study the Steiner tree problem in the $\mathcal{CONGESTED}$ $\mathcal{CLIQUE}$ model., Comment: 22 pages, 6 figures

The Prize-Collecting Steiner Tree (PCST) problem is a generalization of the Steiner Tree problem that has applications in network design, content distribution networks, and many more. There are a few centralized approximation algorithms \cite{DB_MG_DS_DW_1993, GW_1995, DJ_MM_SP_2000, AA_MB_MH_2011} for solving the PCST problem. However no distributed algorithm is known that solves PCST with a guaranteed approximation factor. In this work we present an asynchronous distributed $(2 - \frac{1}{n - 1})$-approximation algorithm that constructs a PCST for a given connected undirected graph with non-negative edge weights and a non-negative prize value for each node. Our algorithm is an adaptation of the centralized algorithm proposed by Goemans and Williamson \cite{GW_1995} to the distributed setting, and is based on the primal-dual method. The message complexity of the algorithm with input graph having node set $V$ and edge set $E$ is $O(|V||E|)$. Initially each node knows only its own prize value and the weight of each incident edge. The algorithm is spontaneously initiated at a special node called the \emph{root node} and when it terminates each node knows whether it is in the PCST or not. To the best of our knowledge this is the first distributed constant approximation algorithm for PCST., Comment: Distributed algorithm, 32 pages, 8 figures