Low Stretch Spanning Trees and Probabilistic Tree Embedding
Explore the concepts of low-stretch spanning trees and probabilistic tree embedding from the class on Succinct Graph Structures and Their Applications in Spring 2020. Learn about optimizing problems on trees, probabilistic tree embedding theorems, and low diameter decomposition. Discover the applications in solving optimization problems efficiently.
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 Spring 2020 Class 6: Low Stretch Spanning Trees
Low Stretch Spanning Trees Goal: given graph ? = (?,?) compute tree ? ? such that ???,? ???,? ? ??(?,?) Q: What is the best ? one can hope for? Raz and Rabinovitch: ? = (?) Even if ? = (? ,? ) such that ? ? I.e., ? is not necessarily a subgraph of ?
Motivation Many optimization problems are simpler on trees Solve problem on low-stretch tree of ? to provide good approx. for ? Example: k-median problem, find ? ?, ? ? minimizing ? ???(?,?) NP-complete for general graphs, polynomial for trees (dyn. programming) ?-stretch spanning tree ? approx. for the problem Many other applications (solving fast system of linear equations)
Probabilistic Tree Embedding Given graph ?, a probability distribution ? over trees ? = {?1, ? } is an ?-probabilistic tree embedding if: ? ? ? ??for every ?? ? ???,? ????,? ??? ?????,? ? ??(?,?) Cycle graph?
Example: Cycle Graph ?:= Uniform distribution over all spanning trees 1/? 1/? Equivalent to sampling each edge with probability 1 1/? 1/? ? 1/? 1/? ?? ????,? =1 ? ? 1 +? 1 = 2 2 1/? ? ? 1/? 1/? 1/? 1/? For general graphs ? = (log?) [Alon, Karp, Peleg, West]
Probabilistic Tree Embedding Theorem [Bartal-95, FRT-03]: Every n-vertex graph ? = (?,?)has an ?-probabilistic tree embedding with ? = ?(log ?) There exists a randomized algorithm that computes a tree ? such that: ? ? ?(?) and ? ???,? = ?(????)???,? , ?,? Cor.: By sampling ?(log?) trees, w.h.p. dT(u,v) = ?(log?)dGu,v , ?,?
Probabilistic Tree Embedding Bartal, 95: ? = ?(log ? log ????) Fakcharoenphol, Rao, Talwar, 03: ? = ?(log ?) Key Tool: Low Diameter Decomposition Definitions: The weak-diameter of a subgraph ? ? is ????,? ? ??(?,?) The strong-diameter of a subgraph ? ? is ????,? ? ?? (?,?) ??????,? = { ? ? ???,? ? }
Low Diameter Decomposition (Ball Carving) Given a graph ? = (?,?) and parameter ?, a low-diameter-decomposition is a randomized partitioning ? = ?1 ?2 ? such that: weak diameter of ? ?? at most ? Pr[? ?? and ? ?? ?] ?(log ?/?) ??(?,?) ? ? ? ? Low-diam clusters with few inter-cluster edges ? ?
High Level Idea Grow carved balls around vertices where radius of each ball is taken from the geometric distribution with parameter ? = 4log?/? ? ???? ?counting number of trials till first success Pr ? = ? = 1 ?? 1 ? Memory-less property: Pr[? ? + ? ] = Pr[? ?] ? ?? ? ? ?? ??
Low Diameter Decomposition Alg. LDD(G ,G,D) Set ? 1 and unmark all vertices in ? ? While there are unmarked vertices in ? do: ?? ? ? Pick an unmarked vertex ? ? Sample ?? ???(?) for ? = min{ 1,4log?/?} Add all unmarked vertices of ? in ?????(?,??) to ?? ? ? + 1 ?? ??
Low Diameter Decomposition Claim 1: weak diameter of ? ?? at most ? Pf: Show that Rv D/2 w.h.p Pr ?? ? = 1 ??/2= ? ??/2= ? 4 log ??/(2?)= 1/?2 2 The claim holds for every ? with probability 1 1/?
Low Diameter Decomposition Claim 2: Pr[? ?? and ? ?? ?] ? ??(?,?) Sampling from ???(?) flipping a coin with probability ? and counting #flips until first head Assume that ? ?? (centered at ?) Pr[? ?? and ? ?? ?] = Pr[?? [???,? ,???,? )] ? ? ? ???,? dGw,v ? ??(?,?) ??(?,?) ?
Low Diameter Decomposition Alg. LDD(G ,G,D) Set ? 1 and unmark all vertices in ? While there are unmarked vertices in ? do: ? Pick an unmarked vertex ? ? Sample ?? ???(?) for ? = min{ 1,4log?/?} Add all unmarked vertices of ? in ?????(?,??) to ?? ? ? + 1 ?? ? ? ?? ?? Diam of each ?[??] 1/?, separation probability ? ??(?,?)
Tree Embedding given LDD ?0 Recursive application of LDD algorithm ? ? LDD on ? with D/2 where ? = ????(?) ? ?[?3] ?[?1] ?[?2] ?/2 Form a weighted tree of depth log???? Leaf nodes are vertices of ? ?/2 ?/2 ?[?1,1] ?[?1,2]
Probabilistic Tree Embedding ?0 Alg. TE(G ,G,D) If ? ? = { ?}, return ? ? ? ? ?[?3] ?[?1] ?[?2] ?1, ,?? = ???(? ,?,? 2) ?? ?? ? ??,?,? ?0 2 for every ? 1, ,? ? ? ? ?1 ??= ?0,? ?? ?3 ,? ?? = ? ?2 ? 2 ? 2 ? 2 ? 2 ? ??? {??,? {1, ,?}}
Probabilistic Tree Embedding ?0 ? ? ? ?/2 ?/2 log? ?/2? 1 ? ?/2? 1
Probabilistic Tree Embedding Claim 1: ???,? ??(?,?) w.h.p. Pf. ? and ? are separated in level ? 1. The diam of level-?components ?/2? 1thus???,? ?/2? 1 Level-?components are connected to their children with weight ?/2? 1 ???,? ??/?? ?
Probabilistic Tree Embedding Claim 2: If ? and ? are separated in level ? 1, then ???,? ??/?? ? The path from root to leaf is of length ? +? ?+ + ? ?? ? ? ?? ?+ + ? ??/?? ? Path from level i node to leaf of length ?? ?+ ?0 ? ? ? ?/2 ?/2
Probabilistic Tree Embedding Claim 3: ?(???,? ) = ? log ? log ???? ???,? ??=: indicator for the event that ? and ? are separated in level-? ?(???,? ) = Pr ?1 4? + Pr ?2 ?1 2? + + ?1 ?2 ?? 1] 4?/2? 1+ +Pr[?? ?1 ?2 ?? 1] 4?/2? 1 , ? = log???? +Pr[??
Probabilistic Tree Embedding 2?log ? ? ?1 ?2 ?? 1] = ? Claim 4: Pr[?? ??(?,?) ?,? are in the same level-? component ?? with diam ?/2? 1 By the property of the LDD on ??, the probability that ? and ? are sep. 2?log ? ? is at most ? ??(?,?)
Probabilistic Tree Embedding Claim 3: ?(???,? ) = ? log ? log ???? ???,? ??=: indicator for the event that ? and ? are separated in level-? ?(???,? ) = Pr ?1 4? + Pr ?2 ?1 2? + + ?1 ?2 ?? 1] 4?/2? 1+ +Pr[?? 4? 2? 1 ?1 ?2 ?? 1] +Pr[?? = log ???? ?(log ?)??(?,?) 2?log ? ? ? ??(?,?)
Alternative LDD [CKR01] Components of weak diam? log ? ? 2 and separation probability ? ??(?,?) Pick a radius ? [? ?,? ?] Random permutation ? of all vertices The ? ? graph ??= ???? ? ? ,? ? ? ?????(? ? ,?) Weak diam 2?/4 Sep. probability: ? and ? at distance ? in ?. What s the probability that ????(?,?) is cut (i.e., not fully assigned to same comp.)
Alternative LDD [CKR01]: Cutting Probability ?(?,?) is cut then must exist ? ? such that ? ? = ? satisfying that: a) ?? ??????,? = for every ? ? 1 b) ?? ??????,? and ??????,? ?? Let ?1,?2, ,?? be sorted in non-decreasing distance from ? Pr ??????,? is cut = ?Pr[?????(?,?)is cut by ??] ?????(?,?) Two events must hold to be cut by ??: ? (? ??,? ?,? ??,? + ?) ? ?? is the first in ? ??
Alternative LDD [CKR01]: Cutting Probability Pr ??????,? is cut = Pr[?????(?,?)is cut by ??] ?????(?,?) ? 2? ?/8 1 ? ?= ?(ln?/?))? ? Two events must hold to be cut by ??: ?? ? (? ??,? ?,? ??,? + ?) ?? is the first in ?
Improved Analysis 2? ?/8 1 Pr ??????,? is cut = ?Pr[?????(?,?)is cut by ??] ? ?= ?(ln?/?))? Observation: sufficient to sum over ?? satisfying that ? ? ? ??,? ? + ? Assume w.l.o.g ? 16 Susbet of vertices ?? ? such that ? ??,? [? ? ??,? ?] |???? ?,? ???? ?,? 2| Pr ??????,? is cut =16? 1/? =16? 2 ln ???? ?,? ? ? ?=|???? ?,? 16 16| ??
Improved Stretch of Probabilistic Tree Embedding Claim 3: ?(???,? ) = ? log ? log ???? ???,? ??=: indicator for the event that ? and ? are separated in level-? ?(???,? ) = Pr ?1 4? + Pr ?2 ?1 2? + + ?1 ?2 ?? 1] 4?/2? 1+ +Pr[?? ?1 ?2 ?? 1] 4?/2? 1 , ? = log???? +Pr[?? ?4?/2? 1 16???,? 4?/2? 1
Probabilistic Tree Embedding Improved Claim 3: ?(???,? ) = ? log ? ???,? ?(???,? ) = 4 ???,? ??+ ?? + + ?1 12 ln ? ??(?,?) 2
