Dual-failure distance and connectivity oracles

ABSTRACT

Spontaneous failure is an unavoidable aspect of all networks, particularly those with a physical basis such as communications networks or road networks. Whether due to malicious coordinated attacks or other causes, failures temporarily change the topology of the network and, as a consequence, its connectivity and distance metric. In this paper we look at the problem of efficiently answering connectivity, distance, and shortest route queries in the presence of two node or link failures. Our data structure uses Õ(n²) space and answers queries in Õ (1) time, which is within a polylogarithmic factor of optimal and nearly matches the single-failure distance oracles of Demestrescu et al. It may yet be possible to find distance/connectivity oracles capable of handling any fixed number of failures. However, the sheer complexity of our algorithm suggests that moving beyond dual-failures will require a fundamentally different approach to the problem.

REFERENCES

• 1: Michael A. Bender , Martin Farach-Colton, The LCA Problem Revisited, Proceedings of the 4th Latin American Symposium on Theoretical Informatics, p.88-94, April 10-14, 2000
• 2: Michael A. Bender , Martín Farach-Colton, The level ancestor problem simplified, Theoretical Computer Science, v.321 n.1, p.5-12, June 16, 2004 [doi>10.1016/j.tcs.2003.05.002]
• 3: Aaron Bernstein , David Karger, Improved distance sensitivity oracles via random sampling, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.34-43, January 20-22, 2008, San Francisco, California
• 4: Timothy M. Chan , Mihai Patrascu , Liam Roditty, Dynamic Connectivity: Connecting to Networks and Geometry, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.95-104, October 25-28, 2008 [doi>10.1109/FOCS.2008.29]
• 5: Camil Demetrescu , Giuseppe F. Italiano, A new approach to dynamic all pairs shortest paths, Journal of the ACM (JACM), v.51 n.6, p.968-992, November 2004 [doi>10.1145/1039488.1039492]
• 6: Camil Demetrescu , Mikkel Thorup , Rezaul Alam Chowdhury , Vijaya Ramachandran, Oracles for Distances Avoiding a Failed Node or Link, SIAM Journal on Computing, v.37 n.5, p.1299-1318, January 2008 [doi>10.1137/S0097539705429847]
• 7: Yuval Emek , David Peleg , Liam Roditty, A near-linear time algorithm for computing replacement paths in planar directed graphs, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.428-435, January 20-22, 2008, San Francisco, California
• 8: J. Hershberger , S. Suri, Vickrey Prices and Shortest Paths: What is an Edge Worth?, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.252, October 14-17, 2001
• 9: John Hershberger , Subhash Suri , Amit Bhosle, On the Difficulty of Some Shortest Path Problems, Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, p.343-354, February 27-March 01, 2003
• 10: David R. Karger , Daphne Koller , Steven J. Phillips, Finding the hidden path: time bounds for all-pairs shortest paths, SIAM Journal on Computing, v.22 n.6, p.1199-1217, Dec. 1993 [doi>10.1137/0222071]
• 11: E. L. Lawler. A procedure for computing the K best solutions to discrete optimization problems and its application to the shortest path problem. Management Sci., 18:401--405, 1971/72.
• 12: K. Malik, A. K. Mittal, and S. K. Gupta. The k most vital arcs in the shortest path problem. Oper. Res. Lett., 8(4):223--227, 1989.
• 13: Enrico Nardelli , Guido Proietti , Peter Widmayer, A faster computation of the most vital edge of a shortest path, Information Processing Letters, v.79 n.2, p.81-85, June 30, 2001 [doi>10.1016/S0020-0190(00)00175-7]
• 14: Enrico Nardelli , Guido Proietti , Peter Widmayer, Finding the most vital node of a shortest path, Theoretical Computer Science, v.296 n.1, p.167-177, 4 March 2003 [doi>10.1016/S0304-3975(02)00438-3]
• 15: N. Nisan and A. Ronen. Algorithmic mechanism design. Games Econom. Behav., 35(1--2):166--196, 2001. Economics and artificial intelligence.
• 16: Mihai Patrascu , Mikkel Thorup, Planning for Fast Connectivity Updates, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.263-271, October 21-23, 2007 [doi>10.1109/FOCS.2007.54]
• 17: S. Pettie. Sensitivity analysis of minimum spanning trees in sub-inverse-Ackermann time. In Proceedings 16th Int'l Symposium on Algorithms and Computation (ISAAC), pages 964--973, 2005.
• 18: L. Roditty and U. Zwick. Replacement paths and k-simple shortest paths in unweighted directed graphs. In Proceedings 32nd Int'l Colloq. on Automata, Languages, and Programming (ICALP), pages 249--260, 2005.
• 19: Baruch Schieber , Uzi Vishkin, On finding lowest common ancestors: simplification and parallelization, SIAM Journal on Computing, v.17 n.6, p.1253-1262, Dec. 1988 [doi>10.1137/0217079]
• 20: J. Y. Yen. Finding the K shortest loopless paths in a network. Management Sci., 17:712--716, 1970/71.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms