 Download Download Presentation Download Presentation - - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -
##### Presentation Transcript

2. Talk Outline • Spanners • Definition • Applications • Previous work • Our Results • Our Techniques for Additive-6 spanner • New existence proof • Efficiency • Conclusion

3. Spanners • G = (V, E) undirected unweighted graph, n vertices, m edges • G(u,v) shortest path length from u to v in G • [A, PS] An (a, b)-spanner of G is a subgraph H such that for all u, v in V, H(u,v) · aG(u,v) + b • If b = 0, H is a multiplicative spanner • If a = 1, H is an additive spanner • Challenge: find sparse H, and do it quickly

4. Spanner Application • 3-approximate distance queries G(u,v) with small space • Construct a (3,0)-spanner H with O(n3/2) edges. [PS, ADDJS] do this efficiently • Query answer: G(u,v) ·H(u,v) · 3G(u,v) • Algorithmic tool: replace complicated dense graph with spanner • Spanner should be sparse • Algorithm should be efficient

5. Multiplicative Spanners • [PS, ADDJS] For every k, can find a (2k-1, 0)-spanner with O(n1+1/k) edges in O(m) time • This is optimal assuming a girth conjecture of Erdos

6. Surprise, Surprise • [ACIM, DHZ]: Construct a (1,2)-spanner H with O(n3/2) edges in O~(n2) time • Remarkable: for all u,v:G(u,v) ·H(u,v) ·G(u,v) + 2 • Query answer is a 3-approximation, but with much stronger guarantees for G(u,v) large

7. Additive Spanners • Sparsity Upper Bounds: • (1,2)-spanner: O(n3/2) edges [ACIM, DHZ] • (1,6)-spanner: O(n4/3) edges [BKMP] • For any constant c > 6, best (1,c)-spanner known is O(n4/3) • For graphs with few edges on short cycles, can get better bounds [P] • Time Bounds: • A (1,2)-spanner can be found in O~(n2) time [DHZ] • A (1,6)-spanner can be found in O(mn2/3) time [BKMP, Elkin]

8. Talk Outline • Spanners • Definition • Applications • Previous Work • Our Results • Our Techniques for Additive-6 spanner • New existence proof • Efficiency • Conclusion

9. Main Contribution • We construct an additive-6 spanner with O~(n4/3) edges in O~(n2) time • Improves previous O(mn2/3) time for all m, n • Based on a new “path-hitting” framework

10. Corollary: Graphs with Large Girth • We construct additive spanners for input graphs G with large girth in O~(n2) time • E.g., if G has girth > 4, we construct an additive 4-spanner with O~(n4/3) edges in O~(n2) time • Improves previous O(mn) time • E.g., if G has girth > 4, we construct an additive 8-spanner with O~(n5/4) edges in O~(n2) time • Improves previous O(mn3/4) time • Generalizes to graphs with few edges on short cycles

11. Corollary: Source-wise Preservers • Given a subset S of O(n2/3) vertices of G, we compute a subgraph H of O~(n4/3) edges in O~(n2) time so that • For all u,v in S, δH(u,v) ·δG(u,v) + 2 • Improves previous O(mn2/3) time

12. Talk Outline • Spanners • Definition • Applications • Previous Work • Our Results • Our Techniques for Additive-6 spanner • New existence proof • Efficiency • Conclusion

13. Include Light Edges • Include all edges incident to degree < n1/3 vertices in spanner • Call these edges light • At most O(n4/3) edges included

14. Path-Hitting v u • Consider any shortest path. Suppose it goes from u to v. • Done if all edges on path are light • Otherwise there are heavy edges • Each heavy edge e is adjacent to a set Se of > n1/3 vertices • For heavy edges e and e’, Se and Se’ are disjoint

15. Path-Hitting v Wasn’t heavy u r z s P P’ • Randomly sample O~(n2/3) vertices. Call these representatives • Connect each vertex to one representative (if possible) • W.h.p. every degree > n1/3 vertex has an adjacent representative • Suppose there are x heavy edges • Then there are > x * n1/3 distinct vertices at distance one from the path • Randomly sample O~(n2/3/x) vertices. Call these path-hitters • W.h.p. sample a vertex adjacent to the path • Path from u to v in the spanner: • traverse light edges + representative edge to get to r • take P to get to z • take P’ to get to s • traverse representative edge + light edges to get to v • By triangle inequality can show additive distortion is 6 • Connect each path-hitter to each representative using an almost (+0, +1, +2) shortest path P with at most x heavy edges • Only pay for heavy edges along P • At most x heavy edges along P • # of edges included is O~(n2/3)*O~(n2/3/x)*x = O~(n4/3)

16. Recap • Algorithm: • 1. Randomly sample O~(n2/3) representatives • 2. Randomly sample O~(n2/3/x) path-hitters • 3. Connect each representative to each path-hitter on an almost (+0, +1, +2) shortest path using O(x) heavy edges • This works w.h.p. for all shortest paths containing between x and 2x heavy edges • To make it work for all shortest paths, vary x in powers of 2 and take the union of the edge-sets • Theorem: there exists an additive-6 spanner with O~(n4/3) edges

17. Talk Outline • Spanners and related objects • Definition • Applications • Previous Work • Our Results • Our Techniques for Additive-6 spanner • New existence proof • Efficiency • Conclusion

18. Efficiency • Algorithm: 1. Randomly sample O~(n2/3) representatives 2. Randomly sample O~(n2/3/x) path-hitters 3. Connect each representative to each path-hitter on an almost (+0, +1, +2) shortest path using O(x) heavy edges • Only one time consuming step • Bicreteria problem: • Almost (+0, +1, +2) shortest path AND O(x) heavy edges • Simple breadth-first-search-like procedure • Time complexity proportional to # of edges in the graph • Only get quadratic time if # of edges is O(n4/3x) 

19. Deleting High Degree Vertices • If maximum degree · n1/3x, we get quadratic time • Delete all degree > n1/3x vertices and incident edges, run algorithm on subgraph • Oops, some shortest paths are disconnected v u

20. Dominating Sets z Maximum degree = d v u • This only happens if there is a degree d > n1/3x vertex on the path • Delete all degree > d vertices in graph and incident edges • Choose a dominating set of O~(n/d) vertices for degree d vertices • Connect vertices in dominating set to representatives via an almost shortest path with O(x) heavy edges • # of edges is O~(n/d * n2/3 * x) = O~(n4/3). Time is O~(n/d * nd) = O~(n2). • Vary both d and x in powers of 2. Take the union of the edge-sets found.

21. Talk Outline • Spanners and related objects • Definition • Applications • Previous Work • Our Results • Our Techniques for Additive-6 spanner • New existence proof • Efficiency • Conclusion

22. Conclusion • New path-hitting framework improves running times of spanner problems to O~(n2) • Additive-6 spanner with O~(n4/3) edges • Further sparsifies inputs with large girth • Approximate source-wise preservers • Other graph problems for which technique may apply • Constructing emulators more efficiently • Constructing near-additive spanners more efficiently, i.e., for all pairs u, v, δH(u,v) · (1+ε)δG(u,v) + 4, where ε > 0 is arbitrary