Ken-ichi Kawarabayashi
ABSTRACT
We present a deterministic near-linear time algorithm that computes the edge-connectivity and finds a minimum cut for a simple undirected unweighted graph G with n vertices and m edges. This is the first o(mn) time deterministic algorithm for the problem. In near-linear time we can also construct the classic cactus representation of all minimum cuts.
The previous fastest deterministic algorithm by Gabow from STOC'91 took O(m+λ2 n), where λ is the edge connectivity, but λ could be Ω(n).
At STOC'96 Karger presented a randomized near linear time Monte Carlo algorithm for the minimum cut problem. As he points out, there is no better way of certifying the minimality of the returned cut than to use Gabow's slower deterministic algorithm and compare sizes.
Our main technical contribution is a near-linear time algorithm that contracts vertex sets of a simple input graph G with minimum degree δ, producing a multigraph G with ~O(m/δ) edges which preserves all minimum cuts of G with at least two vertices on each side.
In our deterministic near-linear time algorithm, we will decompose the problem via low-conductance cuts found using PageRank a la Brin and Page (1998), as analyzed by Andersson, Chung, and Lang at FOCS'06. Normally such algorithms for low-conductance cuts are randomized Monte Carlo algorithms, because they rely on guessing a good start vertex. However, in our case, we have so much structure that no guessing is needed.
- R. Andersen, F. R. K. Chung, and K. J. Lang. Using pagerank to locally partition a graph. Internet Mathematics, 4(1):35--64, 2007.Google Scholar
Cross Ref
- S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. J. Comput. Networks and ISDN Systems archive, 30:107--117, 1998. Google ScholarDigital Library
- P. Chalermsook, J. Fakcharoenphol, and D. Nanongkai. A deterministic near-linear time algorithm for finding minimum cuts in planar graphs. In Proc. 15th SODA, pages 828--829, 2004. Google ScholarDigital Library
- E. A. Dinitz, A. V. Karzanov, and M. V. Lomonosov. On the structure of a family of minimum weighted cuts in a graph. Studies in Discrete Optimization, pages 290--306, 1976.Google Scholar
- S. Even and R. E. Tarjan. Network flow and testing graph connectivity. SIAM Journal of Computing, 4:507--518, 1975.Google ScholarCross Ref
- L. R. Ford and D. R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8:399--404, 1956.Google ScholarCross Ref
- A. Frank. On the edge-connectivity algorithm of nagamochi and ibaraki. Laboratoire Artemis, IMAG, Universitk J. Fourier, Grenoble, 1994.Google Scholar
- H. N. Gabow. Applications of a poset representation to edge connectivity and graph rigidity. In Proceedings of the 32nd Annual Symposium on the Foundations of Computer Science, pages 812--821, 1991. Google ScholarDigital Library
- H. N. Gabow. A matroid approach to finding edge connectivity and packing arborescences. J. Comp. Syst. Sc., 50:259--273, 1995. Announced at STOC'91. Google ScholarDigital Library
- R. E. Gomory and T. C. Hu. Multi-terminal network flows. Journal of the Society of Industrial and Applied Mathematics, 9(4):551--570, 1961.Google ScholarCross Ref
- J. Hao and J. Orlin. A faster algorithm for finding the minimum cut in a directed graph. Journal of Algorithms, 17(3):424--446, 1994. announced at SODA'92. Google ScholarDigital Library
- M. Henzinger and D. Williamson. On the number of small cuts in a graph. Inf. Process. Lett., 59(1):41--44, 1996. Google ScholarDigital Library
- D. R. Karger. Random sampling in cut, flow, and network design problems. Math. Oper. Res., 24(2):383--413, 1999. Announced at STOC'94. Google ScholarCross Ref
- D. R. Karger. Minimum cuts in near-linear time. J. ACM, 47(1):46--76, 2000. Announced at STOC'96. Google ScholarDigital Library
- D. R. Karger and D. Panigrahi. A near-linear time algorithm for constructing a cactus representation of minimum cuts. In Proc. the Twentieth ACM-SIAM Symp. on Discrete Algorithms, pages 246--255, 2009. Google ScholarDigital Library
- D. R. Karger and C. Stein. A new approach to the minimum cut problem. J. ACM, 43(4), 1996. Announced at SODA'92 and STOC'93. Google ScholarDigital Library
- A. Karzanov and E. Timofeev. Efficient algorithm for finding all minimal edge cuts of a nonoriented graph. Kibernetika, 2:8--12, 1986. translated in Cybernetics, (1986), pp. 156--162.Google Scholar
- K. Kawarabayashi and M. Thorup. Deterministic global minimum cut of a simple graph in near-linear time. CoRR, abs/1411.5123, 2014.Google Scholar
- D. W. Matula. Determining the edge connectivity in o(mn) time. In Proc. the 28th Annual Symp. on the Foundations of Computer Science, pages 249--251, 1987. Google ScholarDigital Library
- D. W. Matula. A linear time 2+ε approximation algorithm for edge connectivity. In Proc. 4th ACM-SIAM Symp. on Discrete Algorithms, pages 500--504, 1993. Google ScholarDigital Library
- K. Menger. Zur allgemeinen kurventheorie. Fund. Math., 10:96--115, 1927.Google ScholarCross Ref
- H. Nagamochi and T. Ibaraki. Computing edge connectivity in multigraphs and capacitated graphs. SIAM Journal of Discrete Mathematics, 5(1):54--66, 1992. Announced at SIGAL'90. Google ScholarDigital Library
- V. D. Podderyugin. An algorithm for finding the edge connectity of graphs. Vopr. Kibern., 2:136, 1973.Google Scholar
- A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer, NY, 2003.Google Scholar
- M. Stoer and F. Wagner. A simple minimum cut. J. ACM, 44:585--591, 1997. Announced at ESA'94. Google ScholarDigital Library
Index Terms
- Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time
Recommendations
Deterministic mincut in almost-linear time
STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of ComputingWe present a deterministic (global) mincut algorithm for weighted, undirected graphs that runs in m1+o(1) time, answering an open question of Karger from the 1990s. To obtain our result, we de-randomize the construction of the skeleton graph in Karger’s ...
Deterministic Edge Connectivity in Near-Linear Time
We present a deterministic algorithm that computes the edge-connectivity of a graph in near-linear time. This is for a simple undirected unweighted graph G with n vertices and m edges. This is the first o(mn) time deterministic algorithm for the ...
A new approach to the minimum cut problem
This paper present a new approach to finding minimum cuts in undirected graphs. The fundamental principle is simple: the edges in a graph's minimum cut form an extremely small fraction of the graph's edges. Using this idea, we give a randomized, ...
Comments