{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T04:41:49Z","timestamp":1773895309448,"version":"3.50.1"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,2]]},"abstract":"<jats:p>Real-world directed graphs are dynamically changing, and it is important to identify and maintain the strong connectivity information between nodes, which is useful in numerous applications. Given an input graph<jats:italic>G<\/jats:italic>, we study a new problem,<jats:italic>minimum strongly connected subgraph collection<\/jats:italic>(MSCSC), which asks for a complete collection of subgraphs, each of which contains a<jats:italic>maximal<\/jats:italic>set of nodes that are strongly connected to each other via<jats:italic>minimum<\/jats:italic>number of edges in<jats:italic>G.<\/jats:italic><\/jats:p><jats:p>MSCSC is NP-hard, and its computation and maintenance are challenging, especially on large-scale dynamic graphs. Thus, we resort to approximate MSCSC with theoretical guarantees. We develop a series of approximate MSCSC methods for both static and dynamic graphs. Specifically, we first develop a static MSCSC method MSC that only needs one scan of the graph<jats:italic>G<\/jats:italic>, runs in linear time<jats:italic>w.r.t.<\/jats:italic>, the number of edges, and provides rigorous approximation guarantees. Then, based on MSC, we leverage a reduced directed acyclic graph of<jats:italic>G<\/jats:italic>to design incremental MSCSC method MSC<jats:sup>i<\/jats:sup>with two variants to handle edge insertions efficiently. We further develop MSC<jats:sup>d<\/jats:sup>that updates MSCSC under edge deletions by efficiently scanning only locally affected subgraphs. Moreover, to demonstrate the high utility, we conduct two use case studies to apply our MSCSC methods to boost the efficiency of dynamic strongly connected component (SCC) maintenance and dynamic SCC-based reachability index maintenance. Extensive experiments on 8 large graphs, including 3 billion-edge graphs, validate the superior efficiency of our methods.<\/jats:p>","DOI":"10.14778\/3648160.3648173","type":"journal-article","created":{"date-parts":[[2024,5,3]],"date-time":"2024-05-03T21:52:53Z","timestamp":1714773173000},"page":"1324-1336","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Minimum Strongly Connected Subgraph Collection in Dynamic Graphs"],"prefix":"10.14778","volume":"17","author":[{"given":"Xin","family":"Chen","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong"}]},{"given":"Jieming","family":"Shi","sequence":"additional","affiliation":[{"name":"Hong Kong Polytechnic University"}]},{"given":"You","family":"Peng","sequence":"additional","affiliation":[{"name":"The University of New South Wales"}]},{"given":"Wenqing","family":"Lin","sequence":"additional","affiliation":[{"name":"Tencent"}]},{"given":"Sibo","family":"Wang","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}]},{"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"The University of New South Wales"}]}],"member":"320","published-online":{"date-parts":[[2024,5,3]]},"reference":[{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Amir Abboud and Virginia Vassilevska Williams. 2014. Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems. In FOCS. 434--443.","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Rakesh Agrawal Alexander Borgida and H. V. Jagadish. 1989. Efficient Management of Transitive Relationships in Large Data and Knowledge Bases. In SIGMOD. 253--262.","DOI":"10.1145\/66926.66950"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2009.10.032"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2756553","article-title":"A new approach to incremental cycle detection and related problems","volume":"12","author":"Bender Michael A","year":"2015","unstructured":"Michael A Bender, Jeremy T Fineman, Seth Gilbert, and Robert E Tarjan. 2015. A new approach to incremental cycle detection and related problems. TALG 12, 2 (2015), 1--22.","journal-title":"TALG"},{"key":"e_1_2_1_6_1","first-page":"1","article-title":"Incremental SCC Maintenance in Sparse Graphs","volume":"14","author":"Bernstein Aaron","year":"2021","unstructured":"Aaron Bernstein, Aditi Dudeja, and Seth Pettie. 2021. Incremental SCC Maintenance in Sparse Graphs. In ESA. 14:1--14:16.","journal-title":"ESA."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Aaron Bernstein Maximilian Probst and Christian Wulff-Nilsen. 2019. Decremental strongly-connected components and single-source reachability in near-linear time. In STOC. 365--376.","DOI":"10.1145\/3313276.3316335"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Paolo Boldi and Sebastiano Vigna. 2004. The WebGraph Framework I: Compression Techniques. In WWW. 595--601.","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2009.117"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Yangjun Chen and Yibin Chen. 2008. An Efficient Algorithm for Answering Graph Reachability Queries. In ICDE. 893--902.","DOI":"10.1109\/ICDE.2008.4497498"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"James Cheng Silu Huang Huanhuan Wu and Ada Wai-Chee Fu. 2013. TF-Label: a topological-folding labeling scheme for reachability querying in a large graph. In SIGMOD. 193--204.","DOI":"10.1145\/2463676.2465286"},{"key":"e_1_2_1_12_1","first-page":"961","article-title":"Fast Computation of Reachability Labeling for Large Graphs","volume":"3896","author":"Cheng Jiefeng","year":"2006","unstructured":"Jiefeng Cheng, Jeffrey Xu Yu, Xuemin Lin, Haixun Wang, and Philip S. Yu. 2006. Fast Computation of Reachability Labeling for Large Graphs. In EDBT, Vol. 3896. 961--979.","journal-title":"EDBT"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403098"},{"key":"e_1_2_1_14_1","unstructured":"Edsger Wybe Dijkstra. 1976. A discipline of programming."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20460"},{"key":"e_1_2_1_16_1","first-page":"4","article-title":"O'Reach: Even Faster Reachability in Large Graphs","volume":"27","author":"Hanauer Kathrin","year":"2022","unstructured":"Kathrin Hanauer, Christian Schulz, and Jonathan Trummer. 2022. O'Reach: Even Faster Reachability in Large Graphs. ACM J. Exp. Algorithmics 27 (2022), 4.2:1--4.2:27.","journal-title":"ACM J. Exp. Algorithmics"},{"key":"e_1_2_1_17_1","first-page":"1","article-title":"On fast parallel detection of strongly connected components (SCC) in small-world graphs","volume":"92","author":"Hong Sungpack","year":"2013","unstructured":"Sungpack Hong, Nicole C. Rodia, and Kunle Olukotun. 2013. On fast parallel detection of strongly connected components (SCC) in small-world graphs. In SC. 92:1--92:11.","journal-title":"SC."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/99935.99944"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Ruoming Jin Hui Hong Haixun Wang Ning Ruan and Yang Xiang. 2010. Computing label-constraint reachability in graph databases. In SIGMOD. 123--134.","DOI":"10.1145\/1807167.1807183"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1929934.1929941"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556578"},{"key":"e_1_2_1_22_1","unstructured":"Ruoming Jin Yang Xiang Ning Ruan and David Fuhry. 2009. 3-HOP: a highcompression indexing scheme for reachability query. In SIGMOD. 813--826."},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Ruoming Jin Yang Xiang Ning Ruan and Haixun Wang. 2008. Efficiently answering reachability queries on very large directed graphs. In SIGMOD. 595--608.","DOI":"10.1145\/1376616.1376677"},{"key":"e_1_2_1_24_1","first-page":"1","article-title":"On Fully Dynamic Strongly Connected Components. In ESA (LIPIcs), Vol. 274","volume":"68","author":"Karczmarz Adam","year":"2023","unstructured":"Adam Karczmarz and Marcin Smulewicz. 2023. On Fully Dynamic Strongly Connected Components. In ESA (LIPIcs), Vol. 274. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 68:1--68:15.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793256685"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(95)00105-Z"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"J\u00e9r\u00f4me Kunegis. 2013. KONECT: the Koblenz network collection. In WWW. 1343--1350.","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2483699.2483707","article-title":"Improved deterministic algorithms for decremental reachability and strongly connected components","volume":"9","author":"\u0141\u0105cki Jakub","year":"2013","unstructured":"Jakub \u0141\u0105cki. 2013. Improved deterministic algorithms for decremental reachability and strongly connected components. TALG 9, 3 (2013), 1--15.","journal-title":"TALG"},{"key":"e_1_2_1_29_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_30_1","first-page":"1","article-title":"Efficient decomposition of strongly connected components on GPUs","volume":"60","author":"Li Guohui","year":"2014","unstructured":"Guohui Li, Zhe Zhu, Cong Zhang, and Fumin Yang. 2014. Efficient decomposition of strongly connected components on GPUs. JSA 60, 1 (2014), 1--10.","journal-title":"JSA"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-016-0407-z"},{"key":"e_1_2_1_32_1","volume-title":"Database Systems for Advanced Applications. DASFAA 2021 International Workshops: BDQM, GDMA, MLDLDSA, MobiSocial, and MUST, Taipei, Taiwan, April 11--14","author":"Li Wenjie","year":"2021","unstructured":"Wenjie Li, Lei Zou, Peng Peng, and Zheng Qin. 2021. NREngine: A Graph-Based Query Engine for Network Reachability. In Database Systems for Advanced Applications. DASFAA 2021 International Workshops: BDQM, GDMA, MLDLDSA, MobiSocial, and MUST, Taipei, Taiwan, April 11--14, 2021, Proceedings 26. Springer, 90--106."},{"key":"e_1_2_1_33_1","volume-title":"DBL: Efficient Reachability Queries on Dynamic Graphs. In DASFAA (Lecture Notes in Computer Science)","author":"Lyu Qiuyi","year":"2021","unstructured":"Qiuyi Lyu, Yuchen Li, Bingsheng He, and Bin Gong. 2021. DBL: Efficient Reachability Queries on Dynamic Graphs. In DASFAA (Lecture Notes in Computer Science), Vol. 12682. Springer, 761--777."},{"key":"e_1_2_1_34_1","volume-title":"Algorithms - ESA 2014 - 22th Annual European Symposium","author":"Merz Florian","year":"2014","unstructured":"Florian Merz and Peter Sanders. 2014. PReaCH: A Fast Lightweight Reachability Index Using Pruning and Contraction Hierarchies. In Algorithms - ESA 2014 - 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings (Lecture Notes in Computer Science), Andreas S. Schulz and Dorothea Wagner (Eds.), Vol. 8737. Springer, 701--712."},{"key":"e_1_2_1_35_1","volume-title":"Networks","author":"Newman Mark","unstructured":"Mark Newman. 2018. Networks. Oxford university press."},{"key":"e_1_2_1_36_1","volume-title":"IFCA: Index-Free Community-Aware Reachability Processing Over Large Dynamic Graphs","author":"Pang Yue","year":"2023","unstructured":"Yue Pang, Lei Zou, and Yu Liu. 2023. IFCA: Index-Free Community-Aware Reachability Processing Over Large Dynamic Graphs. In ICDE. IEEE, 2220--2234."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/060650271"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556573"},{"key":"e_1_2_1_39_1","unstructured":"Ralf Schenkel Anja Theobald and Gerhard Weikum. 2005. Efficient Creation and Incremental Maintenance of the HOPI Index for Complex XML Document Collections. In ICDE. 360--371."},{"key":"e_1_2_1_40_1","volume-title":"ARROW: Approximating Reachability Using Random Walks Over Web-Scale Graphs. In ICDE. 470--481.","author":"Sengupta Neha","year":"2019","unstructured":"Neha Sengupta, Amitabha Bagchi, Maya Ramanath, and Srikanta Bedathur. 2019. ARROW: Approximating Reachability Using Random Walks Over Web-Scale Graphs. In ICDE. 470--481."},{"key":"e_1_2_1_41_1","volume-title":"FERRARI: Flexible and efficient reachability range assignment for graph indexing","author":"Seufert Stephan","year":"2013","unstructured":"Stephan Seufert, Avishek Anand, Srikanta J. Bedathur, and Gerhard Weikum. 2013. FERRARI: Flexible and efficient reachability range assignment for graph indexing. In ICDE. IEEE Computer Society, 1009--1020."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(81)90008-0"},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","unstructured":"George M. Slota Sivasankaran Rajamanickam and Kamesh Madduri. 2014. BFS and Coloring-Based Parallel Algorithms for Strongly Connected Components and Related Problems. In IPDPS. 550--559.","DOI":"10.1109\/IPDPS.2014.64"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2631160"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","unstructured":"Silke Tri\u00dfl and Ulf Leser. 2007. Fast and practical indexing and querying of very large graphs. In SIGMOD. 845--856.","DOI":"10.1145\/1247480.1247573"},{"key":"e_1_2_1_47_1","volume-title":"Wagner Meira Jr., and Mohammed J. Zaki","author":"Veloso Ren\u011b Rodrigues","year":"2014","unstructured":"Ren\u011b Rodrigues Veloso, Lo\u00efc Cerf, Wagner Meira Jr., and Mohammed J. Zaki. 2014. Reachability Queries in Very Large Graphs: A Fast Refined Online Search Approach. In EDBT. OpenProceedings.org, 511--522."},{"key":"e_1_2_1_48_1","unstructured":"Adrian Vetta. 2001. Approximating the minimum strongly connected subgraph via a matching lower bound. In SODA. 417--426."},{"key":"e_1_2_1_49_1","volume-title":"Dual Labeling: Answering Graph Reachability Queries in Constant Time. In ICDE. 75.","author":"Wang Haixun","year":"2006","unstructured":"Haixun Wang, Hao He, Jun Yang, Philip S. Yu, and Jeffrey Xu Yu. 2006. Dual Labeling: Answering Graph Reachability Queries in Constant Time. In ICDE. 75."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0468-3"},{"key":"e_1_2_1_51_1","doi-asserted-by":"crossref","unstructured":"Yosuke Yano Takuya Akiba Yoichi Iwata and Yuichi Yoshida. 2013. Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths. In CIKM. 1601--1606.","DOI":"10.1145\/2505515.2505724"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920879"},{"key":"e_1_2_1_53_1","volume-title":"Zaki","author":"Yildirim Hilmi","year":"2013","unstructured":"Hilmi Yildirim, Vineet Chaoji, and Mohammed J. Zaki. 2013. DAGGER: A Scalable Index for Reachability Queries in Large Dynamic Graphs. CoRR abs\/1301.0977 (2013)."},{"key":"e_1_2_1_54_1","volume-title":"An Overview of Reachability Indexes on Graphs. In SIGMOD Conference Companion. ACM, 61--68","author":"Zhang Chao","year":"2023","unstructured":"Chao Zhang, Angela Bonifati, and M. Tamer \u00d6zsu. 2023. An Overview of Reachability Indexes on Graphs. In SIGMOD Conference Companion. ACM, 61--68."},{"key":"e_1_2_1_55_1","volume-title":"A linear time 53-approximation for the minimum strongly-connected spanning subgraph problem. Information processing letters 86, 2","author":"Zhao Liang","year":"2003","unstructured":"Liang Zhao, Hiroshi Nagamochi, and Toshihide Ibaraki. 2003. A linear time 53-approximation for the minimum strongly-connected spanning subgraph problem. Information processing letters 86, 2 (2003), 63--70."},{"key":"e_1_2_1_56_1","unstructured":"Andy Diwen Zhu Wenqing Lin Sibo Wang and Xiaokui Xiao. 2014. Reachability queries on large dynamic graphs: a total order approach. In SIGMOD. 1323--1334."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3648160.3648173","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,18]],"date-time":"2024-11-18T01:01:50Z","timestamp":1731891710000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3648160.3648173"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2]]},"references-count":55,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["10.14778\/3648160.3648173"],"URL":"https:\/\/doi.org\/10.14778\/3648160.3648173","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,2]]},"assertion":[{"value":"2024-05-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}