2014/04/27 by Merav Parter, Parter, Merav · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Limits and Structures in Graph Theory #cs.DS
paper · pdf · doi:10.48550/arxiv.1404.6835
arxiv created 2014/04/27 · openalex publication_date 2014/04/27 · arxiv updated 2014/04/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(n1+1/k). This size-stretch bound is essentially optimal by the girth conjecture. 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 with m edges, there is a (polynomially constructible) k-hybrid spanner with O(k2 ⋅ n1+1/k) edges. \indent 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).