We consider locally checkable labeling (LCL) problems in the LOCAL model of distributed computing. Since 2016, there has been a substantial body of work examining the possible complexities of LCL problems. For example...
详细信息
ISBN:
(纸本)9783959773096
We consider locally checkable labeling (LCL) problems in the LOCAL model of distributed computing. Since 2016, there has been a substantial body of work examining the possible complexities of LCL problems. For example, it has been established that there are no LCL problems exhibiting deterministic complexities falling between omega(log* n) and o(log n). This line of inquiry has yielded a wealth of algorithmic techniques and insights that are useful for algorithm designers. While the complexity landscape of LCL problems on general graphs, trees, and paths is now well understood, graph classes beyond these three cases remain largely unexplored. Indeed, recent research trends have shifted towards a fine-grained study of special instances within the domains of paths and trees. In this paper, we generalize the line of research on characterizing the complexity landscape of LCL problems to a much broader range of graph classes. We propose a conjecture that characterizes the complexity landscape of LCL problems for an arbitrary class of graphs that is closed under minors, and we prove a part of the conjecture. Some highlights of our findings are as follows. We establish a simple characterization of the minor-closed graph classes sharing the same deterministic complexity landscape as paths, where O(1), Theta(log* n), and Theta(n) are the only possible complexity classes. It is natural to conjecture that any minor-closed graph class shares the same complexity landscape as trees if and only if the graph class has bounded treewidth and unbounded pathwidth. We prove the "only if" part of the conjecture. For the class of graphs with pathwidth at most k, we show the existence of LCL problems with randomized and deterministic complexities Theta(n), Theta(n(1/2)), Theta(n(1/3)),..., Theta(n(1/k)) and the non-existence of LCL problems whose deterministic complexity is between omega(log* n) and o(n(1/k)). Consequently, in addition to the well-known complexity landscapes for paths, tre
Breadth-First-Search (BFS) trees serve a pivotal role in designing efficient graphalgorithms due to their efficacy in traversing and exploring graph structures with a systematic layer-by-layer approach. This paper in...
详细信息
ISBN:
(数字)9783031673214
ISBN:
(纸本)9783031673207;9783031673214
Breadth-First-Search (BFS) trees serve a pivotal role in designing efficient graphalgorithms due to their efficacy in traversing and exploring graph structures with a systematic layer-by-layer approach. This paper introduces an agent-based novel approach for constructing a BFS tree on an arbitrary anonymous graph G with n nodes and m edges using k >= n autonomous mobile agents. In this paper, we provide algorithms for BFS tree construction for different starting configurations and demonstrate their applications. Our main result considers the dispersed starting configuration (i.e., each node is occupied by a single agent at the start) and takes O(D Delta) rounds to execute, where D is the diameter and Delta is the highest degree of G. The algorithm assumes the knowledge of a root node for the BFS tree. We further continue our investigation for BFS tree construction with two other classical configurations, namely, rooted configuration and arbitrary configuration (with and without the knowledge of root) of the agents with some other follow-up configurations for k > n. In addition, the paper demonstrates the application of the BFS tree construction methodology in tasks like - checking a graph for bipartiteness and gathering agents into a single node, a fundamental task in distributed robotics.
By prior work, it is known that any distributedgraph algorithm that finds a maximal matching requires Omega(log* n) communication rounds, while it is possible to find a maximal fractional matching in O(1) rounds in b...
详细信息
ISBN:
(纸本)9783031327322;9783031327339
By prior work, it is known that any distributedgraph algorithm that finds a maximal matching requires Omega(log* n) communication rounds, while it is possible to find a maximal fractional matching in O(1) rounds in bounded-degree graphs. However, all prior O(1)-round algorithms for maximal fractional matching use arbitrarily fine-grained fractional values. In particular, none of them is able to find a half-integral solution, using only values from {0, 1/2, 1}. We show that the use of finegrained fractional values is necessary, and moreover we give a complete characterization on exactly how small values are needed: if we consider maximal fractional matching in graphs of maximum degree Delta = 2d, and any distributedgraph algorithm with round complexity T(Delta) that only depends on Delta and is independent of n, we show that the algorithm has to use fractional values with a denominator at least 2(d). We give a new algorithm that shows that this is also sufficient.
We study distributedalgorithms built around minor-based vertex sparsifiers, and give the first algorithm in the CONGEST model for solving linear systems in graph Laplacian matrices to high accuracy. Our Laplacian sol...
详细信息
ISBN:
(纸本)9781665420556
We study distributedalgorithms built around minor-based vertex sparsifiers, and give the first algorithm in the CONGEST model for solving linear systems in graph Laplacian matrices to high accuracy. Our Laplacian solver has a round complexity of O(n(o(1))(root n + D)), and thus almost matches the lower bound of (Omega) over tilde(root n+D), where n is the number of nodes in the network and D is its diameter. We show that our distributed solver yields new sublinear round algorithms for several cornerstone problems in combinatorial optimization. This is achieved by leveraging the powerful algorithmic framework of Interior Point Methods (IPMs) and the Laplacian paradigm in the context of distributed graph algorithms, which entails numerically solving optimization problems on graphs via a series of Laplacian systems. Problems that benefit from our distributed algorithmic paradigm include exact mincost flow, negative weight shortest paths, maxflow, and bipartite matching on sparse directed graphs. For the maxflow problem, this is the first exact distributed algorithm that applies to directed graphs, while the previous work by [Ghaffari et al. SICOMP'18] considered the approximate setting and works only for undirected graphs. For the mincost flow and the negative weight shortest path problems, our results constitute the first exact distributedalgorithms running in a sublinear number of rounds. Given that the hybrid between IPMs and the Laplacian paradigm has proven useful for tackling numerous optimization problems in the centralized setting, we believe that our distributed solver will find future applications. At the heart of our distributed Laplacian solver is the notion of spectral subspace sparsifiers of [Li, Schild FOCS'18]. We present a nontrivial distributed implementation of their construction by (i) giving a parallel variant of their algorithm that avoids the sampling of random spanning trees and uses approximate leverage scores instead, and (ii) showing that t
distributedalgorithms for constructing structures such as a maximal independent set (MIS) or maximal matching (MM) are wellstudied in standard message-passing network models. In this paper, we consider a natural vari...
详细信息
ISBN:
(纸本)9781450391467
distributedalgorithms for constructing structures such as a maximal independent set (MIS) or maximal matching (MM) are wellstudied in standard message-passing network models. In this paper, we consider a natural variant of this problem in which we begin with an instance of the graph structure and partition our algorithm execution that follows into two stages. During the first stage after the graph structure is calculated, some additional precomputation is done. In the second stage, an arbitrary collection of.. nodes are crashed. The goal is to then repair the structure as efficiently as possible. We are interested in the circumstances under which the repair can be faster than the time required to build the structure from scratch, and focus, in particular, on trade-offs in which extra precomputation rounds during the first stage can be traded for faster repairs during the second.
Many combinatorial optimization problems, including maximum weighted matching and maximum independent set, can be approximated within (1 +/-epsilon) factors in poly(log n, 1/epsilon) rounds in the LOCAL model via netw...
详细信息
ISBN:
(纸本)9781450392624
Many combinatorial optimization problems, including maximum weighted matching and maximum independent set, can be approximated within (1 +/-epsilon) factors in poly(log n, 1/epsilon) rounds in the LOCAL model via network decompositions [Ghaffari, Kuhn, and Maus, STOC 2018]. These approaches, however, require sending messages of unlimited size, so they do not extend to the more realistic CONGEST model, which restricts the message size to be O(log n) bits. For example, despite the long line of research devoted to the distributed matching problem, it still remains a major open problem whether an (1 - epsilon)-approximate maximum weighted matching can be computed in poly(log n, 1/epsilon) rounds in the CONGEST model. In this paper, we develop a generic framework for obtaining poly(log n, 1/epsilon)-round (1 +/- epsilon)-approximation algorithms for many combinatorial optimization problems, including maximum weighted matching, maximum independent set, and correlation clustering, in graphs excluding a fixed minor in the CONGEST model. This class of graphs covers many sparse network classes that have been studied in the literature, including planar graphs, bounded-genus graphs, and bounded-treewidth graphs. Furthermore, we show that our framework can be applied to give an efficient distributed property testing algorithm for an arbitrary minor-closed graph property that is closed under taking disjoint union, significantly generalizing the previous distributed property testing algorithm for planarity in [Levi, Medina, and Ron, PODC 2018 & distributed Computing 2021]. Our framework uses distributed expander decomposition algorithms [Chang and Saranurak, FOCS 2020] to decompose the graph into clusters of high conductance. We show that any graph excluding a fixed minor admits small edge separators. Using this result, we show the existence of a high-degree vertex in each cluster in an expander decomposition, which allows the entire graph topology of the cluster to be routed to a
We present a simple deterministic distributed algorithm that computes a (Delta+1)-vertex coloring in O(log(2) Delta center dot log n) rounds. The algorithm can be implemented with O(log n)-bit messages. The algorithm ...
详细信息
ISBN:
(纸本)9781665420556
We present a simple deterministic distributed algorithm that computes a (Delta+1)-vertex coloring in O(log(2) Delta center dot log n) rounds. The algorithm can be implemented with O(log n)-bit messages. The algorithm can also be extended to the more general (degree + 1)-list coloring problem. Obtaining a polylogarithmic-time deterministic algorithm for (Delta + 1)-vertex coloring had remained a central open question in the area of distributed graph algorithms since the 1980s, until a recent network decomposition algorithm of Rozho.n and Ghaffari [STOC'20]. The current state of the art is based on an improved variant of their decomposition, which leads to an O(log(5) n)-round algorithm for (Delta + 1)-vertex coloring. Our coloring algorithm is completely different and considerably simpler and faster. It solves the coloring problem in a direct way, without using network decomposition, by gradually rounding a certain fractional color assignment until reaching an integral color assignments. Moreover, via the approach of Chang, Li, and Pettie [STOC'18], this improved deterministic algorithm also leads to an improvement in the complexity of randomized algorithms for (Delta + 1)-coloring, now reaching the bound of O(log(3) log n) rounds. As a further application, we provide faster deterministic distributedalgorithms for the following vertex coloring variants. In graphs of arboricity a, we show that a (2 + epsilon)a-vertex coloring can be computed in O(log(3) a center dot log n) rounds. We also show that for Delta >= 3, a Delta-coloring of a Delta-colorable graph G can be computed in O(log(2) Delta center dot log(2) n) rounds.
This paper investigates the energy complexity of distributedgraph problems in multi-hop radio networks, where the energy cost of an algorithm is measured by the maximu m number of awake rounds of a vertex. Recent wor...
详细信息
This paper investigates the energy complexity of distributedgraph problems in multi-hop radio networks, where the energy cost of an algorithm is measured by the maximu m number of awake rounds of a vertex. Recent works revealed that some problems, such as broadcast, breadth-first search, and maximal matching, can be solved with energy-ecient algorithms that consume only poly log n energy. However, there exist some problems, such as computing the diameter of the graph, that requir e Omega(n) energy to solve. To improve energ y eciency for these problems, we focus on a special graph class: bounded-genus graphs. We present algorithms for computin g the exact diameter, the exact global minimum cut size , and a (1 +/- epsilon)-approximate s-t minimum cut root size with O( root n) energy for bounded-genus graphs. Our approach is based on a generic framework that divides the vertex set into high-degree and low-degree parts and leverages the structural properties of bounded-genus graphs to control the number of certain connected components in the subgraph induced by the low-degree part.
By prior work, it is known that any distributedgraph algorithm that finds a maximal matching requires omega(log* n) communication rounds, while it is possible to find a maximal fractional matching in 0(1) rounds in b...
详细信息
By prior work, it is known that any distributedgraph algorithm that finds a maximal matching requires omega(log* n) communication rounds, while it is possible to find a maximal fractional matching in 0(1) rounds in bounded-degree graphs. However, all prior 0(1)-round algorithms for maximal fractional matching use arbitrarily fine-grained fractional values. In particular, none of them is able to find a half-integral solution, using only values from {0, 21, 1}. We show that the use of fine-grained fractional values is necessary, and moreover we give a complete characterization on exactly how small values are needed: if we consider maximal fractional matching in graphs of maximum degree Delta = 2d, and any distributedgraph algorithm with round complexity T(Delta) that only depends on Delta and is independent of n, we show that the algorithm has to use fractional values with a denominator at least 2d. We give a new algorithm that shows that this is also sufficient.
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. is the maximum degree. The lower bound by...
详细信息
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. 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 any algorithm that finds a maximal matching or maximal independent set with probability at least 1 - 1/n requires Omega(min{Delta, log logn/ log log logn}) rounds in the LOCAL model of distributed computing. As a corollary, it follows that any deterministic algorithm that finds a maximal matching or maximal independent set requires Omega(min{Delta, logn/ log logn}) rounds;this is an improvement over prior lower bounds also as a function of n.
暂无评论