2026-09-08T01:21:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26484 2026-09-05T19:45:12Z ddc:004 open_access

Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time Georgiadis, Loukas Kipouridis, Evangelos Kosinas, Evangelos Papadopoulos, Charis Parotsidis, Nikos Graph connectivity edge-connected components directed edge-cuts Computing edge-connected components in directed and undirected graphs is a fundamental and well-studied problem in graph algorithms. In a very recent breakthrough, Korhonen [STOC 2025] showed that for any fixed k, the k-edge connected components of an undirected graph can be computed in linear time. In contrast, the directed case remains significantly more challenging: linear-time algorithms are only known for k ≤ 3, and for any fixed k > 3, the best known bound for sparse or moderately dense graphs is still the O(mn)-time algorithm of Nagamochi and Watanabe (1993). In this paper, we break the O(mn) barrier for all k = o(n^{1/4}/√{log{n}}). We present a randomized algorithm that computes the (k+2)-edge-connected components of a k-edge-connected directed graph in O(k² m √n log n) time, for any k. This constitutes the first improvement over the classic Nagamochi-Watanabe bound for any constant k > 3. Our approach introduces new structural insights into directed edge-cuts and combines these with both new and existing techniques. A central contribution of our work is a substantial simplification and generalization of the framework introduced in [Loukas Georgiadis et al., 2023], which achieved an Õ(m√m) bound for computing the 3-edge-connected components of a digraph. In addition, we develop a variant of our algorithm that achieves the same O(m √n log n) running time for computing the 4-edge-connected components of a general directed graph. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Loukas Georgiadis and Evangelos Kipouridis and Evangelos Kosinas and Charis Papadopoulos and Nikos Parotsidis 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.95 urn:nbn:de:0030-drops-264846 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.95 eng https://creativecommons.org/licenses/by/4.0/legalcode