Abstract
An (α,β)-spanner of an n-vertex graph G = (V,E) is a subgraph H of G satisfying that dist(u, v, H) ≤ α·dist(u, v, G) + β for every pair (u, v) ∈ V ×V, where dist(u,v,G′) denotes the distance between u and v in G′ ⊆ G. It is known that for every integer k ≥ 1, every graph G has a polynomially constructible (2k − 1,0)-spanner of size O(n 1 + 1/k). This size-stretch bound is essentially optimal by the girth conjecture. Yet, it is important to note that any argument based on the girth only applies to adjacent vertices. It is therefore intriguing to ask if one can “bypass” the conjecture by settling for a multiplicative stretch of 2k − 1 only for neighboring vertex pairs, while maintaining a strictly better multiplicative stretch for the rest of the pairs. We answer this question in the affirmative and introduce the notion of k-hybrid spanners, in which non neighboring vertex pairs enjoy a multiplicative k stretch and the neighboring vertex pairs enjoy a multiplicative (2k − 1) stretch (hence, tight by the conjecture). We show that for every unweighted n-vertex graph G, there is a (polynomially constructible) k-hybrid spanner with O(k 2 ·n 1 + 1/k) edges. This should be compared against the current best (α,β) spanner construction of [5] that obtains (k,k − 1) stretch with O(k ·n 1 + 1/k) edges. An alternative natural approach to bypass the girth conjecture is to allow ourself to take care only of a subset of pairs S ×V for a given subset of vertices S ⊆ V referred to here as sources. Spanners in which the distances in S ×V are bounded are referred to as sourcewise spanners. Several constructions for this variant are provided (e.g., multiplicative sourcewise spanners, additive sourcewise spanners and more).
Recipient of the Google European Fellowship in distributed computing; research supported in part by this Fellowship. Supported in part by the Israel Science Foundation (grant 894/09), United States-Israel Binational Science Foundation (grant 2008348), Israel Ministry of Science and Technology (infrastructures grant), and Citi Foundation.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Agarwal, R., Godfrey, P.B., Har-Peled, S.: Approximate distance queries and compact routing in sparse graphs. In: Proc. INFOCOM (2011)
Aingworth, D., Chekuri, C., Indyk, P., Motwani, R.: Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput. 28(4), 1167–1181 (1999)
Alon, N., Spencer, J.H.: The probabilistic method. Wiley, Chichester (1992)
Althöfer, I., Das, G., Dobkin, D., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Networks 9(1), 81–100 (1993)
Baswana, S., Kavitha, T., Mehlhorn, K., Pettie, S.: Additive spanners and (α, β)-spanners. ACM Trans. Algo. 7, A.5 (2010)
Baswana, S., Sen, S.: A simple Linear Time Randomized Algorithm for Computing Sparse Spanners in Weighted Graphs. Random Structures and Algorithms 30(4), 532–563 (2007)
Baswana, S., Kavitha, T.: Faster algorithms for approximate distance oracles and all-pairs small stretch paths. In: Proc. FOCS, pp. 591–602 (2006)
Baswana, S., Sen, S.: Approximate distance oracles for unweighted graphs in expected O (n 2) time. ACM Transactions on Algorithms (TALG) 2(4), 557–577 (2006)
Bollobás, B., Coppersmith, D., Elkin, M.: Sparse distance preservers and additive spanners. SIAM Journal on Discrete Mathematics 19(4), 1029–1055 (2005)
Coppersmith, D., Elkin, M.: Sparse sourcewise and pairwise distance preservers. SIAM Journal on Discrete Mathematics 20(2), 463–501 (2006)
Chechik, S.: New Additive Spanners. In: Proc. SODA, vol. 29(5), pp. 498–512 (2013)
Cygan, M., Grandoni, F., Kavitha, T.: On Pairwise Spanners. In: Proc. STACS, pp. 209–220 (2013)
Gavoille, C., Peleg, D.: Compact and localized distributed data structures. Distributed Computing 16(2), 111–120 (2003)
Dor, D., Halperin, S., Zwick, U.: All-pairs almost shortest paths. SIAM on Computing 29(5), 1740–1759 (2000)
Elkin, M., Peleg, D.: (1 + ε, β)-Spanner Constructions for General Graphs. SIAM Journal on Computing 33(3), 608–631 (2004)
Elkin, M.: Computing almost shortest paths. ACM Transactions on Algorithms (TALG) 1(2), 283–323 (2005)
Elkin, M., Emek, Y., Spielman, D.A., Teng, S.H.: Lower stretch spanning trees. In: Proc. STOC, pp. 494–503 (2005)
Erdős, P.: Extremal problems in graph theory. In: Proc. Symp. Theory of Graphs and its Applications, pp. 29–36 (1963)
Kapralov, M., Panigrahy, R.: Spectral sparsification via random spanners. In: ITCS (2012)
Kavitha, T., Varma, N.M.: Small Stretch Pairwise Spanners. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol. 7965, pp. 601–612. Springer, Heidelberg (2013)
Liestman, A.L., Shermer, T.C.: Additive graph spanners. Networks 23(4), 343–363 (1993)
Mendel, M., Naor, A.: Ramsey partitions and proximity data structures. In: FOCS, vol. 23(4), pp. 109–118 (2006)
Parter, M.: Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners (2014), http://arxiv.org/abs/1404.6835
Pǎtraşcu, M., Roditty, L.: Distance oracles beyond the Thorup-Zwick bound. In: FOCS, pp. 815–823 (2010)
Peleg, D., Schaffer, A.A.: Graph spanners. Journal of Graph Theory 12(1), 99–116 (1989)
Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. SIAM Journal on Computing 18(4), 740–747 (1989)
Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM (2000)
Pettie, S.: Low distortion spanners. ACM Transactions on Algorithms (TALG) 6(1) (2009)
Roditty, L., Thorup, M., Zwick, U.: Deterministic constructions of approximate distance oracles and spanners. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 261–272. Springer, Heidelberg (2005)
Thorup, M.: Undirected single-source shortest paths with positive integer weights in linear time. Journal of the ACM (JACM) 46(3), 362–394 (1999)
Thorup, M., Zwick, U.: Approximate distance oracles. Journal of the ACM (JACM) 52(1), 1–24 (2005)
Thorup, M., Zwick, U.: Spanners and emulators with sublinear distance errors. In: SODA, pp. 802–809 (2006)
Wenger, R.: Extremal graphs with no C4’s, C6’s, or C10’s. Journal of Combinatorial Theory, 113–116 (1991)
Woodruff, D.P.: Lower bounds for additive spanners, emulators, and more. In: Proc. 47th Symp. on Foundations of Computer Science, pp. 389–398 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Parter, M. (2014). Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds) Automata, Languages, and Programming. ICALP 2014. Lecture Notes in Computer Science, vol 8573. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-43951-7_49
Download citation
DOI: https://doi.org/10.1007/978-3-662-43951-7_49
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-43950-0
Online ISBN: 978-3-662-43951-7
eBook Packages: Computer ScienceComputer Science (R0)