Dynamic subgraph connectivity with geometric applications

ABSTRACT

(MATH) Inspired by dynamic connectivity applications in computational geometry, we consider a problem we call dynamic subgraph connectivity: design a data structure for an undirected graph $G=(V,E)$ and a subset of vertices $S\on V$, to support insertions and deletions in~$S$ and connectivity queries (are two vertices connected\@?) in the subgraph induced by~$S$. We develop the first sublinear, fully dynamic method for this problem for general sparse graphs, using an elegant combination of several simple ideas. Our method requires linear space, $\OO (|E|^{4\w/(3\w+3)})=O(|E|^{0.94})$ amortized update time, and $\OO(|E|^{1/3})$ query time, where $\w$ is the matrix multiplication exponent and $\OO$ hides polylogarithmic factors.

REFERENCES

• 1: P. K. Agarwal, N. Alon, B. Aronov, and S. Suri. Can visibility graphs be represented compactly? Discrete Comput.Geom., 12:347--365 1994.
• 2: P. K. Agarwal and J. Erickson. Geometric range searching and its relatives. In Advances in Discrete and Computational Geometry (B. Chazelle, J. E. Goodman, and R. Pollack, eds.), pp. 1--56, AMS Press, 1999.
• 3: P. K. Agarwal and M. van Kreveld. Polygon and connected component intersection searching. Algorithmica 15 626--660 1996.
• 4: N. Alon, R. Yuster, and U. Zwick. Finding and counting given length cycles. Algorithmica 17 209--223 1997.
• 5: J. Bentley and J. Saxe. Decomposable searching problems I: static-to-dynamic transformation. J Algorithmica 1 301--358 1980.
• 6: Timothy M. Chan, A fully dynamic algorithm for planar, Proceedings of the seventeenth annual symposium on Computational geometry, p.172-176, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378660]
• 7: Timothy M. Chan, Semi-online maintenance of geometric optima and measures, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.474-483, January 06-08, 2002, San Francisco, California
• 8: Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
• 9: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 10: C. Demetrescu , G. F. Italiano, Fully dynamic transitive closure: breaking through the O(n/sup 2/) barrier, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.381, November 12-14, 2000
• 11: David Dobkin , Subhash Suri, Maintenance of geometric extrema ∈ , Journal of the ACM (JACM), v.38 n.2, p.275-298, April 1991 [doi>10.1145/103516.103518]
• 12: D. Eppstein. Dynamic Euclidean minimum spanning trees and extrema of binary functions. Discrete Comput.Geom., 13 111--122 1995.
• 13: David Eppstein , Zvi Galil , Giuseppe F. Italiano , Amnon Nissenzweig, Sparsification—a technique for speeding up dynamic graph algorithms, Journal of the ACM (JACM), v.44 n.5, p.669-696, Sept. 1997 [doi>10.1145/265910.265914]
• 14: Tomás Feder , Rajeev Motwani, Clique partitions, graph compression and speeding-up algorithms, Journal of Computer and System Sciences, v.51 n.2, p.261-272, Oct. 1995 [doi>10.1006/jcss.1995.1065]
• 15: G. N. Frederickson. Data structures for on-line updating of minimum spanning trees, with applications. SAIM J. Comput., 14 781--798 1998.
• 16: D. Frigioni and G. F. Italiano. Dynamically switching vertices in planar graphs. Algorithmica 28 76--103 2000.
• 17: Monika R. Henzinger , Valerie King, Randomized fully dynamic graph algorithms with polylogarithmic time per operation, Journal of the ACM (JACM), v.46 n.4, p.502-516, July 1999 [doi>10.1145/320211.320215]
• 18: Monika R. Henzinger , Valerie King, Maintaining Minimum Spanning Forests in Dynamic Graphs, SIAM Journal on Computing, v.31 n.2, p.364-374, 2001 [doi>10.1137/S0097539797327209]
• 19: John Hershberger , Subhash Suri, Kinetic connectivity of rectangles, Proceedings of the fifteenth annual symposium on Computational geometry, p.237-246, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304977]
• 20: John Hershberger , Subhash Suri, Simplified kinetic connectivity for rectangles and hypercubes, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.158-167, January 07-09, 2001, Washington, D.C., United States
• 21: Jacob Holm , Kristian de Lichtenberg , Mikkel Thorup, Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.79-89, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276715]
• 22: H. Imai and T. Asano. Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane. J.Algorithms 310--323 1983.
• 23: S. Khanna, R. Motwani, and R. H. Wilson. On certificates and lookahead on dynamic graph problems. Algorithmica 21 377--394 1998.
• 24: Ramakrishna Thurimella , Mario Alberto Lopez, On Computing Connected Components of Line Segments, IEEE Transactions on Computers, v.44 n.4, p.597-601, April 1995 [doi>10.1109/12.376174]
• 25: K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice-Hall, 1994.
• 26: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 27: Mikkel Thorup, Decremental dynamic connectivity, Journal of Algorithms, v.33 n.2, p.229-243, Nov. 1999 [doi>10.1006/jagm.1999.1033]
• 28: Mikkel Thorup, Near-optimal fully-dynamic graph connectivity, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.343-350, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335345]

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures; Geometrical problems and computations

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Design, Theory