Premium
Constructing near spanning trees with few local inspections
Author(s) -
Levi Reut,
Moshkovitz Guy,
Ron Dana,
Rubinfeld Ronitt,
Shapira Asaf
Publication year - 2017
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20652
Subject(s) - combinatorics , spanning tree , mathematics , kruskal's algorithm , graph factorization , minimum degree spanning tree , vertex (graph theory) , minimum spanning tree , induced subgraph isomorphism problem , discrete mathematics , bounded function , vertex connectivity , graph , induced subgraph , distance hereditary graph , line graph , graph power , voltage graph , mathematical analysis
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 + ϵ ) n edges (for a prespecified constant ϵ > 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 / ( log t ) 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 / ( log t ) 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. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 183–200, 2017