Loukas Georgiadis

FOCS Conference 2024 Conference Paper

Computing the 3-Edge-Connected Components of Directed Graphs in Linear Time

• Loukas Georgiadis
• Giuseppe F. Italiano
• Evangelos Kosinas

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.

SODA Conference 2023 Conference Paper

Faster Computation of 3-Edge-Connected Components in Digraphs

• Loukas Georgiadis
• Evangelos Kipouridis
• Charis Papadopoulos
• Nikos Parotsidis

We present an Õ ( m 3/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 <s> 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 <s> and G < V\S > 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.

TCS Journal 2020 Journal Article

Approximating the smallest 2-vertex connected spanning subgraph of a directed graph

• Loukas Georgiadis
• Giuseppe F. Italiano
• Aikaterini Karanasiou

We consider the problem of approximating the smallest 2-vertex connected spanning subgraph (2VCSS) of a 2-vertex connected directed graph, and provide new efficient algorithms. We provide two linear-time algorithms, the first based on a linear-time test for 2-vertex connectivity and divergent spanning trees, and the second based on low-high orders, that correspondingly give 3- and 2-approximations. Then we show that these linear-time algorithms can be combined with an algorithm of Cheriyan and Thurimella that achieves a 3/2-approximation. The combined algorithms preserve the 3/2 approximation guarantee of the Cheriyan-Thurimella algorithm and improve its running time from O ( m 2 ) to O ( m n + n 2 ), for a digraph with n vertices and m edges. Finally, we present an experimental evaluation of the above algorithms for a variety of input data. The experimental results show that our linear-time algorithms perform very well in practice. Furthermore, the experiments show that the combined algorithms not only improve the running time of the Cheriyan-Thurimella algorithm, but it may also compute a better solution.

I&C Journal 2018 Journal Article

2-vertex connectivity in directed graphs

• Loukas Georgiadis
• Giuseppe F. Italiano
• Luigi Laura
• Nikos Parotsidis

Given a directed graph, two vertices v and w are 2-vertex-connected if there are two internally vertex-disjoint paths from v to w and two internally vertex-disjoint paths from w to v. In this paper, we show how to compute this relation in O ( m + n ) time, where n is the number of vertices and m is the number of edges of the graph. As a side result, we show how to build in linear time an O ( n ) -space data structure, which can answer in constant time queries on whether any two vertices are 2-vertex-connected. Additionally, when two query vertices v and w are not 2-vertex-connected, our data structure can produce in constant time a “witness” of this property, by exhibiting a vertex or an edge that is contained in all paths from v to w or in all paths from w to v.

TCS Journal 2017 Journal Article

Sparse certificates for 2-connectivity in directed graphs

• Loukas Georgiadis
• Giuseppe F. Italiano
• Aikaterini Karanasiou
• Charis Papadopoulos
• Nikos Parotsidis

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. Also, augmented versions of our 2VCC algorithm computes a 6-approximation for maintaining both the 2-edge and the 2-vertex-connected components (2CC), and for maintaining all the 2-connectivity relations of G (2C), i. e. , both the 2-edge and the 2-vertex-connected subgraphs and components. Moreover, we provide heuristics that improve the size of the computed subgraphs in practice, and conduct a thorough experimental study to assess their merits in practical scenarios.

SODA Conference 2017 Conference Paper

Strong Connectivity in Directed Graphs under Failures, with Applications

• Loukas Georgiadis
• Giuseppe F. Italiano
• Nikos Parotsidis

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.

SODA Conference 2015 Conference Paper

2-Edge Connectivity in Directed Graphs

• Loukas Georgiadis
• Giuseppe F. Italiano
• Luigi Laura
• Nikos Parotsidis

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.

MFCS Conference 2007 Conference Paper

Dynamic Matchings in Convex Bipartite Graphs

• Gerth Stølting Brodal
• Loukas Georgiadis
• Kristoffer Arnsfelt Hansen
• Irit Katriel

Abstract We consider the problem of maintaining a maximum matching in a convex bipartite graph G = ( V, E ) under a set of update operations which includes insertions and deletions of vertices and edges. It is not hard to show that it is impossible to maintain an explicit representation of a maximum matching in sub-linear time per operation, even in the amortized sense. Despite this difficulty, we develop a data structure which maintains the set of vertices that participate in a maximum matching in O (log 2 | V |) amortized time per update and reports the status of a vertex (matched or unmatched) in constant worst-case time. Our structure can report the mate of a matched vertex in the maximum matching in worst-case O ( min { k log 2 | V | + log| V |, | V | log| V |}) time, where k is the number of update operations since the last query for the same pair of vertices was made. In addition, we give an \(O(\sqrt{|V|} \log^2{|V|})\) -time amortized bound for this pair query.

SODA Conference 2006 Conference Paper

Design of data structures for mergeable trees

• Loukas Georgiadis
• Robert Endre Tarjan
• Renato F. Werneck

FOCS Conference 2006 Conference Paper

Improved Dynamic Planar Point Location

• Lars Arge
• Gerth Stølting Brodal
• Loukas Georgiadis

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

SODA Conference 2005 Conference Paper

Dominator tree verification and vertex-disjoint paths

• Loukas Georgiadis
• Robert Endre Tarjan

SODA Conference 2004 Conference Paper

Finding dominators revisited: extended abstract

• Loukas Georgiadis
• Robert Endre Tarjan