Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. We consider a relaxed version of this problem in the setting of local algorithms. The relaxation is that the constructed subgraph is a sparse spanning subgraph containing at most (1+ϵ)n edges (where n is the number of vertices and ϵ is a given approximation/sparsity parameter). In the local setting, the goal is to quickly determine whether a given edge e belongs to such a subgraph, without constructing the whole subgraph, but rather by inspecting (querying) the local neighborhood of e. The challenge is to maintain consistency. That is, to provide answers concerning different edges according to the same spanning subgraph. We first show that for general boundeddegree graphs, the query complexity of any such algorithm must be Ω(n−−√). This lower bound holds for constantdegree graphs that have high expansion. Next we design an algorithm for (boundeddegree) graphs with high expansion, obtaining a result that roughly matches the lower bound. We then turn to study graphs that exclude a fixed minor (and are hence nonexpanding). We design an algorithm for such graphs, which may have an unbounded maximum degree. The query complexity of this algorithm is poly(1/ϵ,h) (independent of n and the maximum degree), where h is the number of vertices in the excluded minor. Though our two algorithms are designed for very different types of graphs (and have very different complexities), on a highlevel there are several similarities, and we highlight both the similarities and the differences.
more »
« less
Constructing near spanning trees with few local inspections
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 boundeddegree graph. Given an edge e in G we would like to decide whether e belongs to a connected subgraph math formula consisting of math formula edges (for a prespecified constant math formula), where the decision for different edges should be consistent with the same subgraph math formula. Can this task be performed by inspecting only a constant number of edges in G? Our main results are:
We show that if every tvertex subgraph of G has expansion math formula then one can (deterministically) construct a sparse spanning subgraph math formula of G using few inspections. To this end we analyze a “local” version of a famous minimumweight spanning tree algorithm.
We show that the above expansion requirement is sharp even when allowing randomization. To this end we construct a family of 3regular graphs of high girth, in which every tvertex subgraph has expansion math formula. 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.
more »
« less
 Award ID(s):
 1650733
 NSFPAR ID:
 10026350
 Date Published:
 Journal Name:
 Random structures & algorithms
 Volume:
 50
 Issue:
 2
 ISSN:
 10982418
 Page Range / eLocation ID:
 183200
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


A graph spanner is a fundamental graph structure that faithfully preserves the pairwise distances in the input graph up to a small multiplicative stretch. The common objective in the computation of spanners is to achieve the bestknown existential sizestretch tradeoff efficiently. Classical models and algorithmic analysis of graph spanners essentially assume that the algorithm can read the input graph, construct the desired spanner, and write the answer to the output tape. However, when considering massive graphs containing millions or even billions of nodes not only the input graph, but also the output spanner might be too large for a single processor to store. To tackle this challenge, we initiate the study of local computation algorithms (LCAs) for graph spanners in general graphs, where the algorithm should locally decide whether a given edge (u,v)∈E belongs to the output spanner. Such LCAs give the user the `illusion' that a specific sparse spanner for the graph is maintained, without ever fully computing it. We present the following results: For general nvertex graphs and r∈{2,3}, there exists an LCA for (2r−1)spanners with O˜(n1+1/r) edges and sublinear probe complexity of O˜(n1−1/2r). These size/stretch tradeoffs are best possible (up to polylogarithmic factors). For every k≥1 and nvertex graph with maximum degree Δ, there exists an LCA for O(k2) spanners with O˜(n1+1/k) edges, probe complexity of O˜(Δ4n2/3), and random seed of size polylog(n). This improves upon, and extends the work of [LenzenLevi, 2018]. We also complement our results by providing a polynomial lower bound on the probe complexity of LCAs for graph spanners that holds even for the simpler task of computing a sparse connected subgraph with o(m) edges.more » « less

Given a directed acyclic graph (DAG) G=(V,E), we say that G is (e,d)depthrobust (resp. (e,d)edgedepthrobust) if for any set S⊆V (resp. S⊆E) of at most S≤e nodes (resp. edges) the graph G−S contains a directed path of length d. While edgedepthrobust graphs are potentially easier to construct, many applications in cryptography require node depthrobust graphs with small indegree. We create a graph reduction that transforms an (e,d)edgedepthrobust graph with m edges into a (e/2,d)depthrobust graph with O(m) nodes and constant indegree. One immediate consequence of this result is the first construction of a provably (nloglognlogn,nlogn(logn)loglogn)depthrobust graph with constant indegree. Our reduction crucially relies on STrobust graphs, a new graph property we introduce which may be of independent interest. We say that a directed, acyclic graph with n inputs and n outputs is (k1,k2)STrobust if we can remove any k1 nodes and there exists a subgraph containing at least k2 inputs and k2 outputs such that each of the k2 inputs is connected to all of the k2 outputs. If the graph if (k1,n−k1)STrobust for all k1≤n we say that the graph is maximally STrobust. We show how to construct maximally STrobust graphs with constant indegree and O(n) nodes. Given a family M of STrobust graphs and an arbitrary (e,d)edgedepthrobust graph G we construct a new constantindegree graph Reduce(G,M) by replacing each node in G with an STrobust graph from M. We also show that STrobust graphs can be used to construct (tight) proofsofspace and (asymptotically) improved wideblock labeling functions.more » « less

null (Ed.)We consider nodeweighted survivable network design (SNDP) in planar graphs and minorclosed families of graphs. The input consists of a nodeweighted undirected graph G = ( V , E ) and integer connectivity requirements r ( uv ) for each unordered pair of nodes uv . The goal is to find a minimum weighted subgraph H of G such that H contains r ( uv ) disjoint paths between u and v for each node pair uv . Three versions of the problem are edgeconnectivity SNDP (ECSNDP), elementconnectivity SNDP (ElemSNDP), and vertexconnectivity SNDP (VCSNDP), depending on whether the paths are required to be edge, element, or vertex disjoint, respectively. Our main result is an O ( k )approximation algorithm for ECSNDP and ElemSNDP when the input graph is planar or more generally if it belongs to a proper minorclosed family of graphs; here, k = max uv r ( uv ) is the maximum connectivity requirement. This improves upon the O ( k log n )approximation known for nodeweighted ECSNDP and ElemSNDP in general graphs [31]. We also obtain an O (1) approximation for nodeweighted VCSNDP when the connectivity requirements are in {0, 1, 2}; for higher connectivity our result for ElemSNDP can be used in a blackbox fashion to obtain a logarithmic factor improvement over currently known general graph results. Our results are inspired by, and generalize, the work of Demaine, Hajiaghayi, and Klein [13], who obtained constant factor approximations for nodeweighted Steiner tree and Steiner forest problems in planar graphs and proper minorclosed families of graphs via a primaldual algorithm.more » « less

We present a weighted approach to compute a maximum cardinality matching in an arbitrary bipartite graph. Our main result is a new algorithm that takes as input a weighted bipartite graph G(A cup B,E) with edge weights of 0 or 1. Let w <= n be an upper bound on the weight of any matching in G. Consider the subgraph induced by all the edges of G with a weight 0. Suppose every connected component in this subgraph has O(r) vertices and O(mr/n) edges. We present an algorithm to compute a maximum cardinality matching in G in O~(m(sqrt{w} + sqrt{r} + wr/n)) time. When all the edge weights are 1 (symmetrically when all weights are 0), our algorithm will be identical to the wellknown HopcroftKarp (HK) algorithm, which runs in O(m sqrt{n}) time. However, if we can carefully assign weights of 0 and 1 on its edges such that both w and r are sublinear in n and wr=O(n^{gamma}) for gamma < 3/2, then we can compute maximum cardinality matching in G in o(m sqrt{n}) time. Using our algorithm, we obtain a new O~(n^{4/3}/epsilon^4) time algorithm to compute an epsilonapproximate bottleneck matching of A,B subsetR^2 and an 1/(epsilon^{O(d)}}n^{1+(d1)/(2d1)}) poly log n time algorithm for computing epsilonapproximate bottleneck matching in ddimensions. All previous algorithms take Omega(n^{3/2}) time. Given any graph G(A cup B,E) that has an easily computable balanced vertex separator for every subgraph G'(V',E') of size V'^{delta}, for delta in [1/2,1), we can apply our algorithm to compute a maximum matching in O~(mn^{delta/1+delta}) time improving upon the O(m sqrt{n}) time taken by the HKAlgorithm.more » « less