A Local Algorithm for Constructing Spanners in Minor-Free Graphs
Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. We consider this problem in the setting of local algorithms: one wants to quickly determine whether a given edge e is in a specific spanning tree, without computing the whole spanning tree, but rather by inspecti...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Dagstuhl Publishing
2017
|
| Online Access: | http://hdl.handle.net/1721.1/111969 https://orcid.org/0000-0002-4353-7639 |
| _version_ | 1811093122162098176 |
|---|---|
| author | Levi, Reut Ron, Dana Rubinfeld, Ronitt |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Levi, Reut Ron, Dana Rubinfeld, Ronitt |
| author_sort | Levi, Reut |
| collection | MIT |
| description | Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. We consider this problem in the setting of local algorithms: one wants to quickly determine whether a given edge e is in a specific spanning tree, without computing the whole spanning tree, but rather by inspecting the local neighborhood of e. The challenge is to maintain consistency. That is, to answer queries about different edges according to the same spanning tree. Since it is known that this problem cannot be solved without essentially viewing all the graph, we consider the relaxed version of finding a spanning subgraph with (1+c)n edges instead of n-1 edges (where n is the number of vertices and c is a given approximation/sparsity parameter). It is known that this relaxed problem requires inspecting order of n^{1/2} edges in general graphs (for any constant c), which motivates the study of natural restricted families of graphs. One such family is the family of graphs with an excluded minor (which in particular includes planar graphs). For this family there is an algorithm that achieves constant success probability, and inspects (d/c)^{poly(h)log(1/c)} edges (for each edge it is queried on), where d is the maximum degree in the graph and h is the size of the excluded minor. The distances between pairs of vertices in the spanning subgraph G' are at most a factor of poly(d, 1/c, h) larger than in G. In this work, we show that for an input graph that is H-minor free for any H of size h, this task can be performed by inspecting only poly(d, 1/c, h) edges in G. The distances between pairs of vertices in the spanning subgraph G' are at most a factor of h log(d)/c (up to poly-logarithmic factors) larger than in G. Furthermore, the error probability of the new algorithm is significantly improved to order of 1/n. This algorithm can also be easily adapted to yield an efficient algorithm for the distributed (message passing) setting. |
| first_indexed | 2024-09-23T15:40:03Z |
| format | Article |
| id | mit-1721.1/111969 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:40:03Z |
| publishDate | 2017 |
| publisher | Dagstuhl Publishing |
| record_format | dspace |
| spelling | mit-1721.1/1119692022-10-02T03:19:15Z A Local Algorithm for Constructing Spanners in Minor-Free Graphs Levi, Reut Ron, Dana Rubinfeld, Ronitt Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Rubinfeld, Ronitt Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. We consider this problem in the setting of local algorithms: one wants to quickly determine whether a given edge e is in a specific spanning tree, without computing the whole spanning tree, but rather by inspecting the local neighborhood of e. The challenge is to maintain consistency. That is, to answer queries about different edges according to the same spanning tree. Since it is known that this problem cannot be solved without essentially viewing all the graph, we consider the relaxed version of finding a spanning subgraph with (1+c)n edges instead of n-1 edges (where n is the number of vertices and c is a given approximation/sparsity parameter). It is known that this relaxed problem requires inspecting order of n^{1/2} edges in general graphs (for any constant c), which motivates the study of natural restricted families of graphs. One such family is the family of graphs with an excluded minor (which in particular includes planar graphs). For this family there is an algorithm that achieves constant success probability, and inspects (d/c)^{poly(h)log(1/c)} edges (for each edge it is queried on), where d is the maximum degree in the graph and h is the size of the excluded minor. The distances between pairs of vertices in the spanning subgraph G' are at most a factor of poly(d, 1/c, h) larger than in G. In this work, we show that for an input graph that is H-minor free for any H of size h, this task can be performed by inspecting only poly(d, 1/c, h) edges in G. The distances between pairs of vertices in the spanning subgraph G' are at most a factor of h log(d)/c (up to poly-logarithmic factors) larger than in G. Furthermore, the error probability of the new algorithm is significantly improved to order of 1/n. This algorithm can also be easily adapted to yield an efficient algorithm for the distributed (message passing) setting. 2017-10-24T18:21:47Z 2017-10-24T18:21:47Z 2016-09 Article http://purl.org/eprint/type/ConferencePaper 978-3-95977-018-7 1868-8969 http://hdl.handle.net/1721.1/111969 Levi, Reut et al. "A Local Algorithm for Constructing Spanners in Minor-Free Graphs" Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016), September 7-9 2016, Paris, France, edited by Klaus Jansen et al., Dagstuhl Publishing, September 2016 © Reut Levi, Dana Ron, and Ronitt Rubinfeld https://orcid.org/0000-0002-4353-7639 en_US http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.38 Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016) Creative Commons Attribution 4.0 International License http://creativecommons.org/licenses/by/4.0/ application/pdf Dagstuhl Publishing Dagstuhl Publishing |
| spellingShingle | Levi, Reut Ron, Dana Rubinfeld, Ronitt A Local Algorithm for Constructing Spanners in Minor-Free Graphs |
| title | A Local Algorithm for Constructing Spanners in Minor-Free Graphs |
| title_full | A Local Algorithm for Constructing Spanners in Minor-Free Graphs |
| title_fullStr | A Local Algorithm for Constructing Spanners in Minor-Free Graphs |
| title_full_unstemmed | A Local Algorithm for Constructing Spanners in Minor-Free Graphs |
| title_short | A Local Algorithm for Constructing Spanners in Minor-Free Graphs |
| title_sort | local algorithm for constructing spanners in minor free graphs |
| url | http://hdl.handle.net/1721.1/111969 https://orcid.org/0000-0002-4353-7639 |
| work_keys_str_mv | AT levireut alocalalgorithmforconstructingspannersinminorfreegraphs AT rondana alocalalgorithmforconstructingspannersinminorfreegraphs AT rubinfeldronitt alocalalgorithmforconstructingspannersinminorfreegraphs AT levireut localalgorithmforconstructingspannersinminorfreegraphs AT rondana localalgorithmforconstructingspannersinminorfreegraphs AT rubinfeldronitt localalgorithmforconstructingspannersinminorfreegraphs |