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.

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.

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 present an Õ(m3/2) time randomized (Monte Carlo) algorithm for computing the 3-edge-connected components of a digraph with m edges and n vertices. This constitutes the first improvement since the algorithm of Nagamochi & Watanabe from 1993, which runs in O(m · n) time. Thus, our algorithm is the first that overcomes the run-time of O(n) computations of 3-bounded max-flows (that is, computations of the value min{Flow(s,t), 3} for O(n) pairs s-t). Our algorithm involves a combination of known and new techniques together with new structural insights on the interactions between directed min-cuts. One novel aspect that we introduce is an efficient graph operation G for replacing a set of vertices S that is disconnected from V\S by an edge-cut of size 2 (2-out set), with a gadget of small size that preserves the pairwise connectivity among the vertices of V\S. Another main ingredient of our approach is an extension of the framework for computing the vertex-connectivity (or edge-connectivity) in a digraph [Nanongkai et al., STOC'19]. This extension allows us to efficiently identify either all small 2-out sets of vertices, or identify enough 2-out sets whose total internal volume is a constant fraction of the edges of the graph. Repeatedly replacing each identified 2-out set S with a small gadget (using the G and G operations) either shrinks the size of the graph by a constant fraction, or concludes that no small 2-out set exists. We believe that our techniques may be of independent interest. Finally, we augment our algorithm with a data structure that can report in constant time the edges of some edge-cut of size at most 2 that disconnects any two query vertices u,v, or report in constant time that no such edge-cut exists.

International audience

Let G = (V, E) be a strongly connected directed graph. The edge connectivity λ of G is the minimum number of edges whose deletion leaves a graph that is not strongly connected. Computing the edge connectivity of a graph is a classical subject in graph theory, and is an important notion in several application areas, such as transportation, communication, production, scheduling, and power engineering. In this paper we explore the design space of efficient algorithms for computing the edge connectivity of a directed graph in practice. In particular, we present efficient implementations of Gabow's algorithm, which is based on matroid intersection and packing spanning trees, as well as algorithms based on recent “local search” algorithms for minimum-cut. We conduct a thorough empirical study to highlight the merits and weaknesses of each technique.

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.

In this paper, we investigate some basic connectivity problems in directed graphs (digraphs). Let $G$ be a digraph with $m$ edges and $n$ vertices, and let $G\setminus e$ (resp., $G\setminus v$) be the digraph obtained after deleting edge $e$ (resp., vertex $v$) from $G$. As a first result, we show how to compute in $O(m+n)$ worst-case time: the total number of strongly connected components in $G\setminus e$ (resp., $G\setminus v$) for all edges $e$ (resp., for all vertices $v$) in $G$. Let $G$ be strongly connected. We say that edge $e$ (resp., vertex $v$) separates two vertices $x$ and $y$ if $x$ and $y$ are no longer strongly connected in $G\setminus e$ (resp., $G\setminus v$). As a second set of results, we show how to build in $O(m+n)$ time $O(n)$-space data structures that can answer in optimal time the following basic connectivity queries on digraphs: report in $O(n)$ worst-case time all the strongly connected components of $G\setminus e$ (resp., $G\setminus v$) for a query edge $e$ (resp., vertex $v$); test whether an edge or a vertex separates two query vertices in $O(1)$ worst-case time; report all edges (resp., vertices) that separate two query vertices in optimal worst-case time, i.e., in time $O(k)$, where $k$ is the number of separating edges (resp., separating vertices). (For $k=0$, the time is $O(1).$) All our bounds are tight and are obtained with a common algorithmic framework, based on a novel compact representation of the decompositions induced by the 1-connectivity (i.e., 1-edge and 1-vertex) cuts in digraphs, which might be of independent interest. With the help of our data structures we can design efficient algorithms for several other connectivity problems on digraphs and we can also obtain in linear time a strongly connected spanning subgraph of $G$ with $O(n)$ edges that maintains the 1-connectivity cuts of $G$ and the decompositions induced by those cuts.

The All-Pairs Min-Cut problem (aka All-Pairs Max-Flow) asks to compute a minimum s-t cut (or just its value) for all pairs of vertices s, t. We study this problem in directed graphs with unit edge/vertex capacities (corresponding to edge/vertex connectivity). Our focus is on the k-bounded case, where the algorithm has to find all pairs with min-cut value less than k, and report only those. The most basic case k = 1 is the Transitive Closure (TC) problem, which can be solved in graphs with n vertices and m edges in time O(mn) combinatorially, and in time O(nω) where ω < 2.38 is the matrix-multiplication exponent. These time bounds are conjectured to be optimal. We present new algorithms and conditional lower bounds that advance the frontier for larger k, as follows: A randomized algorithm for vertex capacities that runs in time O((nk)ω). This is only a factor kω away from the TC bound, and nearly matches it for all k = no(1). Two deterministic algorithms for edge capacities (which is more general) that work in DAGs and further reports a minimum cut for each pair. The first algorithm is combinatorial (does not involve matrix multiplication) and runs in time O(2O(k2) · mn). The second algorithm can be faster on dense DAGs and runs in time O((k log n)4k+o(k) · nω). Previously, Georgiadis et al. [ICALP 2017], could match the TC bound (up to no(1) factors) only when k = 2, and now our two algorithms match it for all k = o(√log n) and k = o(log log n). The first super-cubic lower bound of nω−1−o(1)k2 time under the 4-Clique conjecture, which holds even in the simplest case of DAGs with unit vertex capacities. It improves on the previous (SETH-based) lower bounds even in the unbounded setting k = n. For combinatorial algorithms, our reduction implies an n2−o(1)k2 conditional lower bound. Thus, we identify new settings where the complexity of the problem is (conditionally) higher than that of TC. Our three sets of results are obtained via different techniques. The first one adapts the network coding method of Cheung, Lau, and Leung [SICOMP 2013] to vertex-capacitated digraphs. The second set exploits new insights on the structure of latest cuts together with suitable algebraic tools. The lower bounds arise from a novel reduction of a different structure than the SETH-based constructions.

Motivated by very recent work on 2-connectivity in directed graphs, we revisit the problem of computing the 2-edge- and 2-vertex-connected components, and the maximal 2-edge- and 2-vertex-connected subgraphs of a directed graph G. We explore the design space for efficient algorithms in practice, based on recently proposed techniques, and conduct a thorough empirical study to highlight the merits and weaknesses of each technique.

We consider the critical node detection problem (CNDP) in directed graphs. Given a directed graph G and a parameter k, we wish to remove a subset S of at most k vertices of G such that the residual graph G ﹨ S has minimum pairwise strong connectivity. This problem is NP-hard, and thus we are interested in practical heuristics. We present a sophisticated linear-time algorithm for the k = 1 case, and, based on this algorithm, give an efficient heuristic for the general case. Then, we conduct a thorough experimental evaluation of various heuristics for CNDP. Our experimental results suggest that our heuristic performs very well in practice, both in terms of running time and of solution quality.

In the 2-reachability problem we are given a directed graph G and we wish to determine if there are two (edge or vertex) disjoint paths from u to v, for given pair of vertices u and v. In this paper, we present an algorithm that computes 2-reachability information for all pairs of vertices in O(n^w log n) time, where n is the number of vertices and w is the matrix multiplication exponent. Hence, we show that the running time of all-pairs 2-reachability is only within a log factor of transitive closure. Moreover, our algorithm produces a witness (i.e., a separating edge or a separating vertex) for all pair of vertices where 2-reachability does not hold. By processing these witnesses, we can compute all the edge- and vertex-dominator trees of G in O(n^2) additional time, which in turn enables us to answer various connectivity queries in O(1) time. For instance, we can test in constant time if there is a path from u to v avoiding an edge e, for any pair of query vertices u and v, and any query edge e, or if there is a path from u to v avoiding a vertex w, for any query vertices u, v, and w.

We introduce a new dynamic data structure for maintaining the strongly connected components (SCCs) of a directed graph (digraph) under edge deletions, so as to answer a rich repertoire of connectivity queries. Our main technical contribution is a decremental data structure that supports sensitivity queries of the form "are u and v strongly connected in the graph G \ w?", for any triple of vertices u, v, w, while G undergoes deletions of edges. Our data structure processes a sequence of edge deletions in a digraph with $n$ vertices in O(m n log n) total time and O(n^2 log n) space, where m is the number of edges before any deletion, and answers the above queries in constant time. We can leverage our data structure to obtain decremental data structures for many more types of queries within the same time and space complexity. For instance for edge-related queries, such as testing whether two query vertices u and v are strongly connected in G \ e, for some query edge e. As another important application of our decremental data structure, we provide the first nontrivial algorithm for maintaining the dominator tree of a flow graph under edge deletions. We present an algorithm that processes a sequence of edge deletions in a flow graph in O(m n log n) total time and O(n^2 log n) space. For reducible flow graphs we provide an O(mn)-time and O(m + n)-space algorithm. We give a conditional lower bound that provides evidence that these running times may be tight up to subpolynomial factors.

Let G be a directed graph (digraph) with m edges and n vertices, and let G \ e (resp., G \ v) be the digraph obtained after deleting edge e (resp., vertex v) from G. We show how to compute in O(m + n) worst-case time: The total number of strongly connected components in G \ e (resp., G \ v), for all edges e (resp., for all vertices v) in G. The size of the largest and of the smallest strongly connected components in G \ e (resp., G \ v), for all edges e (resp., for all vertices v) in G. Let G be strongly connected. We say that edge e (resp., vertex v) separates two vertices x and y, if x and y are no longer strongly connected in G \ e (resp., G \ v). We also show how to build in O(m+n) time O(n)-space data structures that can answer in optimal time the following basic connectivity queries on digraphs: Report in O(n) worst-case time all the strongly connected components of G \ e (resp., G \ v), for a query edge e (resp., vertex v). Test whether an edge or a vertex separates two query vertices in O(1) worst-case time. Report all edges (resp., vertices) that separate two query vertices in optimal worst-case time, i.e., in time O(k), where k is the number of separating edges (resp., separating vertices). (For k = 0, the time is O(1)). All our bounds are tight and are obtained with a common algorithmic framework, based on a novel compact representation of the decompositions induced by 1-edge and 1-vertex cuts in digraphs, which might be of independent interest. With the help of our data structures we can design efficient algorithms for several other connectivity problems on digraphs and we can also obtain in linear time a strongly connected spanning subgraph of G with O(n) edges that maintains the 1-connectivity cuts of G and the decompositions induced by those cuts.

Let G = (V, E) be a 2-vertex-connected directed graph with m edges and n vertices. We consider the problem of approximating the smallest 2-vertex connected spanning subgraph (2VCSS) of G, and provide new efficient algorithms for this problem based on a clever use of low-high orders. The best previously known algorithms were able to compute a 3/2-approximation in O(m n+n 2) time, or a 3-approximation faster in linear time. In this paper, we present a linear-time algorithm that achieves a better approximation ratio of 2, and another algorithm that matches the previous 3/2-approximation in O(m n + n 2 ) time. We conducted a thorough experimental evaluation of all the above algorithms on a variety of input graphs. The experimental results show that both our two new algorithms perform well in practice. In particular, in our experiments the new 3/2-approximation algorithm was always faster than the previous 3/2-approximation algorithm, while their two approximation ratios were close. On the other side, our new linear-time algorithm yielded consistently better approximation ratios than the previously known linear-time algorithm, at the price of a small overhead in the running time.

A flow graph $G=(V,E,s)$ is a directed graph with a distinguished start vertex $s$. The dominator tree $D$ of $G$ is a tree rooted at $s$, such that a vertex $v$ is an ancestor of a vertex $w$ if and only if all paths from $s$ to $w$ include $v$. The dominator tree is a central tool in program optimization and code generation and has many applications in other diverse areas including constraint programming, circuit testing, biology, and in algorithms for graph connectivity problems. A low-high order of $G$ is a preorder $δ$ of $D$ that certifies the correctness of $D$ and has further applications in connectivity and path-determination problems. In this paper, we first consider how to maintain efficiently a low-high order of a flow graph incrementally under edge insertions. We present algorithms that run in $O(mn)$ total time for a sequence of $m$ edge insertions in an initially empty flow graph with $n$ vertices.These immediately provide the first incremental certifying algorithms for maintaining the dominator tree in $O(mn)$ total time, and also imply incremental algorithms for other problems. Hence, we provide a substantial improvement over the $O(m^2)$ simple-minded algorithms, which recompute the solution from scratch after each edge insertion. We also show how to apply low-high orders to obtain a linear-time $2$-approximation algorithm for the smallest $2$-vertex-connected spanning subgraph problem (2VCSS). Finally, we present efficient implementations of our new algorithms for the incremental low-high and 2VCSS problems and conduct an extensive experimental study on real-world graphs taken from a variety of application areas. The experimental results show that our algorithms perform very well in practice.

Motivated by the emergence of large-scale networks in today's applications, we show how to compute efficiently smaller subgraphs that maintain some properties of an input graph. In particular, let G be a strongly connected directed graph. We consider the problem of computing the smallest strongly connected spanning subgraph of G that maintains certain connectivity relations of G. Specifically, for 2-edge-connectivity, we consider how to maintain the maximal 2-edge-connected subgraphs (2ECS) or the 2-edge-connected components (2ECC) of G, or both the maximal 2-edge-connected subgraphs and the 2-edge-connected components (2EC). Similarly, for 2-vertex-connectivity, we consider how to maintain the maximal 2-vertex-connected subgraphs (2VCS) or the 2-vertex-connected components (2VCC) of G, or both the maximal 2-vertex-connected subgraphs and the 2-vertex-connected components (2VC). All those problems are NP-hard, and thus we are interested in approximation algorithms. Additionally, we aim at designing algorithms with a good practical performance, so that they are able to scale effectively to very large graphs. While for 2ECS and 2VCS one can obtain an approximation ratio smaller than 2 by combining previously known results, providing good approximations for the 2-edge and the 2-vertex-components case seems more challenging. Here, we present linear-time approximation algorithms that achieve the following approximation guarantees: 4-approximation for 2ECC and 2EC, and 6-approximation for 2VCC and 2VC.

We survey some recent results on 2-edge and 2-vertex connectivity problems in directed graphs. Despite being complete analogs of the corresponding notions on undirected graphs, in digraphs 2-vertex and 2-edge connectivity have a much richer and more complicated structure. It is thus not surprising that 2-connectivity problems on directed graphs appear to be more difficult than on undirected graphs. For undirected graphs it has been known for over 40 years how to compute all bridges, articulation points, 2-edge- and 2-vertex-connected components in linear time, by simply using depth-first search. In the case of digraphs, however, the very same problems have been much more challenging and required the development of new tools and techniques.

In this paper, we initiate the study of the dynamic maintenance of $2$-edge-connectivity relationships in directed graphs. We present an algorithm that can update the $2$-edge-connected blocks of a directed graph with $n$ vertices through a sequence of $m$ edge insertions in a total of $O(mn)$ time. After each insertion, we can answer the following queries in asymptotically optimal time: (i) Test in constant time if two query vertices $v$ and $w$ are $2$-edge-connected. Moreover, if $v$ and $w$ are not $2$-edge-connected, we can produce in constant time a "witness" of this property, by exhibiting an edge that is contained in all paths from $v$ to $w$ or in all paths from $w$ to $v$. (ii) Report in $O(n)$ time all the $2$-edge-connected blocks of $G$. To the best of our knowledge, this is the first dynamic algorithm for $2$-connectivity problems on directed graphs, and it matches the best known bounds for simpler problems, such as incremental transitive closure.

Edge and vertex connectivity are fundamental concepts in graph theory. While they have been thoroughly studied in the case of undirected graphs, surprisingly, not much has been investigated for directed graphs. In this article, we study 2-edge connectivity problems in directed graphs and, in particular, we consider the computation of the following natural relation: We say that two vertices v and w are 2- edge-connected if there are two edge-disjoint paths from v to w and two edge-disjoint paths from w to v . This relation partitions the vertices into blocks such that all vertices in the same block are 2-edge-connected. Differently from the undirected case, those blocks do not correspond to the 2-edge-connected components of the graph. The main result of this article is an algorithm for computing the 2-edge-connected blocks of a directed graph in linear time. Besides being asymptotically optimal, our algorithm improves significantly over previous bounds. Once the 2-edge-connected blocks are available, we can test in constant time if two vertices are 2-edge-connected. Additionally, when two query vertices v and w are not 2-edge-connected, we can produce in constant time a “witness” of this property by exhibiting an edge that is contained in all paths from v to w or in all paths from w to v . We are also able to compute in linear time a sparse certificate for this relation, i.e., a subgraph of the input graph that has O ( n ) edges and maintains the same 2-edge-connected blocks as the input graph, where n is the number of vertices.

How does one verify that the output of a complicated program is correct? One can formally prove that the program is correct, but this may be beyond the power of existing methods. Alternatively, one can check that the output produced for a particular input satisfies the desired input--output relation by running a checker on the input--output pair. Then one only needs to prove the correctness of the checker. For some problems, however, even such a checker may be too complicated to formally verify. There is a third alternative: augment the original program to produce not only an output but also a correctness certificate , with the property that a very simple program (whose correctness is easy to prove) can use the certificate to verify that the input--output pair satisfies the desired input--output relation. We consider the following important instance of this general question: How does one verify that the dominator tree of a flow graph is correct? Existing fast algorithms for finding dominators are complicated, and even verifying the correctness of a dominator tree in the absence of additional information seems complicated. We define a correctness certificate for a dominator tree, show how to use it to easily verify the correctness of the tree, and show how to augment fast dominator-finding algorithms so that they produce a correctness certificate. We also relate the dominator certificate problem to the problem of finding divergent spanning trees in a flow graph, and we develop algorithms to find such trees. All our algorithms run in linear time. Previous algorithms apply just to the special case of only trivial dominators, and they take at least quadratic time.

note Share on Addendum to "Dominator Tree Certification and Divergent Spanning Trees" Authors: Loukas Georgiadis University of Ioannina, Ioannina, Greece University of Ioannina, Ioannina, GreeceView Profile , Robert E. Tarjan Princeton University and Intertrust Technologies, Sunnyvale, CA Princeton University and Intertrust Technologies, Sunnyvale, CAView Profile Authors Info & Claims ACM Transactions on AlgorithmsVolume 12Issue 4September 2016 Article No.: 56pp 1–3https://doi.org/10.1145/2928271Published:16 August 2016Publication History 1citation145DownloadsMetricsTotal Citations1Total Downloads145Last 12 Months4Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Graph connectivity is a fundamental concept in graph theory with numerous practical applications. Very recently, various notions of 2-connectivity in directed graphs (digraphs) have been introduced. In particular, 2-connectivity revealed to have a much richer and more complicated structure in directed graphs than in undirected graphs. In this paper we consider the computation of the 2-connected components and the 2-connected blocks of a digraph in practice, in the case of both edge and vertex connectivity. Specifically, we present efficient implementations of previously proposed and of new algorithms for computing the 2-vertex-connected components and the 2-vertex-connected blocks, the 2-edge-connected components and the 2-edge-connected blocks, and evaluate their performance experimentally on large digraphs taken from a variety of application areas. To the best of our knowledge, this is the first empirical study for these problems. Our extensive experimental study sheds light on the relative difficulty of computing these notions of 2-connectivity in digraphs in practice. Furthermore, our experimental results suggest that the 2-vertex- and 2-edge-connected components of digraphs that arise in many practical applications can be found efficiently, despite the fact that currently the best known asymptotical bound for their computation is O(mn).

Edge and vertex connectivity are fundamental concepts in graph theory. While they have been thoroughly studied in the case of undirected graphs, surprisingly not much has been investigated for directed graphs. In this paper we study 2-edge connectivity problems in directed graphs and, in particular, we consider the computation of the following natural relation: We say that two vertices v and w are 2-edge-connected if there are two edge-disjoint paths from v to w and two edge-disjoint paths from w to v. This relation partitions the vertices into blocks such that all vertices in the same block are 2-edge-connected. Differently from the undirected case, those blocks do not correspond to the 2-edge-connected components of the graph. The main result of this paper is an algorithm for computing the 2-edge-connected blocks of a directed graph in linear time. Besides being asymptotically optimal, our algorithm improves significantly over previous bounds. Once the 2-edge-connected blocks are available, we can test in constant time if two vertices are 2-edge-connected. Additionally, we also show how to compute in linear time a sparse certificate for this relation, i.e., a subgraph of the input graph that has O(n) edges and maintains the same 2-edge-connected blocks as the input graph, where n is the number of vertices.

Motivated by an application in computational geometry, we consider a novel variant of the problem of efficiently maintaining a forest of dynamic rooted trees. This variant includes an operation that merges two tree paths. In contrast to the standard problem, in which a single operation can only add or delete one arc, one merge can add and delete up to a linear number of arcs. In spite of this, we develop three different methods that need only polylogarithmic time per operation. The first method extends a solution of Farach and Thorup [1998] for the special case of paths. Each merge takes O (log 2 n ) amortized time on an n -node forest and each standard dynamic tree operation takes O (log n ) time; the latter bound is amortized, worst case, or randomized depending on the underlying data structure. For the special case that occurs in the motivating application, in which arbitrary arc deletions (cuts) do not occur, we give a method that takes O (log n ) time per operation, including merging. This is best possible in a model of computation with an Ω( n log n ) lower bound for sorting n numbers, since such sorting can be done in O ( n ) tree operations. For the even-more-special case in which there are no cuts and no parent queries, we give a method that uses standard dynamic trees as a black box: each mergeable tree operation becomes a constant number of standard dynamic tree operations. This third method can also be used in the motivating application, but only by changing the algorithm in the application. Each of our three methods needs different analytical tools and reveals different properties of dynamic trees.

We consider the problem of cross-layer resource allocation for wireless networks operating with rechargeable batteries under general arrival, channel state and recharge processes. The objective is to maximize total system utility, defined as a function of the long-term rate achieved per link, while satisfying energy and power constraints. A policy with decoupled admission control and power allocation decisions is proposed that achieves asymptotic optimality for sufficiently large battery capacity to maximum transmission power ratio (explicit bounds are provided). We present first a downlink resource allocation scenario; the analysis is then extended to multihop networks. The policy is evaluated via simulations and is seen to perform very well even in the non-asymptotic regime. This policy is particularly suitable for sensor networks, which typically satisfy the asymptotic conditions required by our methodology.

We study algorithms for the minimum mean cycle problem, a parametric version of shortest path feasibility (SPF). The three basic approaches to the problem are cycle-based, binary search, and tree-based. The first two use an SPF algorithm as a subroutine, while the latter uses a parametric approach. When implementing the SPF-based methods, one has a choice of SPF algorithms and incremental optimization strategies. There are also several ways to handle precision issues. This leads to dozens of variants, which we systematically compare. Our experimental setup is more comprehensive than in previous studies. In our experiments, the tree-based method and two implementations of the cycle-based method outperformed other approaches, including binary search.

This is an experimental study of algorithms for the shortest path feasibility problem: Given a directed weighted graph, find a negative cycle or present a short proof that none exists. We study previously known and new algorithms. Our testbed is more extensive than those previously used, including both static and incremental problems, as well as worst-case instances. We show that, while no single algorithm dominates, a small subset (including a new algorithm) has very robust performance in practice. Our work advances state of the art in the area.

We present linear-time algorithms for the classic problem of finding dominators in a flowgraph, and for several other problems whose solutions require evaluating a function defined on paths in a tree. Although all these problems had linear-time solutions previously, our algorithms are simpler, in some cases substantially. Our improvements come from three new ideas: a refined analysis of path compression that gives a linear bound if the compressions favor certain nodes; replacement of random-access table look-up by a radix sort; and a more careful partitioning of a tree into easily managed parts. In addition to finding dominators, our algorithms find nearest common ancestors off-line, verify and construct minimum spanning trees, do interval analysis of a flowgraph, and build the component tree of a weighted tree. Our algorithms do not require the power of a random-access machine; they run in linear time on a pointer machine. The genesis of our work was the discovery of a subtle error in the analysis of a previous allegedly linear-time algorithm for finding dominators. That algorithm was an attempt to simplify a more complicated algorithm, which itself was intended to correct errors in a yet earlier algorithm. Our work provides a systematic study of the subtleties in the dominators problem, the techniques needed to solve it in linear time, and the range of application of the resulting methods. We have tried to make our techniques as simple and as general as possible and to understand exactly how earlier approaches to the dominators problem were either incorrect or overly complicated.

We develop the first linear-space data structures for dynamic planar point location in general subdivisions that achieve logarithmic query time and poly-logarithmic update time