Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. Motivated by several recent studies of local graph algorithms, we consider the following variant of this problem. Let G be a conn...
详细信息
Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. Motivated by several recent studies of local graph algorithms, we consider the following variant of this problem. Let G be a connected bounded-degree graph. Given an edge e in G we would like to decide whether e belongs to a connected subgraph G consisting of (1+E)n edges (for a prespecified constant E>0), where the decision for different edges should be consistent with the same subgraph G. Can this task be performed by inspecting only a constant number of edges in G? Our main results are: We show that if every t-vertex subgraph of G has expansion 1/(logt)1+o(1) then one can (deterministically) construct a sparse spanning subgraph G of G using few inspections. To this end we analyze a local version of a famous minimum-weight spanning tree algorithm. We show that the above expansion requirement is sharp even when allowing randomization. To this end we construct a family of 3-regular graphs of high girth, in which every t-vertex subgraph has expansion 1/(logt)1-o(1). We prove that for this family of graphs, any local algorithm for the sparse spanning graph problem requires inspecting a number of edges which is proportional to the girth. (c) 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 183-200, 2017
This paper is centered on the complexity of graph problems in the well-studied local model of distributed computing, introduced by Linial FOCS'87]. It is widely known that for many of the classic distributed graph...
详细信息
ISBN:
(纸本)9781450345286
This paper is centered on the complexity of graph problems in the well-studied local model of distributed computing, introduced by Linial FOCS'87]. It is widely known that for many of the classic distributed graph problems (including maximal independent set (MIS) and (Delta + 1)-vertex coloring), the randomized complexity is at most polylogarithmic in the size n of the network, while the best deterministic complexity is typically 2(O(root log n)). Understanding and potentially narrowing down this exponential gap is considered to be one of the central long-standing open questions in the area of distributed graph algorithms. We investigate the problem by introducing a complexity-theoretic framework that allows us to shed some light on the role of randomness in the local model. We define the Slocal model as a sequential version of the local model. Our framework allows us to prove completeness results with respect to the class of problems which can be solved efficiently in the Slocal model, implying that if any of the complete problems can be solved deterministically in poly log n rounds in the local model, we can deterministically solve all efficient Slocal-problems (including MIS and (Delta + 1)coloring) in poly log n rounds in the local model. Perhaps most surprisingly, we show that a rather rudimentary looking graph coloring problem is complete in the above sense: Color the nodes of a graph with colors red and blue such that each node of suficiently large polylogarithmic degree has at least one neighbor of each color. The problem admits a trivial zero-round randomized solution. The result can be viewed as showing that the only obstacle to getting efficient determinstic algorithms in the local model is an efficient algorithm to approximately round fractional values into integer values. In addition, our formal framework also allows us to develop polylogarithmic-time randomized distributed algorithms in a simpler way. As a result, we provide a polylog-time distributed
We consider a problem of routing on directed paths and trees to a single destination, with rate-limited, adversarial traffic. In particular, we focus on local buffer management algorithms that ensure no packet loss, w...
详细信息
ISBN:
(纸本)9781450345934
We consider a problem of routing on directed paths and trees to a single destination, with rate-limited, adversarial traffic. In particular, we focus on local buffer management algorithms that ensure no packet loss, while minimizing the size of the required buffers. While a centralized algorithm for the problem that uses constant-sized buffers has been recently shown [21], there is no known local algorithm that achieves a sub-linear buffer size. In this paper we show tight bounds for the maximum buffer size needed by l-local algorithms for information gathering on directed paths and trees, where an algorithm is called l-local if the decision made by each node v depends only on the sizes of the buffers at most l hops away from v. We show three main results: a lower bound of Omega(c log n/l) for all l -local algorithms on both directed and undirected paths, where c is an upper bound on the link capacity and injection rate. a surprisingly simple 1-local algorithm for directed paths that uses buffers of size O(log n), when c = 1. center dot a natural 2-local extension of this algorithm to directed trees, for c = 1, with the same asymptotic bound. Our Omega (log n) lower bound is significantly lower than the Omega(n) lower bound for greedy algorithms, and perhaps surprisingly, there is a matching upper bound. The algorithm that achieves it can be summarized in two lines: If the size of your buffer is odd, forward a message if your successor's buffer size is equal or lower. If your buffer size is even, forward a message only if your successor's buffer size is strictly lower. For trees, a simple arbitration between siblings is added.
locally-biased graph algorithms are algorithms that attempt to find local or small-scale structure in a large data graph. In some cases, this can be accomplished by adding some sort of locality constraint and calling ...
详细信息
locally-biased graph algorithms are algorithms that attempt to find local or small-scale structure in a large data graph. In some cases, this can be accomplished by adding some sort of locality constraint and calling a traditional graph algorithm;but more interesting are locally-biased graph algorithms that compute answers by running a procedure that does not even look at most of the input graph. This corresponds more closely to what practitioners from various data science domains do, but it does not correspond well with the way that algorithmic and statistical theory is typically formulated. Recent work from several research communities has focused on developing locally-biased graph algorithms that come with strong complementary algorithmic and statistical theory and that are useful in practice in downstream data science applications. We provide a review and overview of this work, highlighting commonalities between seemingly different approaches, and highlighting promising directions for future work.
We present a deterministic distributed algorithm that computes a (2 Delta - 1)-edge-coloring, or even list-edgecoloring, in any n-node graph with maximum degree Delta, in O(log(8) Delta . log n) rounds. This answers o...
详细信息
ISBN:
(纸本)9781538634646
We present a deterministic distributed algorithm that computes a (2 Delta - 1)-edge-coloring, or even list-edgecoloring, in any n-node graph with maximum degree Delta, in O(log(8) Delta . log n) rounds. This answers one of the long-standing open questions of distributed graph algorithms from the late 1980s, which asked for a polylogarithmic-time algorithm. See, e.g., Open Problem 4 in the Distributed Graph Coloring book of Barenboim and Elkin. The previous best round complexities were 2(O(root log n)) by Panconesi and Srinivasan [STOC' 92] and (O) over tilde (root Delta) + O(log* n) by Fraigniaud, Heinrich, and Kosowski [FOCS' 16]. A corollary of our deterministic list-edge-coloring also improves the randomized complexity of (2 Delta - 1)-edgecoloring to poly(log log n) rounds. The key technical ingredient is a deterministic distributed algorithm for hypergraph maximal matching, which we believe will be of interest beyond this result. In any hypergraph of rank r - where each hyperedge has at most r vertices - with n nodes and maximum degree Delta, this algorithm computes a maximal matching in O(r(5) log(6+log r) Delta . log n) rounds. This hypergraph matching algorithm and its extensions also lead to a number of other results. In particular, we obtain a polylogarithmic-time deterministic distributed maximal independent set (MIS) algorithm for graphs with bounded neighborhood independence, hence answering Open Problem 5 of Barenboim and Elkin's book, a ((log Delta/epsilon)(O(log 1/epsilon)) - round deterministic algorithm for (1 + epsilon)-approximation of maximum matching, and a quasi-polylogarithmic-time deterministic distributed algorithm for orienting lambda-arboricity graphs with out-degree at most inverted right perpendicular (1 + epsilon)lambda inverted left perpendicular, for any constant epsilon > 0, hence partially answering Open Problem 10 of Barenboim and Elkin's book.
We discuss local elimination algorithms that compute global information using local computations. Results of benchmarking show real computational capabilities of block elimination algorithms combined with SYMPHONY sol...
详细信息
ISBN:
(纸本)9781467345026;9781467345002
We discuss local elimination algorithms that compute global information using local computations. Results of benchmarking show real computational capabilities of block elimination algorithms combined with SYMPHONY solver. Strategies for parallelizing a sequential local elimination algorithm for sparse discrete optimization problems are analyzed. We propose to use hybrid Master-Worker scheme where Worker processors (GPUs) solve concurrently subproblems corresponding to super-nodes of extended elimination tree that are generated by a single master process (CPU).
A local algorithm with local horizon r is a distributed algorithm that runs in r synchronous communication rounds;here r is a constant that does not depend on the size of the network. As a consequence, the output of a...
详细信息
A local algorithm with local horizon r is a distributed algorithm that runs in r synchronous communication rounds;here r is a constant that does not depend on the size of the network. As a consequence, the output of a node in a local algorithm only depends on the input within r hops from the node. We give tight bounds on the local horizon for a class of local algorithms for combinatorial problems on unit-disk graphs (UDGs). Most of our bounds are due to a refined analysis of existing approaches, while others are obtained by suggesting new algorithms. The algorithms we consider are based on network decompositions guided by a rectangular tiling of the plane. The algorithms are applied to matching, independent set, graph colouring, vertex cover, and dominating set. We also study local algorithms on quasi-UDGs. which are a popular generalisation of UDGs, aimed at more realistic modelling of communication between the network nodes. Analysing the local algorithms on quasi-UDGs allows one to assume that the nodes know their coordinates only approximately, up to an additive error. Despite the localisation error, the quality of the solution to problems on quasi-UDGs remains the same as for the case of UDGs with perfect location awareness. We analyse the increase in the local horizon that comes along with moving from UDGs to quasi-UDGs. (C) 2011 Published by Elsevier B.V.
Limiting the knowledge of individual nodes is a major concern for the design of distributed algorithms. With the local model, theoretical research already established a common model of locality that has gained little ...
详细信息
Limiting the knowledge of individual nodes is a major concern for the design of distributed algorithms. With the local model, theoretical research already established a common model of locality that has gained little practical relevance. As a result, practical research de facto lacks any common locality model. The only common denominator among practitioners is that a local algorithm is distributed with a restricted scope of interaction. This article closes the gap by introducing four practically motivated classes of locality that successively weaken the strict requirements of the local model. These classes are applied to categorize and survey 36 local algorithms from 12 different application domains. A detailed comparison shows the practicality of the classification and provides interesting insights. For example, the majority of algorithms limit the scope of interaction to at most two hops, independent of their locality class. Moreover, the application domain of algorithms tends to influence their degree of locality.
We show that the first phase of the Linial-Saks network decomposition algorithm gives a randomized distributed O(nε)-approximation algorithm for the maximum independent set problem that operates in O(1/&#...
详细信息
ISBN:
(纸本)9781450339643
We show that the first phase of the Linial-Saks network decomposition algorithm gives a randomized distributed O(nε)-approximation algorithm for the maximum independent set problem that operates in O(1/ε) rounds, and we give a matching lower bound that holds even for bipartite graphs.
We investigate the problem of exactly reconstructing, with high confidence and up to isomorphism, the ball of radius r centered at the starting state of a Markov process from independent and anonymous experiments. In ...
详细信息
We investigate the problem of exactly reconstructing, with high confidence and up to isomorphism, the ball of radius r centered at the starting state of a Markov process from independent and anonymous experiments. In an anonymous experiment, the states are visited according to the underlying transition probabilities, but no global state names are known: one can only recognize whether two states, reached within the same experiment, are the same. We prove quite tight bounds for such exact reconstruction in terms of both the number of experiments and their lengths. (C) 2015 Elsevier B.V. All rights reserved.
暂无评论