We present the first super-linear lower bounds for natural graph problems in the CONGEST model, answering a long-standing open question. Specifically, we show that any exact computation of a minimum vertex cover or a maximum independent set requires @math rounds in the worst case in the CONGEST model, as well as any algorithm for @math -coloring a graph, where @math is the chromatic number of the graph. We further show that such strong lower bounds are not limited to NP-hard problems, by showing two simple graph problems in P which require a quadratic and near-quadratic number of rounds. Finally, we address the problem of computing an exact solution to weighted all-pairs-shortest-paths (APSP), which arguably may be considered as a candidate for having a super-linear lower bound. We show a simple @math lower bound for this problem, which implies a separation between the weighted and unweighted cases, since the latter is known to have a complexity of @math . We also formally prove that the standard Alice-Bob framework is incapable of providing a super-linear lower bound for exact weighted APSP, whose complexity remains an intriguing open question.
One of the most central problems in graph theory is vertex coloring, which has been extensively studied in the context of distributed computing (see, e.g., @cite_25 @cite_22 @cite_27 @cite_11 @cite_57 @cite_6 @cite_52 @cite_44 @cite_48 @cite_40 @cite_35 @cite_7 @cite_23 @cite_14 @cite_46 @cite_8 @cite_36 and references therein). The special case of finding a @math -coloring, where @math is the maximum degree of a node in the network, has been the focus of many of these studies, but is a problem, which can be solved in much less than a sublinear number of rounds.
@cite_35 @cite_14 @cite_22 @cite_7 @cite_8 @cite_36 @cite_48 @cite_52 @cite_6 @cite_57 @cite_44 @cite_27 @cite_40 @cite_23 @cite_46 @cite_25 @cite_11
1976011215 2009970369 88197230 2067661972 2169324896 2030160771 2054910423 2136185479 2065826935 2797253418 2110673270 2279830512 2467514673 2751147784
During and immediately after their deployment, ad hoc and sensor networks lack an efficient communication scheme rendering even the most basic network coordination problems difficult. Before any reasonable communication can take place, nodes must come up with an initial structure that can serve as a foundation for more sophisticated algorithms. In this paper, we consider the problem of obtaining a vertex coloring as such an initial structure. We propose an algorithm that works in the unstructured radio network model. This model captures the characteristics of newly deployed ad hoc and sensor networks, i.e. asynchronous wake-up, no collision-detection, and scarce knowledge about the network topology. When modeling the network as a graph with bounded independence, our algorithm produces a correct coloring with O(Δ) colors in time O(Δ log n) with high probability, where n and Δ are the number of nodes in the network and the maximum degree, respectively. Also, the number of locally used colors depends only on the local node density. Graphs with bounded independence generalize unit disk graphs as well as many other well-known models for wireless multi-hop networks. They allow us to capture aspects such as obstacles, fading, or irregular signal-propagation. The Lovasz Local Lemma (LLL), introduced by Erdos and Lovasz in 1975, is a powerful tool of the probabilistic method that allows one to prove that a set of n "bad" events do not happen with non-zero probability, provided that the events have limited dependence. However, the LLL itself does not suggest how to find a point avoiding all bad events. Since the work of Beck (1991) there has been a sustained effort to find a constructive proof (i.e. an algorithm) for the LLL or weaker versions of it. In a major breakthrough Moser and Tardos (2010) showed that a point avoiding all bad events can be found efficiently. They also proposed a distributed parallel version of their algorithm that requires O(log2 n) rounds of communication in a distributed network. In this paper we provide two new distributed algorithms for the LLL that improve on both the efficiency and simplicity of the Moser-Tardos algorithm. For clarity we express our results in terms of the symmetric LLL though both algorithms deal with the asymmetric version as well. Let p bound the probability of any bad event and d be the maximum degree in the dependency graph of the bad events. When epd2 In many graph coloring problems the existence of a valid coloring is established by one or more applications of the LLL. Using our LLL algorithms, we give logarithmic-time distributed algorithms for frugal coloring, defective coloring, coloring girth-4 (triangle-free) and girth-5 graphs, edge coloring, and list coloring. We deterministically compute a Δ + 1 coloring in time O(Δ5c+2 ċ (Δ5)2 c (Δ1)e + (Δ1)e + log* n) and O(Δ5c+2 ċ (Δ5)1 c Δe + Δe + (Δ5)d log Δ5 log n) for arbitrary constants d, e and arbitrary constant integer c, where Δi is defined as the maximal number of nodes within distance i for a node and Δ := Δ1. Our greedy algorithm improves the state-of-the-art Δ + 1 coloring algorithms for a large class of graphs, e.g. graphs of moderate neighborhood growth. We also state and analyze a randomized coloring algorithm in terms of the chromatic number, the run time and the used colors. If Δ ∈ Ω(log1+1 log* n n) and χ ∈ O(Δ log1+1 log* n n) then our algorithm executes in time O(log χ + log* n) with high probability. For graphs of polylogarithmic chromatic number the analysis reveals an exponential gap compared to the fastest Δ + 1 coloring algorithm running in time O(log Δ + √log n). The algorithm works without knowledge of χ and uses less than Δ colors, i.e., (1 - 1 O(χ))Δ with high probability. To the best of our knowledge this is the first distributed algorithm for (such) general graphs taking the chromatic number χ into account. The following problem is considered: given a linked list of length n , compute the distance from each element of the linked list to the end of the list. The problem has two standard deterministic algorithms: a linear time serial algorithm, and an O (log n ) time parallel algorithm using n processors. We present new deterministic parallel algorithms for the problem. Our strongest results are (1) O (log n log* n ) time using n (log n log* n ) processors (this algorithm achieves optimal speed-up); (2) O (log n ) time using n log ( k ) n log n processors, for any fixed positive integer k . The algorithms apply a novel “random-like” deterministic technique. This technique provides for a fast and efficient breaking of an apparently symmetric situation in parallel and distributed computation. We consider the distributed message-passing @math model. In this model a communication network is represented by a graph where vertices host processors, and communication is performed over the edges. Computation proceeds in synchronous rounds. The running time of an algorithm is the number of rounds from the beginning until all vertices terminate. Local computation is free. An algorithm is called local if it terminates within a constant number of rounds. The question of what problems can be computed locally was raised by Naor and Stockmeyer [16] in their seminal paper in STOC'93. Since then the quest for problems with local algorithms, and for problems that cannot be computed locally, has become a central research direction in the field of distributed algorithms [9,11,13,17]. We devise the first local algorithm for an NP-complete problem. Specifically, our randomized algorithm computes, with high probability, an O(n1 2+e ·χ)-coloring within O(1) rounds, where e>0 is an arbitrarily small constant, and χ is the chromatic number of the input graph. (This problem was shown to be NP-complete in [21].) On our way to this result we devise a constant-time algorithm for computing (O(1), O(n1 2+e))-network-decompositions. Network-decompositions were introduced by [1], and are very useful for solving various distributed problems. The best previously-known algorithm for network-decomposition has a polylogarithmic running time (but is applicable for a wider range of parameters) [15]. We also devise a Δ1+e-coloring algorithm for graphs with sufficiently large maximum degree Δ that runs within O(1) rounds. It improves the best previously-known result for this family of graphs, which is O(log*n) [19]. This paper considers the computational power of anonymous message passing algorithms (henceforth, anonymous algorithms), i.e., distributed algorithms operating in a network of unidentified nodes. We prove that every problem that can be solved (and verified) by a randomized anonymous algorithm can also be solved by a deterministic anonymous algorithm provided that the latter is equipped with a 2-hop coloring of the input graph. Since the problem of 2-hop coloring a given graph (i.e., ensuring that two nodes with distance at most 2 have different colors) can by itself be solved by a randomized anonymous algorithm, it follows that with the exception of a few mock cases, the execution of every randomized anonymous algorithm can be decoupled into a generic preprocessing randomized stage that computes a 2-hop coloring, followed by a problem-specific deterministic stage. The main ingredient of our proof is a novel simulation method that relies on some surprising connections between 2-hop colorings and an extensively used graph lifting technique. This paper concerns a number of algorithmic problems on graphs and how they may be solved in a distributed fashion. The computational model is such that each node of the graph is occupied by a processor which has its own ID. Processors are restricted to collecting data from others which are at a distance at most t away from them in t time units, but are otherwise computationally unbounded. This model focuses on the issue of locality in distributed processing, namely, to what extent a global solution to a computational problem can be obtained from locally available data.Three results are proved within this model: • A 3-coloring of an n-cycle requires time @math . This bound is tight, by previous work of Cole and Vishkin. • Any algorithm for coloring the d-regular tree of radius r which runs for time at most @math requires at least @math colors. • In an n-vertex graph of largest degree @math , an @math -coloring may be found in time @math . The distributed @math -coloring problem is one of the most fundamental and well-studied problems in distributed algorithms. Starting with the work of Cole and Vishkin in 1986, a long line of gradually improving algorithms has been published. The state-of-the-art running time, prior to our work, is @math , due to Kuhn and Wattenhofer [Proceedings of the @math th Annual ACM Symposium on Principles of Distributed Computing, Denver, CO, 2006, pp. 7--15]. Linial [Proceedings of the @math th Annual IEEE Symposium on Foundation of Computer Science, Los Angeles, CA, 1987, pp. 331--335] proved a lower bound of @math for the problem, and Szegedy and Vishwanathan [Proceedings of the 25th Annual ACM Symposium on Theory of Computing, San Diego, CA, 1993, pp. 201--207] provided a heuristic argument that shows that algorithms from a wide family of locally iterative algorithms are unlikely to achieve a running time smaller than @math . We present a de... Consider an n-vertex graph G = (V, E) of maximum degree Δ, and suppose that each vertex v ∈ V hosts a processor. The processors are allowed to communicate only with their neighbors in G. The communication is synchronous, that is, it proceeds in discrete rounds. In the distributed vertex coloring problem, the objective is to color G with Δ + 1, or slightly more than Δ + 1, colors using as few rounds of communication as possible. (The number of rounds of communication will be henceforth referred to as running time.) Efficient randomized algorithms for this problem are known for more than twenty years [ 1986; Luby 1986]. Specifically, these algorithms produce a (Δ + 1)-coloring within O(log n) time, with high probability. On the other hand, the best known deterministic algorithm that requires polylogarithmic time employs O(Δ2) colors. This algorithm was devised in a seminal FOCS’87 paper by Linial [1987]. Its running time is O(log* n). In the same article, Linial asked whether one can color with significantly less than Δ2 colors in deterministic polylogarithmic time. By now, this question of Linial became one of the most central long-standing open questions in this area. In this article, we answer this question in the affirmative, and devise a deterministic algorithm that employs Δ1+o(1) colors, and runs in polylogarithmic time. Specifically, the running time of our algorithm is O(f(Δ)log Δ log n), for an arbitrarily slow-growing function f(Δ) = ω(1). We can also produce an O(Δ1+η)-coloring in O(log Δ log n)-time, for an arbitrarily small constant η > 0, and an O(Δ)-coloring in O(Δe log n) time, for an arbitrarily small constant e > 0. Our results are, in fact, far more general than this. In particular, for a graph of arboricity a, our algorithm produces an O(a1+η)-coloring, for an arbitrarily small constant η > 0, in time O(log a log n). We give a new randomized distributed algorithm for (Δ +1)-coloring in the LOCAL model, running in O(s log Δ)+ 2O(slog log n) rounds in a graph of maximum degree Δ. This implies that the (Δ +1)-coloring problem is easier than the maximal independent set problem and the maximal matching problem, due to their lower bounds of Ω(min(sflog n log log n, flog Δ log log Δ)) by Kuhn, Moscibroda, and Wattenhofer [PODC’04]. Our algorithm also extends to list-coloring where the palette of each node contains Δ +1 colors. We extend the set of distributed symmetry-breaking techniques by performing a decomposition of graphs into dense and sparse parts. Vertex coloring is a central concept in graph theory and an important symmetry-breaking primitive in distributed computing. Whereas degree-Δ graphs may require palettes of Δ + 1 colors in the worst case, it is well known that the chromatic number of many natural graph classes can be much smaller. In this paper we give new distributed algorithms to find ( Δ k ) -coloring in graphs of girth 4 (triangle-free graphs), girth 5, and trees. The parameter k can be at most ( 1 4 - o ( 1 ) ) ln ? Δ in triangle-free graphs and at most ( 1 - o ( 1 ) ) ln ? Δ in girth-5 graphs and trees, where o ( 1 ) is a function of Δ. Specifically, for Δ sufficiently large we can find such a coloring in O ( k + log * ? n ) time. Moreover, for any Δ we can compute such colorings in roughly logarithmic time for triangle-free and girth-5 graphs, and in O ( log ? Δ + log Δ ? log ? n ) time on trees. As a byproduct, our algorithm shows that the chromatic number of triangle-free graphs is at most ( 4 + o ( 1 ) ) Δ ln ? Δ , which improves on Jamall's recent bound of ( 67 + o ( 1 ) ) Δ ln ? Δ . Finally, we show that ( Δ + 1 ) -coloring for triangle-free graphs can be obtained in sublogarithmic time for any Δ. Over the past 30 years numerous algorithms have been designed for symmetry breaking problems in the LOCAL model, such as maximal matching, MIS, vertex coloring, and edge-coloring. For most problems the best randomized algorithm is at least exponentially faster than the best deterministic algorithm. In this paper we prove that these exponential gaps are necessary and establish connections between the deterministic and randomized complexities in the LOCAL model. Each result has a very compelling take-away message: 1. Fast @math -coloring of trees requires random bits: Building on the recent lower bounds of , we prove that the randomized complexity of @math -coloring a tree with maximum degree @math is @math , whereas its deterministic complexity is @math for any @math . This also establishes a large separation between the deterministic complexity of @math -coloring and @math -coloring trees. 2. Randomized lower bounds imply deterministic lower bounds: We prove that any deterministic algorithm for a natural class of problems that runs in @math rounds can be transformed to run in @math rounds. If the transformed algorithm violates a lower bound (even allowing randomization), then one can conclude that the problem requires @math time deterministically. 3. Deterministic lower bounds imply randomized lower bounds: We prove that the randomized complexity of any natural problem on instances of size @math is at least its deterministic complexity on instances of size @math . This shows that a deterministic @math lower bound for any problem implies a randomized @math lower bound. It also illustrates that the graph shattering technique is absolutely essential to the LOCAL model. Symmetry-breaking problems are among the most well studied in the field of distributed computing and yet the most fundamental questions about their complexity remain open. In this article we work in the LOCAL model (where the input graph and underlying distributed network are identical) and study the randomized complexity of four fundamental symmetry-breaking problems on graphs: computing MISs (maximal independent sets), maximal matchings, vertex colorings, and ruling sets. A small sample of our results includes the following: —An MIS algorithm running in O(log2D Δ L 2√log n, and comes close to the Ω(flog Δ log log Δ lower bound of Kuhn, Moscibroda, and Wattenhofer. —A maximal matching algorithm running in O(log Δ + log 4log n) time. This is the first significant improvement to the 1986 algorithm of Israeli and Itai. Moreover, its dependence on Δ is nearly optimal. —A (Δ + 1)-coloring algorithm requiring O(log Δ + 2o(√log log n) time, improving on an O(log Δ + √log n)-time algorithm of Schneider and Wattenhofer. —A method for reducing symmetry-breaking problems in low arboricity degeneracy graphs to low-degree graphs. (Roughly speaking, the arboricity or degeneracy of a graph bounds the density of any subgraph.) Corollaries of this reduction include an O(√log n)-time maximal matching algorithm for graphs with arboricity up to 2√log n and an O(log 2 3n)-time MIS algorithm for graphs with arboricity up to 2(log n)1 3. Each of our algorithms is based on a simple but powerful technique for reducing a randomized symmetry-breaking task to a corresponding deterministic one on a poly(log n)-size graph. Numerous problems in Theoretical Computer Science can be solved very efficiently using powerful algebraic constructions. Computing shortest paths, constructing expanders, and proving the PCP Theorem, are just few examples of this phenomenon. The quest for combinatorial algorithms that do not use heavy algebraic machinery, but are roughly as efficient, has become a central field of study in this area. Combinatorial algorithms are often simpler than their algebraic counterparts. Moreover, in many cases, combinatorial algorithms and proofs provide additional understanding of studied problems. In this paper we initiate the study of combinatorial algorithms for Distributed Graph Coloring problems. In a distributed setting a communication network is modeled by a graph (G=(V,E) ) of maximum degree ( ). The vertices of (G ) host the processors, and communication is performed over the edges of (G ). The goal of distributed vertex coloring is to color (V ) with (( + 1) ) colors such that any two neighbors are colored with distinct colors. Currently, efficient algorithms for vertex coloring that require (O( + ^* n) ) time are based on the algebraic algorithm of Linial (SIAM J Comput 21(1):193–201, 1992) that employs set-systems. The best currently-known combinatorial set-system free algorithm, due to (SIAM J Discret Math 1(4):434–446, 1988), requires (O( ^2+ ^*n) ) time. We significantly improve over this by devising a combinatorial (( + 1) )-coloring algorithm that runs in (O( + ^* n) ) time. This exactly matches the running time of the best-known algebraic algorithm. In addition, we devise a tradeoff for computing (O( t) )-coloring in (O( t + ^* n) ) time, for almost the entire range (1 < t < ). We also compute a Maximal Independent Set in (O( + ^* n) ) time on general graphs, and in (O( n n) ) time on graphs of bounded arboricity. Prior to our work, these results could be only achieved using algebraic techniques. We believe that our algorithms are more suitable for real-life networks with limited resources, such as sensor networks.