Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userImproved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees
106
0
0.0
(
0
)
Added by
Dennis Olivetti
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Recently, Balliu, Brandt, and Olivetti [FOCS 20] showed the first $omega(log^* n)$ lower bound for the maximal independent set (MIS) problem in trees. In this work we prove lower bounds for a much more relaxed family of distributed symmetry breaking problems. As a by-product, we obtain improved lower bounds for the distributed MIS problem in trees. For a parameter $k$ and an orientation of the edges of a graph $G$, we say that a subset $S$ of the nodes of $G$ is a $k$-outdegree dominating set if $S$ is a dominating set of $G$ and if in the induced subgraph $G[S]$, every node in $S$ has outdegree at most $k$. Note that for $k=0$, this definition coincides with the definition of an MIS. For a given $k$, we consider the problem of computing a $k$-outdegree dominating set. We show that, even in regular trees of degree at most $Delta$, in the standard LOCAL model, there exists a constant $epsilon>0$ such that for $kleq Delta^epsilon$, for the problem of computing a $k$-outdegree dominating set, any randomized algorithm requires at least $Omega(min{logDelta,sqrt{loglog n}})$ rounds and any deterministic algorithm requires at least $Omega(min{logDelta,sqrt{log n}})$ rounds. The proof of our lower bounds is based on the recently highly successful round elimination technique. We provide a novel way to do simplifications for round elimination, which we expect to be of independent interest. Our new proof is considerably simpler than the lower bound proof in [FOCS 20]. In particular, our round elimination proof uses a family of problems that can be described by only a constant number of labels. The existence of such a proof for the MIS problem was believed impossible by the authors of [FOCS 20].
rate research
Read More
Given a graph $G = (V,E)$, an $(alpha, beta)$-ruling set is a subset $S subseteq V$ such that the distance between any two vertices in $S$ is at least $alpha$, and the distance between any vertex in $V$ and the closest vertex in $S$ is at most $beta$. We present lower bounds for distributedly computing ruling sets. More precisely, for the problem of computing a $(2, beta)$-ruling set in the LOCAL model, we show the following, where $n$ denotes the number of vertices, $Delta$ the maximum degree, and $c$ is some universal constant independent of $n$ and $Delta$. $bullet$ Any deterministic algorithm requires $Omegaleft(min left{ frac{log Delta}{beta log log Delta} , log_Delta n right} right)$ rounds, for all $beta le c cdot minleft{ sqrt{frac{log Delta}{log log Delta}} , log_Delta n right}$. By optimizing $Delta$, this implies a deterministic lower bound of $Omegaleft(sqrt{frac{log n}{beta log log n}}right)$ for all $beta le c sqrt[3]{frac{log n}{log log n}}$. $bullet$ Any randomized algorithm requires $Omegaleft(min left{ frac{log Delta}{beta log log Delta} , log_Delta log n right} right)$ rounds, for all $beta le c cdot minleft{ sqrt{frac{log Delta}{log log Delta}} , log_Delta log n right}$. By optimizing $Delta$, this implies a randomized lower bound of $Omegaleft(sqrt{frac{log log n}{beta log log log n}}right)$ for all $beta le c sqrt[3]{frac{log log n}{log log log n}}$. For $beta > 1$, this improves on the previously best lower bound of $Omega(log^* n)$ rounds that follows from the 30-year-old bounds of Linial [FOCS87] and Naor [J.Disc.Math.91]. For $beta = 1$, i.e., for the problem of computing a maximal independent set, our results improve on the previously best lower bound of $Omega(log^* n)$ on trees, as our bounds already hold on trees.
We present $O(loglog n)$ round scalable Massively Parallel Computation algorithms for maximal independent set and maximal matching, in trees and more generally graphs of bounded arboricity, as well as for constant coloring trees. Following the standards, by a scalable MPC algorithm, we mean that these algorithms can work on machines that have capacity/memory as small as $n^{delta}$ for any positive constant $delta<1$. Our results improve over the $O(log^2log n)$ round algorithms of Behnezhad et al. [PODC19]. Moreover, our matching algorithm is presumably optimal as its bound matches an $Omega(loglog n)$ conditional lower bound of Ghaffari, Kuhn, and Uitto [FOCS19].
There are distributed graph algorithms for finding maximal matchings and maximal independent sets in $O(Delta + log^* n)$ communication rounds; here $n$ is the number of nodes and $Delta$ is the maximum degree. The lower bound by Linial (1987, 1992) shows that the dependency on $n$ is optimal: these problems cannot be solved in $o(log^* n)$ rounds even if $Delta = 2$. However, the dependency on $Delta$ is a long-standing open question, and there is currently an exponential gap between the upper and lower bounds. We prove that the upper bounds are tight. We show that maximal matchings and maximal independent sets cannot be found in $o(Delta + log log n / log log log n)$ rounds with any randomized algorithm in the LOCAL model of distributed computing. As a corollary, it follows that there is no deterministic algorithm for maximal matchings or maximal independent sets that runs in $o(Delta + log n / log log n)$ rounds; this is an improvement over prior lower bounds also as a function of $n$.
The problem of scheduling unrelated machines by a truthful mechanism to minimize the makespan was introduced in the seminal Algorithmic Mechanism Design paper by Nisan and Ronen. Nisan and Ronen showed that there is a truthful mechanism that provides an approximation ratio of $min(m,n)$, where $n$ is the number of machines and $m$ is the number of jobs. They also proved that no truthful mechanism can provide an approximation ratio better than $2$. Since then, the lower bound was improved to $1 +sqrt 2 approx 2.41$ by Christodoulou, Kotsoupias, and Vidali, and then to $1+phiapprox 2.618$ by Kotsoupias and Vidali. Very recently, the lower bound was improved to $2.755$ by Giannakopoulos, Hammerl, and Pocas. In this paper we further improve the bound to $3-delta$, for every constant $delta>0$. Note that a gap between the upper bound and the lower bounds exists even when the number of machines and jobs is very small. In particular, the known $1+sqrt{2}$ lower bound requires at least $3$ machines and $5$ jobs. In contrast, we show a lower bound of $2.2055$ that uses only $3$ machines and $3$ jobs and a lower bound of $1+sqrt 2$ that uses only $3$ machines and $4$ jobs. For the case of two machines and two jobs we show a lower bound of $2$. Similar bounds for two machines and two jobs were known before but only via complex proofs that characterized all truthful mechanisms that provide a finite approximation ratio in this setting, whereas our new proof uses a simple and direct approach.
The minimum degree spanning tree (MDST) problem requires the construction of a spanning tree $T$ for graph $G=(V,E)$ with $n$ vertices, such that the maximum degree $d$ of $T$ is the smallest among all spanning trees of $G$. In this paper, we present two new distributed approximation algorithms for the MDST problem. Our first result is a randomized distributed algorithm that constructs a spanning tree of maximum degree $hat d = O(dlog{n})$. It requires $O((D + sqrt{n}) log^2 n)$ rounds (w.h.p.), where $D$ is the graph diameter, which matches (within log factors) the optimal round complexity for the related minimum spanning tree problem. Our second result refines this approximation factor by constructing a tree with maximum degree $hat d = O(d + log{n})$, though at the cost of additional polylogarithmic factors in the round complexity. Although efficient approximation algorithms for the MDST problem have been known in the sequential setting since the 1990s, our results are first efficient distributed solutions for this problem.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
