Understanding Distributed Graph Algorithms & Spanners for Spring 2021
Explore concepts like Spanners, Shortest-Path Trees, and more in the context of distributed graph algorithms for Spring 2021. Dive into examples, known theorems, and constructions for creating efficient spanners in graphs.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Distributed Graph Algorithms Spring 2021 Spanners
Basic Example: Shortest-Path Trees Preserve distances w.r.t a fixed source node What if we want to preserve distances between all pairs? Stretch
Sch ?ffer Graph Spanners [Peleg, Graph Spanners [Peleg, Sch ffer 89] 89] Sparse subgraphs that preserve distances up to some bounded stretch ?(?)-spanner is a subgraph ? ? such that ???,? ? ???,? , ?,? ? ? = ??:multiplicative k-spanners ? ? = ? + ?: additive spanners ? ? = ? ? + ?: (?,?) spanners ???,? ? ???,? ???,? ???,? + ? Goal: optimize tradeoff between size and stretch
Examples 2-spanner for ??? ???,? ????,? , ?,? 2-spanner for general graph?
Whats Known? Multiplicative spanners: (2? 1) stretch: ?(?1+1/?) edges Additive spanners: +2 stretch: ?3/2edges +4 stretch: ?7/5edges +6 stretch: ?4/3edges +8 +100 ? Lower Bound: Any +??(1) spanner requires (n4/3) edges! Nearly additive spanners: (1 + ?,?) spanners ? = O log log nloglog ?, linear size
Multiplicative Spanners Theorem [Althofer et al. 93]: For any (possibly weighted) graph ? = (?,?)and integer ? ? there exists a (?? ?)spanner ? ?with ?(??+?/?)edges. Greedy Construction: Set ? Traverse edges in increasing weight order ? ?? < ? ?? < < ? ?? Add ??= (??,??)to ? if ???????,?? > ?? ? ?????(??,??)
Greedy Construction: Set ? Traverse edges in increasing weight order ? ?? < ? ?? < < ? ?? Add ??= (??,??)to ? if ???????,?? > ?? ? ?????(??,??) Correctness: Consider a ? ? shortest path P in ? ? ? ? ? ? 2? 1 ?(?) ??????,? (2? 1) ? ??(?)= 2? 1 ?????(?,?)
Greedy Construction: Set ? Traverse edges in increasing weight order ? ?? < ? ?? < < ? ?? Add ??= (??,??)to ? if ???????,?? > ?? ? ?????(??,??) Size analysis: show that ? = ?(?1+1/?) edges. Claim 1: the girth of H is at least 2k+1 Girth: length of shortest cycle Claim 2: Every graph G with g(G) 2? + 1 has ?(?1+1/?) edges.
Greedy Construction: Traverse edges in increasing weight order ? ?? < ? ?? < < ? ?? Add ??= (??,??)to ? if ???????,?? > ?? ? ?????(??,??) Claim 1: the girth of ? is at least 2k+1 Girth: length of shortest cycle Proof: Suppose there is a cycle ? of length at most ?? Let e = (?,?) be the last added edges on ? By the ordering: ? is the heaviest on ? ????? u,v ? ? ? The subgraph H just before adding e ? ? ? ? 2? 1 ?(?) Contradiction for adding ?!
Claim 2: Every graph G with g(G) 2? + 1 has ?(?1+1/?) edges. Proof: Assume ? has 4?1+1/?edges and g(G) 2? + 1 Compute ? ? with min-degree 2?1/? Note: ? ? 2? + 1
Claim 2: Every graph G with g(G) 2? + 1 has ?(?1+1/?) edges. Note: ? ? 2? + 1 Grow BFS of radius k around a fixed node ? in ? Claim: vertices in layer ? ? ? have no mutual neighbor in layer ? + ? ? 2?1/? ?1? 4?2/? ?2? 2???/? Layer ? ??? Cycle length 2? + 2 2? ??? > ? contradiction!
The Girth Conjecture Girth Conjecture: For every ? 1, there is an ?-vertex graph ?? with (?1+1 ?) edges that has girth* at least 2? + 2. ? ? Omitting a single edge ? = (?,?) from ?? increases the ? ? distance to 2? + 1 2? + 1 cycle The only (2k-1) spanner for ?? is ?? Status: GC resolved for ? = ?,?,?,? Lazebnik et al. 96: ?( ??+?/(??/? ?))
k=2, (?2) Girth=4
Baswana-Sen Algorithm for 3-Spanners Goal: 3-spanner with ? (?3/2) edges, here: unweighted. A vertex v is low-deg if ??? ? ? logn Step 1: Add to the spanner H all edges incident to low-deg vertices Step 2: Clustering Sample ? nodes ? ? denoted as centers Each high-deg node adds an edge to one neighboring centers Forms ? stars
Step 3: each high-deg vertex adds one edge to each neighboring star
3-Spanner Analysis Claim: each high-deg vertex has at least one sample neighbor in ? 5 ?logn 1 1 1 ?4 Pr ? ? ? = = (1 ?) 1 ? ? ?(?) Number of edges: 1. Low-deg:?(?3/2logn) 2. Stars: ?(?) 3. High-deg: ?(?3/2log n) [one edge per star] 2. Stretch (drawing)
Baswana-Sen Algorithm for (2k-1) Spanners Output:(?? ?) spanner ? with ? ???+?/? edges ?levels of clustering ?0= { {?1}, ,{??}}, ?1, ,??= Level-i clustering ??: ?? = ?1 ?/? ?
Phase i: Input: clustering ?? , subgraph ?? Level-i clustering ??: ?? = ?1 ?/? ? Step 1: Define clustering ??+? Each cluster center gets sampled independently w.p ? ?/? Each vertex joins an adjacent sampled cluster (if exists) ??+? = ?? (?+?)/?clusters of depth ? + 1
Phase i: Input: clustering ?? , subgraph ?? Level-i clustering ??: ?? = ?1 ?/? ? Step 2: Handle newly-unclustered vertices Each vertex adds one edge per neighboring cluster in ??
Final Phase k-1: Input: clustering ?? 1, subgraph ?? 1 Clustering ?? 1: ?? 1 = ?1/? ? 1 ?? Each vertex in ?? 1 adds (to ??) one edge per neighboring cluster in ?? 1 ? ??
Analysis (Stretch) Consider an edge ?,? ? W.l.o.g. assume ? stopped being clustered not after ?, say in step ? + 1 Show: ??????,? 2? + 1 Level-i clustering ??: ?? = ?1 ?/? ? ? ? Claim follows as all vertices stopped being cluster up to step ? 1
Analysis (Size) Show: each step ? adds ?(?1+1 ?log ?) edges Level-i clustering ??: ?? = ?1 ?/? ? ? ? w.h.p. a vertex has at most ?1/?log ? adjacent clusters
