LIPIcs.ESA.2023.92.pdf
- Filesize: 0.72 MB
- 9 pages
Document
Maximal k-Edge-Connected Subgraphs in Almost-Linear Time for Small k
Authors
Thatchaphol Saranurak 
,
Wuwei Yuan
-
Part of:
Volume:
31st Annual European Symposium on Algorithms (ESA 2023)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: European Symposium on Algorithms (ESA) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2023-08-30
File
Document Identifiers
Author Details
Cite AsGet BibTex
Thatchaphol Saranurak and Wuwei Yuan. Maximal k-Edge-Connected Subgraphs in Almost-Linear Time for Small k. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 92:1-92:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ESA.2023.92
https://doi.org/10.4230/LIPIcs.ESA.2023.92
Abstract
We give the first almost-linear time algorithm for computing the maximal k-edge-connected subgraphs of an undirected unweighted graph for any constant k. More specifically, given an n-vertex m-edge graph G = (V,E) and a number k = log^o(1) n, we can deterministically compute in O(m+n^{1+o(1)}) time the unique vertex partition {V_1,… ,V_z} such that, for every i, V_i induces a k-edge-connected subgraph while every superset V'_i ⊃ V_{i} does not. Previous algorithms with linear time work only when k ≤ 2 [Tarjan SICOMP'72], otherwise they all require Ω(m+n√n) time even when k = 3 [Chechik et al. SODA'17; Forster et al. SODA'20].
Our algorithm also extends to the decremental graph setting; we can deterministically maintain the maximal k-edge-connected subgraphs of a graph undergoing edge deletions in m^{1+o(1)} total update time. Our key idea is a reduction to the dynamic algorithm supporting pairwise k-edge-connectivity queries [Jin and Sun FOCS'20].
Subject Classification
ACM Subject Classification
- Theory of computation → Graph algorithms analysis
Keywords
- Graph algorithms
- Maximal k-edge-connected subgraphs
- Dynamic k-edge connectivity
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, and Ohad Trabelsi. Breaking the cubic barrier for all-pairs max-flow: Gomory-hu tree in nearly quadratic time. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 884-895. IEEE, 2022. URL: https://doi.org/10.1109/FOCS54457.2022.00088.
- Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. Linear-time enumeration of maximal k-edge-connected subgraphs in large networks by random contraction. In Qi He, Arun Iyengar, Wolfgang Nejdl, Jian Pei, and Rajeev Rastogi, editors, 22nd ACM International Conference on Information and Knowledge Management, CIKM'13, San Francisco, CA, USA, October 27 - November 1, 2013, pages 909-918. ACM, 2013. URL: https://doi.org/10.1145/2505515.2505751.
- Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Veronika Loitzenbauer, and Nikos Parotsidis. Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1900-1918. SIAM, 2017. URL: https://doi.org/10.1137/1.9781611974782.124.
- Sebastian Forster, Danupon Nanongkai, Liu Yang, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai. Computing and testing small connectivity in near-linear time and queries via fast local cut algorithms. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 2046-2065. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.126.
- Loukas Georgiadis, Giuseppe F. Italiano, Evangelos Kosinas, and Debasish Pattanayak. On maximal 3-edge-connected subgraphs of undirected graphs. CoRR, abs/2211.06521, 2022. URL: https://doi.org/10.48550/arXiv.2211.06521.
- Monika Rauch Henzinger, Satish Rao, and Harold N. Gabow. Computing vertex connectivity: New bounds from old techniques. In 37th Annual Symposium on Foundations of Computer Science, FOCS '96, Burlington, Vermont, USA, 14-16 October, 1996, pages 462-471. IEEE Computer Society, 1996. URL: https://doi.org/10.1109/SFCS.1996.548505.
- Wenyu Jin and Xiaorui Sun. Fully dynamic s-t edge connectivity in subpolynomial time (extended abstract). In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 861-872. IEEE, 2021. URL: https://doi.org/10.1109/FOCS52979.2021.00088.
- David R. Karger. Minimum cuts in near-linear time. J. ACM, 47(1):46-76, 2000. URL: https://doi.org/10.1145/331605.331608.
- Hiroshi Nagamochi and Toshihide Ibaraki. Algorithmic Aspects of Graph Connectivity. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2008. URL: https://doi.org/10.1017/CBO9780511721649.
- Chaitanya Nalam and Thatchaphol Saranurak. Maximal k-edge-connected subgraphs in weighted graphs via local random contraction. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 183-211. SIAM, 2023. URL: https://doi.org/10.1137/1.9781611977554.ch8.
- Thatchaphol Saranurak and Wuwei Yuan. Maximal k-edge-connected subgraphs in almost-linear time for small k, 2023. URL: https://doi.org/10.48550/arXiv.2307.00147.
- Heli Sun, Jianbin Huang, Yang Bai, Zhongmeng Zhao, Xiaolin Jia, Fang He, and Yang Li. Efficient k-edge connected component detection through an early merging and splitting strategy. Knowl. Based Syst., 111:63-72, 2016. URL: https://doi.org/10.1016/j.knosys.2016.08.006.
- Robert Endre Tarjan. Depth-first search and linear graph algorithms. SIAM J. Comput., 1(2):146-160, 1972. URL: https://doi.org/10.1137/0201010.
- Mikkel Thorup. Fully-dynamic min-cut. In Jeffrey Scott Vitter, Paul G. Spirakis, and Mihalis Yannakakis, editors, Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece, pages 224-230. ACM, 2001. URL: https://doi.org/10.1145/380752.380804.
- Xifeng Yan, Xianghong Jasmine Zhou, and Jiawei Han. Mining closed relational graphs with connectivity constraints. In Robert Grossman, Roberto J. Bayardo, and Kristin P. Bennett, editors, Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Chicago, Illinois, USA, August 21-24, 2005, pages 324-333. ACM, 2005. URL: https://doi.org/10.1145/1081870.1081908.
- Long Yuan, Lu Qin, Xuemin Lin, Lijun Chang, and Wenjie Zhang. I/O efficient ECC graph decomposition via graph reduction. Proc. VLDB Endow., 9(7):516-527, 2016. URL: https://doi.org/10.14778/2904483.2904484.
- Rui Zhou, Chengfei Liu, Jeffrey Xu Yu, Weifa Liang, Baichen Chen, and Jianxin Li. Finding maximal k-edge-connected subgraphs from a large graph. In Elke A. Rundensteiner, Volker Markl, Ioana Manolescu, Sihem Amer-Yahia, Felix Naumann, and Ismail Ari, editors, 15th International Conference on Extending Database Technology, EDBT '12, Berlin, Germany, March 27-30, 2012, Proceedings, pages 480-491. ACM, 2012. URL: https://doi.org/10.1145/2247596.2247652.