Explore the world of additive spanners in graph structures with state-of-the-art techniques, hitting sets, and subgraphs representing various edge properties. Delve into the recurrent patterns in algorithm design and discover deterministic and randomized algorithms for finding small hitting sets efficiently.
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.
Additive Spanners Subgraph ? ? such that ???,? ???,? + ? +2 spanners with ?(?3/2) edges [Aingworth, 96] +4 spanners with ?(?7/5) edges [Chechick, 13] +6 spanners with ?(?4/3) edges [Baswana et al., 05] Lower bound [Abboud and Bodwin, 16]: No +??(1)additive spanner with ?(?4/3 ?) for any fixed ?.
Recurrent Pattern in Spanner Algorithm Goal: spanner with ? ?? edges Step 1: add all edges incident to low-deg vertices How low? ??? ? ? Step 2: handle high-deg vertices via clustering (reduces # actual vertices)
Hitting Sets Universe: ? = {?1,?2, ,??} Collection of sets ?1, ,?? where: ?? ? and ?? Goal: find a small subset ? ? such that ? ?? for every ? {1, ,?} ?1 ?2 ?3 ? = 1,2,3,4 ?1= 1,2,3 , ?2= 2,4 , ?3= {1,4} ? = {1,2} 1 2 3 4
Hitting Sets Universe: ? = {?1,?2, ,??} Sets ?1, ,?? where: ?? ? and ?? Goal: find a small subset ? ? such that ? ?? for every ? {1, ,?} Hitting set Thm: There is a deterministic algorithm that runs in ?(? ) and find a hitting set ? of size ?(?log ? )
Hitting Sets Thm: There is a randomized algorithm that runs in ?(?) and find a hitting set ? ? of size ?(?log ? ) with probability 1 1/?? Algorithm: ? ?????? ?,? for ? = ?log ?/ ? = ?(?log? ) w.h.p. (Chernoff) Pr ?? ? = = 1 ? 1/?? ? is a small hitting set
Hitting Set Instance: Universe: ? Sets: ? ??, ,?(??) high-deg vertices Goal: hit all vertices of degree Solution: sample ?log ?/ vertices ???? ? ? stars cover all high-deg vertices
+2 Additive Spanners +2 Additive Spanners Def: Given an unweighted ?-vertex graph ? = ?,? , a subgraph ? ?is a +2 additive spanner if ???,? ???,? + 2 for every ?,? ? Thm: Every ?-vertex graph ? has a +2 additive spanner ? with ?(?3/2) edges. Algorithm: Add all edges incident to vertices with deg ? ?????? ?,? for ? = ???? ?/ ? Add a BFS tree w.r.t each vertex in ? deg ?
Add all edges incident to vertices with deg ? ?????? ?,? for ? = ???? ?/ ? Add a BFS tree w.r.t each vertex in ? deg ? ? = { ?,? ? deg ? ?} ???(?) ? ? Low-deg edges Hitting-set trees = ?(?3/2log?) edges w.h.p. Claim [Size]: E H
Add all edges incident to vertices with deg ? ?????? ?,? for ? = ???? ?/ ? Add a BFS tree w.r.t each vertex in ? deg ? Claim [Stretch]: ??????,? ??????,? + ? ???,? ???,? + ???,? ?Gu,z + ???,? ???,? + 1 + ???,? = ???,? + 1 + ???,? ???,? + 1 + ???,? + 1 = ???,? + 2 ? ? ? 1 + 1 ?
+4 Additive Spanners Theorem: Every ?-vertex graph ? has a +4 spanner ? with ?(??/?)edges. Vertex ? high-deg if ??? ? ??/? (otherwise, it is low-deg). Add to ?all edges of low-deg vertices. ? ?????? ?,? for ? = ????/??/? (sample ~?2/5vertices S) ? ?????? ?,? for ? = ????/??/? (sample ~?3/5vertices T) Add to ? all BFS trees of vertices in ? Hitting set of high-deg
+4 Additive Spanners ? ?????? ?,? for ? = ????/??/? (sample ~?3/5vertices T) Cluster high-deg vertices around ?: Hitting set of high-deg For each high-deg ?: ? ? ? ? ? For each center ? ?:? ? = {? | ? ? = ?} For each center pair ?,? ?: ?,? = {? ?,? | ? ? ? ,? ? ? & ? ?,? has ?1/5high deg nodes} Add the shortest-path in ?,? to the spanner ?
+4 Additive Spanner Add to ? all edges of low-deg vertices. ? ?????? ?,? for ? = ????/??/? (sample ~?2/5vertices S) ? ?????? ?,? for ? = ????/??/? (sample ~?3/5vertices T) Add to ? all BFS trees of vertices in ? For each center pair ?,? ?: ?,? = {? ?,? | ? ? ? ,? ? ? & ? ?,? has ?1/5high deg nodes} Add the shortest-path in ?,? to the spanner ? = ? (?7/5)edges Lemma [Size]: ? ?
+4 Additive Spanner (Stretch) Add to ? all edges of low-deg vertices. ? ?????? ?,? , ? ?????? ?,? for ? = ????/??/? and ? = ????/??/? Add to ? all BFS trees of vertices in ? 1 5high deg nodes} ?,? ?: ?,? = {? ?,? | ? ? ? ,? ? ? & ? ?,? has ? Add the shortest-path in ?,? to the spanner ? Case 1: ?(?,?) has more than ?1/5high-deg vertices Case 2: ?(?,?) has less than ?1/5high-deg vertices
+4 Additive Spanner (Stretch) Add to ? all edges of low-deg vertices. ? ?????? ?,? , ? = ????/??/? ? ?????? ?,? , ? = ????/??/? Add to ? all BFS trees of vertices in ? Hitting set for paths with many high-deg vertices Hitting set for high-deg vertices ?,? ?: ?,? = {? ?,? | ? ? ? ,? ? ? & ? ?,? has ?1/5high deg nodes} Add the shortest-path in ?,? to the spanner ? Case 1: ?(?,?) has more than ?1/5high-deg vertices Case 2: ?(?,?) has less than ?1/5high-deg vertices
Case 2: ?(?,?) has less than ?1/5high-deg vertices Deg > ?2/5 ? ? ? ? ? ? ?(?,? ) ? ? ?,? : most extreme high-deg vertices on ? ?,? ?,? : centers of ?,? in T ? ?,? ?,? If ? ?,? ?,? is taken into H then ? ?,? is shorter!
1 + ?,? Spanners (nearly additive) Subgraph ? ? such that ???,? ? + ? ???,? + ?, ?,? ? Intuitively: ? + ?,? spanners provide pure multiplicative (? + ??)stretch for sufficiently far-away ?,? pairs (at distance ?/?) in G ???,? 1 + ? ???,? + ? 1 + ? ???,? + ????,? ???,? ?/? Near-exact for far pairs!
1 + ?,? Spanners [Elkin and Peleg 04, Thorup and Zwick 06, Elkin-Neiman 17]: (1 + ?,?) spanners with ? = (log?)/?)log ?with ??( ?1+1/?) edges [Abboud, Bodwin and Pettie 18]:Elkin-Peleg s spanners are optimal for ? = ?(1).
(1 + ?,1/?) Spanners with ?(?5/4) Edges ?1 ??????(?,? 1/4) ( ?1 = ?(?3/4) vertices) ?2 ??????(?1,? 1/2) ( ?2 = ?(?1/4) vertices) A vertex ? ?? is clustered if ? ?,? ?+ ? ?? ? log ? ? ?+ ? Claim: For every clustered vertex ? ?1, w.h.p: ? ?,? ?+ ? ?? ? Pf: Each vertex in ?? is sampled into ?2 with probability ?/ ? ?? is a hitting set for the ? ?,? ?+ ? balls of clustered ?? vertices
(1 + ?,1/?) Spanners with ?(?5/4) Edges ?1 ??????(?,? 1/4) ?2 ??????(?1,? 1/2) Add the following edges to H: ? ?+ ? ? 1 4 log ? Edges incident to low-deg vertices with deg ? Star edges centered at ?? (covering all high-deg vertices) For each unclustered vertex ? ?? add ?(?,?) for every v ? ?,? ?+ ? ?? For each ? ??add BFS(s )
Case 2: ?(?,?) has no clustered neighbor in ?? 1/? ? ? +4 +4 +4 Partition ? ?,? into segments of length ?/? Show that the distance between each segment endpoints is increased by +? Overall, the additive stretch ~?? ???,?
Case 2: ?(?,?) has no clustered neighbor in ?? ? ? ? ? ?? ?1 ?? ?1 ? ?+ ? First segment: ? and ? most extreme high-deg vertices Note: ?? ? ??,1 ?? ?+ 2 ? ??,?? ? ?? ???,? 1 + ????,?? + 1 = ????,?? + 2 ????,? + ???,? + ???,?? + 2 = ???,? + ?
