Document Open Access Logo

Preserving Distances in Very Faulty Graphs

Authors Greg Bodwin, Fabrizio Grandoni, Merav Parter, Virginia Vassilevska Williams

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.73.pdf
  • Filesize: 0.54 MB
  • 14 pages

Document Identifiers

Author Details

Greg Bodwin
Fabrizio Grandoni
Merav Parter
Virginia Vassilevska Williams

Cite As Get BibTex

Greg Bodwin, Fabrizio Grandoni, Merav Parter, and Virginia Vassilevska Williams. Preserving Distances in Very Faulty Graphs. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 73:1-73:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.73

Abstract

Preservers and additive spanners are sparse (hence cheap to store) subgraphs that preserve the distances between given pairs of nodes exactly or with some small additive error, respectively. Since real-world networks are prone to failures, it makes sense to study fault-tolerant versions of the above structures. This turns out to be a surprisingly difficult task. For every small but arbitrary set of edge or vertex failures, the preservers and spanners need to contain replacement paths around the faulted set. Unfortunately, the complexity of the interaction between replacement paths blows up significantly, even from 1 to 2 faults, and the structure of optimal preservers and spanners is poorly understood. In particular, no nontrivial bounds for preservers and additive spanners are known when the number of faults is bigger than 2.

Even the answer to the following innocent question is completely unknown: what is the worst-case size of a preserver for a single pair of nodes in the presence of f edge faults? There are no super-linear lower bounds, nor subquadratic upper bounds for f>2. In this paper we make substantial progress on this and other fundamental questions:

- We present the first truly sub-quadratic size fault-tolerant single-pair preserver in unweighted (possibly directed) graphs: for any n node graph and any fixed number f of faults, O~(fn^{2-1/2^f}) size suffices. Our result also generalizes to the single-source (all targets) case, and can be used to build new fault-tolerant additive spanners (for all pairs). 

- The size of the above single-pair preserver grows to O(n^2) for increasing f. We show that this is necessary even in undirected unweighted graphs, and even if you allow for a small additive error: If you aim at size O(n^{2-eps}) for \eps>0, then the additive error has to be \Omega(eps f). This surprisingly matches known upper bounds in the literature. 

- For weighted graphs, we provide matching upper and lower bounds for the single pair case. Namely, the size of the preserver is Theta(n^2) for f > 1 in both directed and undirected graphs, while for f=1 the size is Theta(n) in undirected graphs. For directed graphs, we have a superlinear upper bound and a matching lower bound.

Most of our lower bounds extend to the distance oracle setting, where rather than a subgraph we ask for any compact data structure.

Subject Classification

Keywords
  • Fault Tolerance
  • shortest paths
  • replacement paths

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. A. Abboud and G. Bodwin. The 4/3 additive spanner exponent is tight. In STOC, pages 351-361, 2016. Google Scholar
  2. Amir Abboud, Greg Bodwin, and Seth Pettie. A hierarchy of lower bounds for sublinear additive spanners. In SODA, pages 568-576, 2017. Google Scholar
  3. D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput., 28(4):1167-1181, 1999. Google Scholar
  4. I. Althöfer, G. Das, D. Dobkin, D. Joseph, and J. Soares. On sparse spanners of weighted graphs. Discrete &Computational Geometry, 9(1):81-100, 1993. Google Scholar
  5. S. Baswana, K. Choudhary, and L. Roditty. Fault tolerant subgraph for single source reachability: generic and optimal. In STOC, pages 509-518, 2016. Google Scholar
  6. S. Baswana, K. Telikepalli, K. Mehlhorn, and S. Pettie. New constructions of (alpha, beta)-spanners and purely additive spanners. In SODA, pages 672-681, 2005. Google Scholar
  7. Aaron Bernstein and David R. Karger. A nearly optimal oracle for avoiding failed vertices and edges. In STOC, pages 101-110, 2009. Google Scholar
  8. D. Bilò, F. Grandoni, L. Gualà, S. Leucci, and G. Proietti. Improved purely additive fault-tolerant spanners. In ESA, pages 167-178. Springer, 2015. Google Scholar
  9. D. Bilò, L. Gualà, S. Leucci, and G. Proietti. Fault-tolerant approximate shortest-path trees. In ESA, pages 137-148. Springer, 2014. Google Scholar
  10. G. Bodwin. Linear size distance preservers. In SODA, 2017. Google Scholar
  11. G. Bodwin and V. Vassilevska Williams. Better distance preservers and additive spanners. In SODA, pages 855-872, 2016. Google Scholar
  12. Greg Bodwin. Linear size distance preservers. In SODA, pages 600-615, 2017. Google Scholar
  13. Greg Bodwin, Fabrizio Grandoni, Merav Parter, and Virginia Vassilevska Williams. Preserving distances in very faulty graphs. CoRR, abs/1703.10293, 2017. URL: http://arxiv.org/abs/1703.10293.
  14. G. Braunschvig, S. Chechik, D. Peleg, and A. Sealfon. Fault tolerant additive and (μ, α)-spanners. Theor. Comput. Sci., 580:94-100, 2015. Google Scholar
  15. S. Chechik. New additive spanners. In SODA, pages 498-512, 2013. Google Scholar
  16. S. Chechik, M. Langberg, D. Peleg, and L. Roditty. Fault-tolerant spanners for general graphs. In STOC, pages 435-444, 2009. Google Scholar
  17. S. Chechik and D. Peleg. Rigid and competitive fault tolerance for logical information structures in networks. In Electrical and Electronics Engineers in Israel (IEEEI), 2010 IEEE 26th Convention of, pages 000024-000025. IEEE, 2010. Google Scholar
  18. D. Coppersmith and M. Elkin. Sparse sourcewise and pairwise distance preservers. SIAM Journal on Discrete Mathematics, 20(2):463-501, 2006. Google Scholar
  19. A. Czumaj and H. Zhao. Fault-tolerant geometric spanners. Discrete &Computational Geometry, 32(2):207-230, 2004. Google Scholar
  20. C. Demetrescu, M. Thorup, R. A. Chowdhury, and V. Ramachandran. Oracles for distances avoiding a failed node or link. SIAM Journal on Computing, 37(5):1299-1318, 2008. Google Scholar
  21. M. Dinitz and R. Krauthgamer. Fault-tolerant spanners: better and simpler. In PODC, pages 169-178, 2011. Google Scholar
  22. R. Duan and S. Pettie. Dual-failure distance and connectivity oracles. In SODA, pages 506-515, 2009. Google Scholar
  23. Ran Duan and Seth Pettie. Connectivity oracles for graphs subject to vertex failures. In SODA, pages 490-509, 2017. Google Scholar
  24. M. Elkin and D. Peleg. (1+epsilon, beta)-spanner constructions for general graphs. SIAM J. Comput., 33(3):608-631, 2004. Google Scholar
  25. P. Erdös. Extremal problems in graph theory. Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), pages 29-36, 1963. Google Scholar
  26. F. Grandoni and V. Vassilevska Williams. Improved distance sensitivity oracles via fast single-source replacement paths. In FOCS, pages 748-757, 2012. Google Scholar
  27. C. Levcopoulos, G. Narasimhan, and M. Smid. Improved algorithms for constructing fault-tolerant spanners. Algorithmica, 32(1):144-156, 2002. Google Scholar
  28. T. Lukovszki. New results on fault tolerant geometric spanners. In Algorithms and Data Structures, pages 193-204. Springer, 1999. Google Scholar
  29. K. Malik, A. K. Mittal, and S. K. Gupta. The k most vital arcs in the shortest path problem. Operations Research Letters, 8(4):223-227, 1989. Google Scholar
  30. M. Parter. Vertex fault tolerant additive spanners. In Distributed Computing, pages 167-181. Springer, 2014. Google Scholar
  31. M. Parter. Dual failure resilient BFS structure. In PODC, pages 481-490, 2015. Google Scholar
  32. M. Parter and D. Peleg. Sparse fault-tolerant BFS trees. In ESA, pages 779-790, 2013. Google Scholar
  33. M. Parter and D. Peleg. Fault tolerant approximate BFS structures. In SODA, pages 1073-1092, 2014. Google Scholar
  34. S. Pettie. Low distortion spanners. ACM Transactions on Algorithms, 6(1), 2009. Google Scholar
  35. L. Roditty and U. Zwick. Replacement paths and k simple shortest paths in unweighted directed graphs. ACM Transactions on Algorithms, 8(4):33, 2012. Google Scholar
  36. M. Thorup and U. Zwick. Spanners and emulators with sublinear distance errors. In SODA, pages 802-809, 2006. Google Scholar
  37. V. Vassilevska Williams. Faster replacement paths. In SODA, pages 1337-1346. SIAM, 2011. Google Scholar
  38. O. Weimann and R. Yuster. Replacement paths and distance sensitivity oracles via fast matrix multiplication. ACM Transactions on Algorithms, 9(2):14, 2013. Google Scholar
  39. D. P. Woodruff. Additive spanners in nearly quadratic time. In ICALP, pages 463-474, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact