--- OA_place: publisher OA_type: gold _id: '20534' abstract: - lang: eng text: "A non-trivial minimum cut (NMC) sparsifier is a multigraph Ĝ that preserves all non-trivial minimum cuts of a given undirected graph G. We introduce a flexible data structure for fully dynamic graphs that can efficiently provide an NMC sparsifier upon request at any point during the sequence of updates. We employ simple dynamic forest data structures to achieve a fast from-scratch construction of the sparsifier at query time. Based on the strength of the adversary and desired type of time bounds, the data structure comes with different guarantees. Specifically, let G be a fully dynamic simple graph with n vertices and minimum degree δ. Then our data structure supports an insertion/deletion of an edge to/from G in n^o(1) worst-case time. Furthermore, upon request, it can return w.h.p. an NMC sparsifier of G that has O(n/δ) vertices and O(n) edges, in Ô(n) time. The probabilistic guarantees hold against an adaptive adversary. Alternatively, the update and query times can be improved to Õ(1) and Õ(n) respectively, if amortized-time guarantees are sufficient, or if the adversary is oblivious. Throughout the paper, we use Õ to hide polylogarithmic factors and Ô to hide subpolynomial (i.e., n^o(1)) factors.\r\nWe discuss two applications of our new data structure. First, it can be used to efficiently report a cactus representation of all minimum cuts of a fully dynamic simple graph. Building this cactus for the NMC sparsifier instead of the original graph allows for a construction time that is sublinear in the number of edges. Against an adaptive adversary, we can with high probability output the cactus representation in worst-case Ô(n) time. Second, our data structure allows us to efficiently compute the maximal k-edge-connected subgraphs of undirected simple graphs, by repeatedly applying a minimum cut algorithm on the NMC sparsifier. Specifically, we can compute with high probability the maximal k-edge-connected subgraphs of a simple graph with n vertices and m edges in Õ(m+n²/k) time. This improves the best known time bounds for k = Ω(n^{1/8}) and naturally extends to the case of fully dynamic graphs." acknowledgement: 'Monika Henzinger and Evangelos Kosinas: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (MoDynStruct, No. 101019564) and the Austrian Science Fund (FWF) grant https://www.doi.org/10.55776/Z422 and grant https://www.doi.org/10.55776/I5982. Harald Räcke and Robin Münk: This project has received funding from the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – 498605858.' article_number: '36' article_processing_charge: No arxiv: 1 author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Evangelos full_name: Kosinas, Evangelos id: 4c7f9625-dbbc-11ee-9d86-bdcc2db5a949 last_name: Kosinas - first_name: Robin full_name: Münk, Robin last_name: Münk - first_name: Harald full_name: Räcke, Harald last_name: Räcke citation: ama: 'Henzinger M, Kosinas E, Münk R, Räcke H. Efficient contractions of dynamic graphs - with applications. In: 33rd Annual European Symposium on Algorithms. Vol 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.ESA.2025.36' apa: 'Henzinger, M., Kosinas, E., Münk, R., & Räcke, H. (2025). Efficient contractions of dynamic graphs - with applications. In 33rd Annual European Symposium on Algorithms (Vol. 351). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2025.36' chicago: Henzinger, Monika, Evangelos Kosinas, Robin Münk, and Harald Räcke. “Efficient Contractions of Dynamic Graphs - with Applications.” In 33rd Annual European Symposium on Algorithms, Vol. 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.ESA.2025.36. ieee: M. Henzinger, E. Kosinas, R. Münk, and H. Räcke, “Efficient contractions of dynamic graphs - with applications,” in 33rd Annual European Symposium on Algorithms, Warsaw, Poland, 2025, vol. 351. ista: 'Henzinger M, Kosinas E, Münk R, Räcke H. 2025. Efficient contractions of dynamic graphs - with applications. 33rd Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms vol. 351, 36.' mla: Henzinger, Monika, et al. “Efficient Contractions of Dynamic Graphs - with Applications.” 33rd Annual European Symposium on Algorithms, vol. 351, 36, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.ESA.2025.36. short: M. Henzinger, E. Kosinas, R. Münk, H. Räcke, in:, 33rd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. conference: end_date: 2025-09-17 location: Warsaw, Poland name: 'ESA: European Symposium on Algorithms' start_date: 2025-09-15 corr_author: '1' date_created: 2025-10-26T23:01:34Z date_published: 2025-10-01T00:00:00Z date_updated: 2025-10-27T08:05:46Z day: '01' ddc: - '000' department: - _id: MoHe doi: 10.4230/LIPIcs.ESA.2025.36 ec_funded: 1 external_id: arxiv: - '2509.05157' file: - access_level: open_access checksum: d2daf9a467e96fb5e7084a8a85321776 content_type: application/pdf creator: dernst date_created: 2025-10-27T08:03:36Z date_updated: 2025-10-27T08:03:36Z file_id: '20542' file_name: 2025_LIPIcs.ESA_HenzingerM.pdf file_size: 934846 relation: main_file success: 1 file_date_updated: 2025-10-27T08:03:36Z has_accepted_license: '1' intvolume: ' 351' language: - iso: eng month: '10' oa: 1 oa_version: Published Version project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' name: The design and evaluation of modern fully dynamic data structures - _id: 34def286-11ca-11ed-8bc3-da5948e1613c grant_number: Z00422 name: Efficient algorithms - _id: bda196b2-d553-11ed-ba76-8e8ee6c21103 grant_number: I05982 name: Static and Dynamic Hierarchical Graph Decompositions publication: 33rd Annual European Symposium on Algorithms publication_identifier: isbn: - '9783959773959' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Efficient contractions of dynamic graphs - with applications tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 351 year: '2025' ... --- OA_type: closed access _id: '18922' abstract: - lang: eng text: 'Let G be a directed graph with m edges and n vertices. We present a deterministic linear-time algorithm for computing the 3-edge-connected components of G. This is a significant improvement over the previous best bound by Georgiadis et al. [SODA 2023], which is Õ(m√{m}) and randomized. Our result is based on a novel characterization of 2-edge cuts in directed graphs and on a new technique that exploits the concept of divergent spanning trees and 2-connectivity-light graphs, and requires a careful modification of the minset-poset technique of Gabow [TALG 2016]. As a side result, our new technique yields also an oracle for providing in constant time a minimum edge-cut for any two vertices that are not 3-edge-connected. The oracle uses space O(n) and can be built in O(mlog n) time: given two query vertices, it determines in constant time whether they are 3-edge-connected, or provides a k-edge cut, with k≤ 2, that separates them.' acknowledgement: "Giuseppe F. Italiano was partially supported by the Italian Ministry of\r\nUniversity and Reseach under PRIN Project n. 2022TS4Y3N - EXPAND: scalable algorithms for EXPloratory Analyses of heterogeneous and dynamic Networked Data.\r\n" article_processing_charge: No author: - first_name: Loukas full_name: Georgiadis, Loukas last_name: Georgiadis - first_name: Giuseppe F. full_name: Italiano, Giuseppe F. last_name: Italiano - first_name: Evangelos full_name: Kosinas, Evangelos id: 4c7f9625-dbbc-11ee-9d86-bdcc2db5a949 last_name: Kosinas citation: ama: 'Georgiadis L, Italiano GF, Kosinas E. Computing the 3-edge-connected components of directed graphs in linear time. In: 65th Annual Symposium on Foundations of Computer Science. IEEE; 2024:62-85. doi:10.1109/focs61266.2024.00015' apa: 'Georgiadis, L., Italiano, G. F., & Kosinas, E. (2024). Computing the 3-edge-connected components of directed graphs in linear time. In 65th Annual Symposium on Foundations of Computer Science (pp. 62–85). Chicago, IL, United States: IEEE. https://doi.org/10.1109/focs61266.2024.00015' chicago: Georgiadis, Loukas, Giuseppe F. Italiano, and Evangelos Kosinas. “Computing the 3-Edge-Connected Components of Directed Graphs in Linear Time.” In 65th Annual Symposium on Foundations of Computer Science, 62–85. IEEE, 2024. https://doi.org/10.1109/focs61266.2024.00015. ieee: L. Georgiadis, G. F. Italiano, and E. Kosinas, “Computing the 3-edge-connected components of directed graphs in linear time,” in 65th Annual Symposium on Foundations of Computer Science, Chicago, IL, United States, 2024, pp. 62–85. ista: 'Georgiadis L, Italiano GF, Kosinas E. 2024. Computing the 3-edge-connected components of directed graphs in linear time. 65th Annual Symposium on Foundations of Computer Science. FOCS: Foundations of Computer Science, 62–85.' mla: Georgiadis, Loukas, et al. “Computing the 3-Edge-Connected Components of Directed Graphs in Linear Time.” 65th Annual Symposium on Foundations of Computer Science, IEEE, 2024, pp. 62–85, doi:10.1109/focs61266.2024.00015. short: L. Georgiadis, G.F. Italiano, E. Kosinas, in:, 65th Annual Symposium on Foundations of Computer Science, IEEE, 2024, pp. 62–85. conference: end_date: 2024-10-30 location: Chicago, IL, United States name: 'FOCS: Foundations of Computer Science' start_date: 2024-10-27 corr_author: '1' date_created: 2025-01-27T14:50:23Z date_published: 2024-10-01T00:00:00Z date_updated: 2025-09-09T12:08:47Z day: '01' department: - _id: MoHe doi: 10.1109/focs61266.2024.00015 external_id: isi: - '001419526400005' isi: 1 language: - iso: eng month: '10' oa_version: None page: 62-85 publication: 65th Annual Symposium on Foundations of Computer Science publication_identifier: isbn: - '9798331516741' publication_status: published publisher: IEEE quality_controlled: '1' scopus_import: '1' status: public title: Computing the 3-edge-connected components of directed graphs in linear time type: conference user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345 year: '2024' ... --- OA_place: publisher OA_type: gold _id: '18309' abstract: - lang: eng text: 'The problem of designing connectivity oracles supporting vertex failures is one of the basic data structures problems for undirected graphs. It is already well understood: previous works [Duan-Pettie STOC''10; Long-Saranurak FOCS''22] achieve query time linear in the number of failed vertices, and it is conditionally optimal as long as we require preprocessing time polynomial in the size of the graph and update time polynomial in the number of failed vertices. We revisit this problem in the paradigm of algorithms with predictions: we ask if the query time can be improved if the set of failed vertices can be predicted beforehand up to a small number of errors. More specifically, we design a data structure that, given a graph G = (V,E) and a set of vertices predicted to fail D̂ ⊆ V of size d = |D̂|, preprocesses it in time Õ(d|E|) and then can receive an update given as the symmetric difference between the predicted and the actual set of failed vertices D̂△D = (D̂ ⧵ D) ∪ (D ⧵ D̂) of size η = |D̂△D|, process it in time Õ(η⁴), and after that answer connectivity queries in G ⧵ D in time O(η). Viewed from another perspective, our data structure provides an improvement over the state of the art for the fully dynamic subgraph connectivity problem in the sensitivity setting [Henzinger-Neumann ESA''16]. We argue that the preprocessing time and query time of our data structure are conditionally optimal under standard fine-grained complexity assumptions.' acknowledgement: "Part of this work was done when Evangelos Kosinas was at University of Ioannina and Adam Polak was at Max Planck Institute of Informatics.\r\n" alternative_title: - LIPIcs article_number: '72' article_processing_charge: Yes arxiv: 1 author: - first_name: Bingbing full_name: Hu, Bingbing last_name: Hu - first_name: Evangelos full_name: Kosinas, Evangelos id: 4c7f9625-dbbc-11ee-9d86-bdcc2db5a949 last_name: Kosinas - first_name: Adam full_name: Polak, Adam last_name: Polak citation: ama: 'Hu B, Kosinas E, Polak A. Connectivity oracles for predictable vertex failures. In: 32nd Annual European Symposium on Algorithms. Vol 308. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.ESA.2024.72' apa: 'Hu, B., Kosinas, E., & Polak, A. (2024). Connectivity oracles for predictable vertex failures. In 32nd Annual European Symposium on Algorithms (Vol. 308). London, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2024.72' chicago: Hu, Bingbing, Evangelos Kosinas, and Adam Polak. “Connectivity Oracles for Predictable Vertex Failures.” In 32nd Annual European Symposium on Algorithms, Vol. 308. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.ESA.2024.72. ieee: B. Hu, E. Kosinas, and A. Polak, “Connectivity oracles for predictable vertex failures,” in 32nd Annual European Symposium on Algorithms, London, United Kingdom, 2024, vol. 308. ista: 'Hu B, Kosinas E, Polak A. 2024. Connectivity oracles for predictable vertex failures. 32nd Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 308, 72.' mla: Hu, Bingbing, et al. “Connectivity Oracles for Predictable Vertex Failures.” 32nd Annual European Symposium on Algorithms, vol. 308, 72, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.ESA.2024.72. short: B. Hu, E. Kosinas, A. Polak, in:, 32nd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. conference: end_date: 2024-09-04 location: London, United Kingdom name: 'ESA: European Symposium on Algorithms' start_date: 2024-09-02 corr_author: '1' date_created: 2024-10-13T22:01:50Z date_published: 2024-09-01T00:00:00Z date_updated: 2025-12-02T13:49:52Z day: '01' ddc: - '000' department: - _id: MoHe doi: 10.4230/LIPIcs.ESA.2024.72 external_id: arxiv: - '2312.08489' isi: - '001545622400072' file: - access_level: open_access checksum: ab1f2f9161549a8763eda15db40e022c content_type: application/pdf creator: dernst date_created: 2024-10-21T10:03:48Z date_updated: 2024-10-21T10:03:48Z file_id: '18455' file_name: 2024_LIPICs_Hu.pdf file_size: 853914 relation: main_file success: 1 file_date_updated: 2024-10-21T10:03:48Z has_accepted_license: '1' intvolume: ' 308' isi: 1 language: - iso: eng month: '09' oa: 1 oa_version: Published Version publication: 32nd Annual European Symposium on Algorithms publication_identifier: isbn: - '9783959773386' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Connectivity oracles for predictable vertex failures tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 308 year: '2024' ...