Fully-dynamic min-cut

ABSTRACT

We show that we can maintain up to polylogarithmic edge connectivity for a fully-dynamic graph in \tilde O(\sqrt{n}) time per edge insertion or deletion. Within logarithmic factors, this matches the best time bound for 1-edge connectivity. Previously, no o(n) bound was known for edge connectivity above 3, and even for 3-edge connectivity, the best update time was O(n^{2/3}), dating back to FOCS'92.Our algorithm maintains a concrete min-cut in terms of a pointer to a tree spanning one side of the cut plus ability to list the cut edges in O(\log n) time per edge.By dealing with polylogarithmic edge connectivity, we immediately get a sampling based expected factor (1+o(1)) approximation to general edge connectivity in \tilde O(\sqrt{n}) time per edge insertion or deletion. This algorithm also maintains a pointer to one side of a min-cut, but if we want to list the cut edges in O(\log n) time per edge, the update time increases to \tilde O(\sqrt{m}).

REFERENCES

• 1: Stephen Alstrup , Jacob Holm , Kristian de Lichtenberg , Mikkel Thorup, Minimizing Diameters of Dynamic Trees, Proceedings of the 24th International Colloquium on Automata, Languages and Programming, p.270-280, July 07-11, 1997
• 2: Stephen Alstrup , Jacob Holm , Mikkel Thorup, Maintaining Center and Median in Dynamic Trees, Proceedings of the 7th Scandinavian Workshop on Algorithm Theory, p.46-56, July 05-07, 2000
• 3: L. G. Valiant D. Angluin. Fast probabilistic algorithms for Hamiltonian circuits and matchings. J. Comput. System Sci., 18:155-193, 1979.
• 4: Yefim Dinitz , Ronit Nossenson, Incremental Maintenance of the 5-Edge-Connectivity Classes of a Graph, Proceedings of the 7th Scandinavian Workshop on Algorithm Theory, p.272-285, July 05-07, 2000
• 5: 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]
• 6: David Eppstein , Zvi Galil , Giuseppe F. Italiano , Thomas H. Spencer, Separator-Based Sparsification II: Edge and Vertex Connectivity, SIAM Journal on Computing, v.28 n.1, p.341-381, Feb. 1999 [doi>10.1137/S0097539794269072]
• 7: Greg N. Frederickson, Data structures for on-line updating of minimum spanning trees, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.252-257, December 1983 [doi>10.1145/800061.808754]
• 8: Greg N. Frederickson, Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees, SIAM Journal on Computing, v.26 n.2, p.484-538, April 1997 [doi>10.1137/S0097539792226825]
• 9: 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]
• 10: David R. Karger, Using randomized sparsification to approximate minimum cuts, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.424-432, January 23-25, 1994, Arlington, Virginia, United States
• 11: David R. Karger, Minimum cuts in near-linear time, Journal of the ACM (JACM), v.47 n.1, p.46-76, Jan. 2000 [doi>10.1145/331605.331608]
• 12: H. Nagamochi and T. Ibaraki. Linear time algorithms for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica, 7:583-596, 1992.
• 13: C. St. J. A. Nash-Williams. Edge disjoint spanning trees of finite graphs. J. London Math. Soc., 36(144):445-450, 1961.
• 14: Serge A. Plotkin , David B. Shmoys , Éva Tardos, Fast approximation algorithms for fractional packing and covering problems, Mathematics of Operations Research, v.20 n.2, p.257-301, May 1995 [doi>10.1287/moor.20.2.257]
• 15: Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]
• 16: Mikkel Thorup, Decremental dynamic connectivity, Journal of Algorithms, v.33 n.2, p.229-243, Nov. 1999 [doi>10.1006/jagm.1999.1033]
• 17: Mikkel Thorup, Dynamic Graph Algorithms with Applications, Proceedings of the 7th Scandinavian Workshop on Algorithm Theory, p.1-9, July 05-07, 2000
• 18: W. T. Tutte. On the problem of decomposing a graph into n connected factors. J. London Math. Soc., 36:221-230, 1961.
• 19: Neal E. Young, Randomized rounding without solving the linear program, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.170-178, January 22-24, 1995, San Francisco, California, United States

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

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

General Terms:
Algorithms, Measurement, Performance, Theory, Verification