Spanners in Graph Structures: Applications and Examples for Network Optimization
Explore the concept of graph spanners in succinct graph structures and their applications, such as fault tolerance, distances, and routing tables. The focus is on optimizing the tradeoff between subgraph size and stretch while preserving distances in dense real-world networks. Learn about multiplicative and additive spanners, construction methods, and known theorems in graph theory.
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
Succinct Graph Structures and Their Applications Ulpana Summer 2024 Class 1: Spanners
Overview Real day networks are very dense (e.g., Facebook, internet..) Sketch the graph while keeping key properties Fault Tolerance Distances Subgraphs Routing Tables Cuts Data- Structure Labels
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
Graph Spanners [Peleg, Sch Graph Spanners [Peleg, Sch ?ffer 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 ( ? = polylog, 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 ? 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
