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.

We provide the following new results on maximal k-edge-connected subgraphs of undirected graphs. (1) A general framework for maintaining the maximal k-edge-connected subgraphs upon insertions of edges or vertices, by successively partitioning the graph into its k-edge-connected components. This defines a decomposition tree, which can be maintained by using algorithms for the incremental maintenance of the k-edge-connected components as black boxes at every level of the tree. As a concrete application of this framework, we provide two algorithms for the incremental maintenance of the maximal 3-edge-connected subgraphs. These algorithms allow for vertex and edge insertions, interspersed with queries asking whether two vertices belong to the same maximal 3-edge-connected subgraph, and there is a trade-off between their time-and space-complexity. Specifically, the first algorithm has O (m alpha (m, n) + n2 log2 n) total running time and uses O(n) space, where m is the number of edge insertions and queries, and n is the total number of vertices inserted starting from an empty graph. The second algorithm performs the same operations in faster O (m alpha (m, n) +n2 alpha (n, n)) time in total, using O(n2) space. (2) We provide efficient constructions of (almost) sparse spanning subgraphs that have the same maximal k-edge-connected subgraphs as the original graph. We refer to such subgraphs as k-certificates. We use those certificates to speed up the computation of the maximal k-edge-connected subgraphs in the static and the fully-dynamic setting. (3) Finally, we give a simple reduction for computing the maximal k-edge-connected subgraphs to a fully dynamic mincut algorithm. (c) 2026 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).

The notions of edge-cuts and \( k \) -edge-connected components are fundamental in graph theory with numerous practical applications. Very recently, the first linear-time algorithms for computing all the 3-edge-cuts and the 4-edge-connected components of a graph have been introduced. In this article, we present carefully engineered implementations of these algorithms and evaluate their efficiency in practice, by performing a thorough empirical study using both real-world graphs taken from a variety of application areas, as well as artificial graphs. To the best of our knowledge, this is the first experimental study for these problems, which highlights the merits and weaknesses of each technique. Furthermore, we present an improved algorithm for computing the 4-edge-connected components of an undirected graph in linear time. The new algorithm uses only elementary data structures, and is implementable in the pointer-machine model of computation.

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. We 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.

We present an optimal oracle for answering connectivity queries in undirected graphs in the presence of at most three vertex failures. Specifically, we show that we can process a graph $G$ in $O(n+m)$ time, in order to build a data structure that occupies $O(n)$ space, which can be used in order to answer queries of the form "given a set $F$ of at most three vertices, and two vertices $x$ and $y$ not in $F$, are $x$ and $y$ connected in $G\setminus F$?" in constant time, where $n$ and $m$ denote the number of vertices and edges, respectively, of $G$. The idea is to rely on the DFS-based framework introduced by Kosinas [ESA'23], for handling connectivity queries in the presence of multiple vertex failures. Our technical contribution is to show how to appropriately extend the toolkit of the DFS-based parameters, in order to optimally handle up to three vertex failures. Our approach has the interesting property that it does not rely on a compact representation of vertex cuts, and has the potential to provide optimal solutions for more vertex failures. Furthermore, we show that the DFS-based framework can be easily extended in order to answer vertex-cut queries, and the number of connected components in the presence of multiple vertex failures. In the case of three vertex failures, we can answer such queries in $O(\log n)$ time.

We study the problem of efficiently answering strong connectivity queries under two vertex failures. Given a directed graph G with n vertices, we provide a data structure with O(nh) space and O(h) query time, where h is the height of a decomposition tree of G into strongly connected subgraphs. This immediately implies data structures with O(n log n) space and O(log n) query time for graphs of constant treewidth, and O(n3/2) space and O(√n) query time for planar graphs. For general directed graphs, we give a refined version of our data structure that achieves O(n√m) space and O(√m) query time, where m is the number of edges of the graph. We also provide some simple BFS-based heuristics that seem to work remarkably well in practice. In the experimental part, we first evaluate various methods to construct a decomposition tree with small height h in practice. Then we provide efficient implementations of our data structures, and evaluate their empirical performance by conducting an extensive experimental study on graphs taken from real-world applications. * The full version of the paper can be accessed at https://arxiv.org/abs/2311.00854. Research supported by the Hellenic Foundation for Research and Innovation (H.F.R.I.) under the “First Call for H.F.R.I. Research Projects to support Faculty members and Researchers and the procurement of high-cost research equipment grant”, Project FANTA (eFficient Algorithms for NeTwork Analysis), number HFRI-FM17-431.

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.

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$\tilde{O}(m\sqrt{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(m\log 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\leq 2$, that separates them.

We provide a deterministic algorithm for computing the 5-edge-connected components of an undirected multigraph in linear time. There were probably good indications that this computation can be performed in linear time, but no such algorithm was actually known prior to this work. Thus, our paper answers a theoretical question, and sheds light on the possibility that a solution may exist for general k. Furthermore, although the algorithm that we provide is quite extensive and broken up into several pieces, it can have an almost-linear time implementation with the use of elementary data structures. A key component in our algorithm is an oracle for answering connectivity queries for pairs of vertices in the presence of at most four edge-failures. Specifically, the oracle has size O(n), it can be constructed in linear time, and it answers connectivity queries in the presence of at most four edge-failures in O(1) time, where n denotes the number of vertices of the graph. We note that this is a result of independent interest.

We revisit once more the problem of designing an oracle for answering connectivity queries in undirected graphs in the presence of vertex failures. Specifically, given an undirected graph $G$ with $n$ vertices and $m$ edges and an integer $d_{\star}\ll n$, the goal is to preprocess the graph in order to construct a data structure $\mathcal{D}$ such that, given a set of vertices $F$ with $|F|=d\leq d_{\star}$, we can derive an oracle from $\mathcal{D}$ that can efficiently answer queries of the form ''is $x$ connected with $y$ in $G\setminus F$?''. Very recently, Long and Saranurak (FOCS 2022) provided a solution to this problem that is almost optimal with respect to the preprocessing time, the space usage, the update time, and the query time. However, their solution is highly complicated, and it seems very difficult to be implemented efficiently. Furthermore, it does not settle the complexity of the problem in the regime where $d_{\star}$ is a constant. Here, we provide a much simpler solution to this problem, that uses only textbook data structures. Our algorithm is deterministic, it has preprocessing time and space complexity $O(d_{\star}m\log n)$, update time $O(d^4 \log n)$, and query time $O(d)$. These bounds compare very well with the previous best, especially considering the simplicity of our approach. In fact, if we assume that $d_{\star}$ is a constant ($d_{\star}\geq 4$), then our algorithm provides some trade-offs that improve the state of the art in some respects. Finally, the data structure that we provide is flexible with respect to $d_{\star}$: it can be adapted to increases and decreases, in time and space that are almost proportional to the change in $d_{\star}$ and the size of the graph.

International audience

We present the first linear-time algorithm that computes the $4$-edge-connected components of an undirected graph. Hence, we also obtain the first linear-time algorithm for testing $4$-edge connectivity. Our results are based on a linear-time algorithm that computes the $3$-edge cuts of a $3$-edge-connected graph $G$, and a linear-time procedure that, given the collection of all $3$-edge cuts, partitions the vertices of $G$ into the $4$-edge-connected components.

Let $G=(V,E)$ be a twinless strongly connected graph. a vertex $v\in V$ is a twinless articulation point if the subrgraph obtained from $G$ by removing the vertex $v$ is not twinless strongly connected. An edge $e\in E$ is a twinless bridge if the subgraph obtained from $G$ by deleting $e$ is not twiless strongly connected graph. In this paper we study twinless articulation points and twinless bridges. We also study the problem of finding a minimum cardinality edge subset $E_{1} \subseteq E$ such that the subgraph $(V,E_{1})$ is twinless strongly connected. Moreover, we present an algorithm for computing the $2$-vertex-twinless connected components of $G$.

A directed graph $G=(V,E)$ is twinless strongly connected if it contains a strongly connected spanning subgraph without any pair of antiparallel (or twin) edges. The twinless strongly connected components (TSCCs) of a directed graph $G$ are its maximal twinless strongly connected subgraphs. These concepts have several diverse applications, such as the design of telecommunication networks and the structural stability of buildings. A vertex $v \in V$ is a twinless strong articulation point of $G$ if the deletion of $v$ increases the number of TSCCs of $G$. Here, we present the first linear-time algorithm that finds all the twinless strong articulation points of a directed graph. We show that the computation of twinless strong articulation points reduces to the following problem in undirected graphs, which may be of independent interest: Given a $2$-vertex-connected (biconnected) undirected graph $H$, find all vertices $v$ that belong to a vertex-edge cut-pair, i.e., for which there exists an edge $e$ such that $H \setminus \{v,e\}$ is not connected. We develop a linear-time algorithm that not only finds all such vertices $v$, but also computes the number of edges $e$ such that $H \setminus \{v,e\}$ is not connected. This also implies that for each twinless strong articulation point $v$ which is not a strong articulation point in a strongly connected digraph $G$, we can compute the number of TSCCs in $G \setminus v$. We note that the problem of computing all vertices that belong to a vertex-edge cut-pair can be solved in linear-time by exploiting the structure of $3$-vertex-connected (triconnected) components of $H$, represented by an SPQR tree of $H$. Our approach, however, is conceptually simple, and thus likely to be more amenable to practical implementations.