The significant progress in constructing graph spanners that are sparse (small number of edges) or light (low total weight) has skipped spanners that are everywhere-sparse (small maximum degree). This disparity is in line with other network design problems, where the maximum-degree objective has been a notorious technical challenge. Our main result is for the Lowest Degree 2-Spanner (LD2S) problem, where the goal is to compute a 2-spanner of an input graph so as to minimize the maximum degree. We design a polynomial-time algorithm achieving approximation factor @math , where @math is the maximum degree of the input graph. The previous @math -approximation was proved nearly two decades ago by Kortsarz and Peleg [SODA 1994, SICOMP 1998]. Our main conceptual contribution is to establish a formal connection between LD2S and a variant of the Densest k-Subgraph (DkS) problem. Specifically, we design for both problems strong relaxations based on the Sherali-Adams linear programming (LP) hierarchy, and show that "faithful" randomized rounding of the DkS-variant can be used to round LD2S solutions. Our notion of faithfulness intuitively means that all vertices and edges are chosen with probability proportional to their LP value, but the precise formulation is more subtle. Unfortunately, the best algorithms known for DkS use the Lov 'asz-Schrijver LP hierarchy in a non-faithful way [Bhaskara, Charikar, Chlamtac, Feige, and Vijayaraghavan, STOC 2010]. Our main technical contribution is to overcome this shortcoming, while still matching the gap that arises in random graphs by planting a subgraph with same log-density.
Graph spanners, first introduced by Peleg and Sch "a ffer @cite_2 and Peleg and Ullman @cite_23 , have been studied extensively, with applications ranging from routing in networks (e.g. @cite_41 @cite_10 ) to solving linear systems (e.g. @cite_13 @cite_15 ). The foundational result on spanners is due to Alth "ofer, Das, Dobkin, Joseph and Soares @cite_30 , who gave an algorithm that, given a graph and an integer @math , constructs a @math -spanner with @math edges. Unfortunately this result obviously does not give anything nontrivial for @math -spanners, and indeed it is easy to see that there exist graphs for which every @math -spanner has @math edges, thus nontrivial absolute bounds on the size of a @math -spanner are not possible. Kortsarz and Peleg @cite_38 were the first to consider relative bounds for spanners. They gave a greedy @math -approximation algorithm for the problem of finding a @math -spanner with the minimum number of edges. This was then extended to variants of @math -spanners, e.g. @cite_20 and @cite_42 @cite_26 (for which only @math is known). All of these bounds are basically optimal, assuming @math , due to a hardness result of Kortsarz @cite_39 .
@cite_13 @cite_30 @cite_38 @cite_26 @cite_41 @cite_42 @cite_39 @cite_23 @cite_2 @cite_15 @cite_10 @cite_20
2045107949 2002041206 2057046770 2952422587 1996879666 1997369416 2018963243 2045446569 1534368076
We present algorithms for solving symmetric, diagonally-dominant linear systems to accuracy e in time linear in their number of non-zeros and log (κ f (A) e), where κ f (A) is the condition number of the matrix defining the linear system. Our algorithm applies the preconditioned Chebyshev iteration with preconditioners designed using nearly-linear time algorithms for graph sparsification and graph partitioning. Given a graphG, a subgraphG' is at-spanner ofG if, for everyu,v ?V, the distance fromu tov inG' is at mostt times longer than the distance inG. In this paper we give a simple algorithm for constructing sparse spanners for arbitrary weighted graphs. We then apply this algorithm to obtain specific results for planar graphs and Euclidean graphs. We discuss the optimality of our results and present several nearly matching lower bounds. A k-spanner of a connected graph G = (V, E) is a subgraph G? consisting of all the vertices of V and a subset of the edges, with the additional property that the distance between any two vertices in G? is larger than that distance in G by no more than a factor of k. This note concerns the problem of finding the sparsest 2-spanner in a given graph and presents an approximation algorithm for this problem with approximation ratio log(|E| |V|) A natural requirement of many distributed structures is fault-tolerance: after some failures, whatever remains from the structure should still be effective for whatever remains from the network. In this paper we examine spanners of general graphs that are tolerant to vertex failures, and significantly improve their dependence on the number of faults @math , for all stretch bounds. For stretch @math we design a simple transformation that converts every @math -spanner construction with at most @math edges into an @math -fault-tolerant @math -spanner construction with at most @math edges. Applying this to standard greedy spanner constructions gives @math -fault tolerant @math -spanners with @math edges. The previous construction by Chechik, Langberg, Peleg, and Roddity [STOC 2009] depends similarly on @math but exponentially on @math (approximately like @math ). For the case @math and unit-length edges, an @math -approximation algorithm is known from recent work of Dinitz and Krauthgamer [arXiv 2010], where several spanner results are obtained using a common approach of rounding a natural flow-based linear programming relaxation. Here we use a different (stronger) LP relaxation and improve the approximation ratio to @math , which is, notably, independent of the number of faults @math . We further strengthen this bound in terms of the maximum degree by using the Local Lemma. Finally, we show that most of our constructions are inherently local by designing equivalent distributed algorithms in the LOCAL model of distributed computation. This paper deals with the problem of maintaining a distributed directory server, that enables us to keep track of mobile users in a distributed network. The paper introduces the graph-theoretic concept of regional matching , and demonstrates how finding a regional matching with certain parameters enables efficient tracking. The communication overhead of our tracking mechanism is within a polylogarithmic factor of the lower bound. A k -spanner of a connected graph G=(V,E) is a subgraph G' consisting of all the vertices of V and a subset of the edges, with the additional property that the distance between any two vertices in G' is larger than the distance in G by no more than a factor of k . This paper concerns the hardness of finding spanners with a number of edges close to the optimum. It is proved that for every fixed k , approximating the spanner problem is at least as hard as approximating the set-cover problem. The synchronizer is a simulation methodology introduced by Awerbuch [J. Assoc. Comput. Math., 32 (1985), pp. 804–823] for simulating a synchronous network by an asynchronous one, thus enabling the execution of a synchronous algorithm on an asynchronous network. In this paper a novel technique for constructing network synchronizers is presented. This technique is developed from some basic relationships between synchronizers and the structure of a t-spanning subgraph over the network. As a special result, a synchronizer for the hypercube with optimal time and communication complexities is obtained. Let G = (V,E) be an undirected weighted graph with vVv = n and vEv = m. Let k ≥ 1 be an integer. We show that G = (V,E) can be preprocessed in O(kmn1 k) expected time, constructing a data structure of size O(kn1p1 k), such that any subsequent distance query can be answered, approximately, in O(k) time. The approximate distance returned is of stretch at most 2k−1, that is, the quotient obtained by dividing the estimated distance by the actual distance lies between 1 and 2k−1. A 1963 girth conjecture of Erdos, implies that Ω(n1p1 k) space is needed in the worst case for any real stretch strictly smaller than 2kp1. The space requirement of our algorithm is, therefore, essentially optimal. The most impressive feature of our data structure is its constant query time, hence the name "oracle". Previously, data structures that used only O(n1p1 k) space had a query time of Ω(n1 k).Our algorithms are extremely simple and easy to implement efficiently. They also provide faster constructions of sparse spanners of weighted graphs, and improved tree covers and distance labelings of weighted or unweighted graphs. This paper studies the client-server version of the 2-spanner problem. This is a natural generalization of the sparse 2-spanner problem that turns out to be useful for certain network design problems. The paper presents a logarithmic ratio approximation algorithm for this problem. The algorithm and the analysis are extended to the directed client-server 2-spanner problem and to the client-server augmentation 2-spanner problem, establishing a logarithmic approximation ratio for these problems too. The paper also studies the bounded-diameter network design (BDND) problem, and establishes a logarithmic approximation ratio for the problem, using the tools developed for the client-server 2-spanner problem.