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.

Given a directed graph G, a transitive reduction G^t of G (first studied by Aho, Garey, Ullman [SICOMP `72]) is a minimal subgraph of G that preserves the reachability relation between every two vertices in G. In this paper, we study the computational complexity of transitive reduction in the dynamic setting. We obtain the first fully dynamic algorithms for maintaining a transitive reduction of a general directed graph undergoing updates such as edge insertions or deletions. Our first algorithm achieves O(m+n log n) amortized update time, which is near-optimal for sparse directed graphs, and can even support extended update operations such as inserting a set of edges all incident to the same vertex, or deleting an arbitrary set of edges. Our second algorithm relies on fast matrix multiplication and achieves O(m+ n^{1.585}) worst-case update time.

In this paper, we consider the *metric $k$-center* problem in the fully dynamic setting, where we are given a metric space $(V,d)$ evolving via a sequence of point insertions and deletions and our task is to maintain a subset $S \subseteq V$ of at most $k$ points that minimizes the objective $\max_{x \in V} \min_{y \in S}d(x, y)$. We want to design our algorithm so that we minimize its *approximation ratio*, *recourse* (the number of changes it makes to the solution $S$) and *update time* (the time it takes to handle an update). We give a simple algorithm for dynamic $k$-center that maintains a $O(1)$-approximate solution with $O(1)$ amortized recourse and $\tilde O(k)$ amortized update time, *obtaining near-optimal approximation, recourse and update time simultaneously*. We obtain our result by combining a variant of the dynamic $k$-center algorithm of Bateni et al. [SODA'23] with the dynamic sparsifier of Bhattacharya et al. [NeurIPS'23].

We consider the problem of maintaining a hierarchical agglomerative clustering (HAC) in the dynamic setting, when the input is subject to point insertions and deletions. We introduce DynHac - the first dynamic HAC algorithm for the popular average-linkage version of the problem which can maintain a 1 + ε approximate solution. Our approach leverages recent structural results on 1 + ε-approximate HAC [1] to carefully identify the part of the clustering dendrogram that needs to be updated in order to produce a solution that is consistent with what a full recomputation from scratch would have output.

Abstract Motivated by a real‐world vehicle routing application, we consider the maximum‐weight independent set problem: given a node‐weighted graph, find a set of independent (mutually nonadjacent) nodes whose node‐weight sum is maximum. Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges. To solve instances of this size, we develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework. This algorithm, which we call METAMIS, uses a wider range of simple local search operations than previously described in the literature. We introduce data structures that make these operations efficient. A new variant of path‐relinking is introduced to escape local optima and so is a new alternating augmenting‐path local search move that improves algorithm performance. We compare an implementation of our algorithm with a state‐of‐the‐art openly available code on public benchmark sets, including some large instances with hundreds of millions of vertices. Our algorithm is, in general, competitive and outperforms this openly available code on large vehicle routing instances. We hope that our results will lead to even better MWIS algorithms.

In the dynamic metric$k-\mathbf{median}$problem, we wish to maintain a set of$k$centers$S\subseteq V$in an input metric space$(V, d)$that gets updated via point insertions/deletions, so as to minimize the objective$\sum\nolimits_{x\in V}\min\nolimits_{y\in S}d(x, y)$. The quality of a dynamic algorithm is measured in terms of its approximation ratio, “recourse” (the number of changes in$S$per update) and “update time” (the time it takes to handle an update). The ultimate goal in this line of research is to obtain a dynamic$O(1)$approximation algorithm with$\tilde{O}(1)$recourse and$\tilde{O}(k)$update time. Dynamic$k-\mathbf{median}$is a canonical example of a class of problems known as dynamic$k-\mathbf{clustering}$, that has received significant attention in recent years [Fichtenberger et al, SODA'21], [Bateni et al, SODA'23], [Lacki et al, SODA'24]. To the best of our knowledge, however, all these previous papers either attempt to minimize the algorithm's recourse while ignoring its update time, or minimize the algorithm's update time while ignoring its recourse. For dynamic$k-\mathbf{median}$in particular, the state-of-the-art results get$\tilde{O}(k^{2})$update time and$O(k)$recourse [Cohen-Addad et al, ICML'19], [Henzinger and Kale, ESA'20], [Bhattacharya et al, NeurIPS'23]. But, this recourse bound of$O(k)$can be trivially obtained by recomputing an optimal solution from scratch after every update, provided we ignore the update time. In addition, the update time of$\tilde{O}(k^{2})$is polynomially far away from the desired bound of$\tilde{O}(k)$. We come arbitrarily close to resolving the main open question on this topic, with the following results. (I) We develop a new framework of randomized local search that is suitable for adaptation in a dynamic setting. For every$\epsilon > 0$, this gives us a dynamic$k-\mathbf{median}$algorithm with$O(k^{\epsilon})$approximation ratio,$\tilde{O}(k^{\epsilon})$recourse and$\tilde{O}(k^{1+\epsilon})$update time. This framework also generalizes to dynamic$k-\mathbf{clustering}$with$\ell^{p}$-norm objectives. As a corollary, we obtain similar bounds for the dynamic$k-\mathbf{means}$problem, and a new trade-off between approximation ratio, recourse and update time for the dynamic$k-\mathbf{center}$problem. (II) If it suffices to maintain only an estimate of the value of the optimal$k-\mathbf{median}$objective, then we obtain a$O(1)$approximation algorithm with$\tilde{O}(k)$update time. We achieve this result via adapting the Lagrangian Relaxation framework of [Jain and Vazirani, JACM'01], and a facility location algorithm of [Mettu and Plaxton, FOCS'00] in the dynamic setting.

We study the classic problem of correlation clustering in dynamic vertex streams. In this setting, vertices are either added or randomly deleted over time, and each vertex pair is connected by a positive or negative edge. The objective is to continuously find a partition which minimizes the sum of positive edges crossing clusters and negative edges within clusters. We present an algorithm that maintains an $O(1)$-approximation with $O(\text{polylog} n)$ amortized update time. Prior to our work Behnezhad et al. in SODA 2023 achieved a $5$-approximation with $O(1)$ expected update time in edge streams which translates in vertex streams to an $O(D)$-update time where $D$ is the maximum possible degree. Finally we complement our theoretical analysis with experiments on real world data.

We consider the numerical taxonomy problem of fitting a positive distance function \({\mathcal {D}:{S\choose 2}\rightarrow \mathbb {R}_{\gt 0}}\) by a tree metric. We want a tree T with positive edge weights and including S among the vertices so that their distances in T match those in \(\mathcal {D}\) . A nice application is in evolutionary biology where the tree T aims to approximate thebranching process leading to the observed distances in \(\mathcal {D}\) [Cavalli-Sforza and Edwards 1967]. We consider the total error, that is, the sum of distance errors over all pairs of points. We present a deterministic polynomial time algorithm minimizing the total error within a constant factor. We can do this both for general trees and for the special case of ultrametrics with a root having the same distance to all vertices in S . The problems are APX-hard, so a constant factor is the best we can hope for in polynomial time. The best previous approximation factor was O ((log n )(log log n )) by Ailon and Charikar [2005], who wrote “determining whether an O (1) approximation can be obtained is a fascinating question.”

A classical problem in computational geometry and graph algorithms is: given a dynamic set 𝒮 of geometric shapes in the plane, efficiently maintain the connectivity of the intersection graph of 𝒮. Previous papers studied the setting where, before the updates, the data structure receives some parameter P. Then, updates could insert and delete disks as long as at all times the disks have a diameter that lies in a fixed range [1/P, 1]. As a consequence of that prerequisite, the aspect ratio ψ (i.e. the ratio between the largest and smallest diameter) of the disks would at all times satisfy ψ ≤ P. The state-of-the-art for storing disks in a dynamic connectivity data structure is a data structure that uses O(Pn) space and that has amortized O(P log⁴ n) expected amortized update time. Connectivity queries between disks are supported in O(log n / log log n) time. In the dynamic setting, one wishes for a more flexible data structure in which disks of any diameter may arrive and leave, independent of their diameter, changing the aspect ratio freely. Ideally, the aspect ratio should merely be part of the analysis. We restrict our attention to axis-aligned squares, and study fully-dynamic square intersection graph connectivity. Our result is fully-adaptive to the aspect ratio, spending time proportional to the current aspect ratio ψ, as opposed to some previously given maximum P. Our focus on squares allows us to simplify and streamline the connectivity pipeline from previous work. When n is the number of squares and ψ is the aspect ratio after insertion (or before deletion), our data structure answers connectivity queries in O(log n / log log n) time. We can update connectivity information in O(ψ log⁴ n + log⁶ n) amortized time. We also improve space usage from O(P ⋅ n log n) to O(n log³ n log ψ) - while generalizing to a fully-adaptive aspect ratio - which yields a space usage that is near-linear in n for any polynomially bounded ψ.

The $k$-means++ algorithm of Arthur and Vassilvitskii (SODA 2007) is often the practitioners' choice algorithm for optimizing the popular $k$-means clustering objective and is known to give an $O(\log k)$-approximation in expectation. To obtain higher quality solutions, Lattanzi and Sohler (ICML 2019) proposed augmenting $k$-means++ with $O(k \log \log k)$ local-search steps obtained through the $k$-means++ sampling distribution to yield a $c$-approximation to the $k$-means clustering problem, where $c$ is a large absolute constant. Here we generalize and extend their local-search algorithm by considering larger and more sophisticated local-search neighborhoods hence allowing to swap multiple centers at the same time. Our algorithm achieves a $9 + \varepsilon$ approximation ratio, which is the best possible for local search. Importantly we show that our algorithm is practical, namely easy to implement and fast enough to run on a variety of classic datasets, and outputs solutions of better cost.

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.

Motivated by a real-world vehicle routing application, we consider the maximum-weight independent set problem: Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum. Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges. To solve instances of this size, we develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search (GRASP) framework. This algorithm, which we call METAMIS, uses a wider range of simple local search operations than previously described in the literature. We introduce data structures that make these operations efficient. A new variant of path-relinking is introduced to escape local optima and so is a new alternating augmenting-path local search move that improves algorithm performance. We compare an implementation of our algorithm with a state-of-the-art openly available code on public benchmark sets, including some large instances with hundreds of millions of vertices. Our algorithm is, in general, competitive and outperforms this openly available code on large vehicle routing instances. We hope that our results will lead to even better MWIS algorithms.

In the correlation clustering problem the input is a signed graph where the sign indicates whether each pair of points should be placed in the same cluster or not. The goal of the problem is to compute a clustering which minimizes the number of disagreements with such recommendation. Thanks to its many practical applications, correlation clustering is a fundamental unsupervised learning problem and has been extensively studied in many different settings. In this paper we study the problem in the classic online setting with recourse; The vertices of the graphs arrive in an online manner and the goal is to maintain an approximate clustering while minimizing the number of times each vertex changes cluster. Our main contribution is an algorithm that achieves logarithmic recourse per vertex in the worst case. We also complement this result with a tight lower bound. Finally we show experimentally that our algorithm achieves better performances than state-of-the-art algorithms on real world data.

We consider the classic facility location problem in fully dynamic data streams, where elements can be both inserted and deleted. In this problem, one is interested in maintaining a stable and high quality solution throughout the data stream while using only little time per update (insertion or deletion). We study the problem and provide the first algorithm that at the same time maintains a constant approximation and incurs polylogarithmic amortized recourse per update. We complement our theoretical results with an experimental analysis showing the practical efficiency of our method.

Correlation clustering is a central problem in unsupervised learning, with applications spanning community detection, duplicate detection, automated labeling and many more. In the correlation clustering problem one receives as input a set of nodes and for each node a list of co-clustering preferences, and the goal is to output a clustering that minimizes the disagreement with the specified nodes' preferences. In this paper, we introduce a simple and computationally efficient algorithm for the correlation clustering problem with provable privacy guarantees. Our additive error is stronger than those obtained in prior work and is optimal up to polylogarithmic factors for fixed privacy parameters.

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 consider the numerical taxonomy problem of fitting a positive distance function$\mathcal{D}:\binom{S}{2}\rightarrow \mathbb{R}_{> 0}$by a tree metric. We want a tree$T$with positive edge weights and including$S$among the vertices so that their distances in$T$match those in$\mathcal{D}$. A nice application is in evolutionary biology where the tree$T$aims to approximate the branching process leading to the observed distances in$\mathcal{D}$[Cavalli-Sforza and Edwards 1967]. We consider the total error, that is the sum of distance errors over all pairs of points. We present a deterministic polynomial time algorithm minimizing the total error within a constant factor. We can do this both for general trees, and for the special case of ultrametrics with a root having the same distance to all vertices in$S$. The problems are APX-hard, so a constant factor is the best we can hope for in polynomial time. The best previous approximation factor was$O((\log n)(\log\log n)$) by Ailon and Charikar [2005] who wrote “Determining whether an$O(1)$approximation can be obtained is a fascinating question”.

Correlation clustering is a central topic in unsupervised learning, with many applications in ML and data mining. In correlation clustering, one receives as input a signed graph and the goal is to partition it to minimize the number of disagreements. In this work we propose a massively parallel computation (MPC) algorithm for this problem that is considerably faster than prior work. In particular, our algorithm uses machines with memory sublinear in the number of nodes in the graph and returns a constant approximation while running only for a constant number of rounds. To the best of our knowledge, our algorithm is the first that can provably approximate a clustering problem using only a constant number of MPC rounds in the sublinear memory regime. We complement our analysis with an experimental scalability evaluation of our techniques.

Let G = (V, E) be an n-vertex directed acyclic graph (DAG). A lowest common ancestor (LCA) of two vertices u and v is a common ancestor w of u and v such that no descendant of w has the same property. In this paper, we consider the problem of computing an LCA, if any, for all pairs of vertices in a DAG. The fastest known algorithms for this problem exploit fast matrix multiplication subroutines and have running times ranging from (n2.687) [Bender et al. SODA'01] down to (n2.615) [Kowaluk and Lingas ICALP'05] and (n2.569) [Czumaj et al. TCS'07]. Somewhat surprisingly, all those bounds would still be Ω(n2.5) even if matrix multiplication could be solved optimally (i.e., ω = 2). This appears to be an inherent barrier for all the currently known approaches, which raises the natural question on whether one could break through the (n2.5) barrier for this problem. In this paper, we answer this question affirmatively: in particular, we present an for ω = 2) algorithm for finding an LCA for all pairs of vertices in a DAG, which represents the first improvement on the running times for this problem in the last 13 years. A key tool in our approach is a fast algorithm to partition the vertex set of the transitive closure of G into a collection of (ℓ) chains and (n/ℓ) antichains, for a given parameter ℓ. As usual, a chain is a path while an antichain is an independent set. We then find, for all pairs of vertices, a candidate LCA among the chain and antichain vertices, separately. The first set is obtained via a reduction to (max, min) matrix multiplication. The computation of the second set can be reduced to Boolean matrix multiplication similarly to previous results on this problem. We finally combine the two solutions together in a careful (non-obvious) manner.

In this paper we present an efficient reachability oracle under single-edge or single-vertex failures for planar directed graphs. Specifically, we show that a planar digraph G can be preprocessed in O(n log2 n/log log n) time, producing an O(n log n)-space data structure that can answer in O(log n) time whether u can reach v in G if the vertex x (the edge f) is removed from G, for any query vertices u, v and failed vertex x (failed edge f). To the best of our knowledge, this is the first data structure for planar directed graphs with nearly optimal preprocessing time that answers all-pairs queries under any kind of failures in polylogarithmic time. We also consider 2-reachability problems, where we are given a planar digraph G and we wish to determine if there are two vertex-disjoint (edge-disjoint) paths from u to v, for query vertices u, v. In this setting we provide a nearly optimal 2-reachability oracle, which is the existential variant of the reachability oracle under single failures, with the following bounds. We can construct in O(n poly log n) time an O(n log3+o(1) n)-space data structure that can check in O(log2+o(1) n) time for any query vertices u, v whether v is 2-reachable from u, or otherwise find some separating vertex (edge) x lying on all paths from u to v in G. To obtain our results, we follow the general recursive approach of Thorup for reachability in planar graphs [J. ACM ‘04] and we present new data structures which generalize dominator trees and previous data structures for strong-connectivity under failures [Georgiadis et al., SODA ‘17]. Our new data structures work also for general digraphs and may be of independent interest.

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.

We consider classic clustering problems in fully dynamic data streams, where data elements can be both inserted and deleted. In this context, several parameters are of importance: (1) the quality of the solution after each insertion or deletion, (2) the time it takes to update the solution, and (3) how different consecutive solutions are. The question of obtaining efficient algorithms in this context for facility location, $k$-median and $k$-means has been raised in a recent paper by Hubert-Chan et al. [WWW'18] and also appears as a natural follow-up on the online model with recourse studied by Lattanzi and Vassilvitskii [ICML'17] (i.e.: in insertion-only streams). In this paper, we focus on general metric spaces and mainly on the facility location problem. We give an arguably simple algorithm that maintains a constant factor approximation, with $O(n\log n)$ update time, and total recourse $O(n)$. This improves over the naive algorithm which consists in recomputing a solution at each time step and that can take up to $O(n^2)$ update time, and $O(n^2)$ total recourse. These bounds are nearly optimal: in general metric space, inserting a point take $O(n)$ times to describe the distances to other points, and we give a simple lower bound of $O(n)$ for the recourse. Moreover, we generalize this result for the $k$-medians and $k$-means problems: our algorithm maintains a constant factor approximation in time $\widetilde{O}(n+k^2)$. We complement our analysis with experiments showing that the cost of the solution maintained by our algorithm at any time $t$ is very close to the cost of a solution obtained by quickly recomputing a solution from scratch at time $t$ while having a much better running time.

The Massive Parallel Computing (MPC) model gained popularity during the last decade and it is now seen as the standard model for processing large scale data. One significant shortcoming of the model is that it assumes to work on static datasets while, in practice, real world datasets evolve continuously. To overcome this issue, in this paper we initiate the study of dynamic algorithms in the MPC model. We first discuss the main requirements for a dynamic parallel model and we show how to adapt the classic MPC model to capture them. Then we analyze the connection between classic dynamic algorithms and dynamic algorithms in the MPC model. Finally, we provide new efficient dynamic MPC algorithms for a variety of fundamental graph problems, including connectivity, minimum spanning tree and matching.

In this paper we study the dynamic versions of two basic graph problems: Minimum Dominating Set and its variant Minimum Connected Dominating Set. For those two problems, we present algorithms that maintain a solution under edge insertions and edge deletions in time O(Delta * polylog n) per update, where Delta is the maximum vertex degree in the graph. In both cases, we achieve an approximation ratio of O(log n), which is optimal up to a constant factor (under the assumption that P != NP). Although those two problems have been widely studied in the static and in the distributed settings, to the best of our knowledge we are the first to present efficient algorithms in the dynamic setting. As a further application of our approach, we also present an algorithm that maintains a Minimal Dominating Set in O(min(Delta, sqrt{m})) per update.

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.

A reciprocal recommendation problem is one where the goal of learning is not just to predict a user's preference towards a passive item (e.g., a book), but to recommend the targeted user on one side another user from the other side such that a mutual interest between the two exists. The problem thus is sharply different from the more traditional items-to-users recommendation, since a good match requires meeting the preferences of both users. We initiate a rigorous theoretical investigation of the reciprocal recommendation task in a specific framework of sequential learning. We point out general limitations, formulate reasonable assumptions enabling effective learning and, under these assumptions, we design and analyze a computationally efficient algorithm that uncovers mutual likes at a pace comparable to those achieved by a clairvoyant algorithm knowing all user preferences in advance. Finally, we validate our algorithm against synthetic and real-world datasets, showing improved empirical performance over simple baselines.

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.

Social media has brought a revolution on how people are consuming news. Beyond the undoubtedly large number of advantages brought by social-media platforms, a point of criticism has been the creation of echo chambers and filter bubbles, caused by social homophily and algorithmic personalization. In this paper we address the problem of balancing the information exposure} in a social network. We assume that two opposing campaigns (or viewpoints) are present in the network, and that network nodes have different preferences towards these campaigns. Our goal is to find two sets of nodes to employ in the respective campaigns, so that the overall information exposure for the two campaigns is balanced. We formally define the problem, characterize its hardness, develop approximation algorithms, and present experimental evaluation results. Our model is inspired by the literature on influence maximization, but we offer significant novelties. First, balance of information exposure is modeled by a symmetric difference function, which is neither monotone nor submodular, and thus, not amenable to existing approaches. Second, while previous papers consider a setting with selfish agents and provide bounds on best response strategies (i.e., move of the last player), we consider a setting with a centralized agent and provide bounds for a global objective function.

Connectivity related concepts are of fundamental interest in graph theory. The area has received extensive attention over four decades, but many problems remain unsolved, especially for directed graphs. A directed graph is 2-edge-connected (resp., 2-vertex-connected) if the removal of any edge (resp., vertex) leaves the graph strongly connected. In this paper we present improved algorithms for computing the maximal 2-edge- and 2- vertex-connected subgraphs of a given directed graph. These problems were first studied more than 35 years ago, with Õ(mn) time algorithms for graphs with m edges and n vertices being known since the late 1980s. In contrast, the same problems for undirected graphs are known to be solvable in linear time. Henzinger et al. [ICALP 2015] recently introduced O(n2) time algorithms for the directed case, thus improving the running times for dense graphs. Our new algorithms run in time O(m3/2), which further improves the running times for sparse graphs. The notion of 2-connectivity naturally generalizes to k-connectivity for k > 2. For constant values of k, we extend one of our algorithms to compute the maximal k-edge-connected in time O(m3/2 logn), improving again for sparse graphs the best known algorithm by Henzinger et al. [ICALP 2015] that runs in O(n2 log n) time.

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.

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.

We present randomized algorithms with a total update time of Õ(m √n) for the problems of decremental single source reachability and decremental strongly connected components on directed graphs. This improves recent breakthrough results of Henzinger, Krinninger and Nanongkai [STOC 14, ICALP 15]. In addition, our algorithms are arguably simpler.

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.

Link recommendations are critical for both improving the utility and expediting the growth of social networks. Most previous approaches focus on suggesting links that are highly likely to be adopted. In this paper, we add a different perspective to the problem by aiming at recommending links that also improve specific properties of the network. In particular, our goal is to recommend to users links that if adopted would improve their centrality in the network. Specifically, we introduce the centrality-aware link recommendation problem as the problem of recommending to a user u, k links from a pool of recommended links so as to maximize the expected decrease of the sum of the shortest path distances of $u$ to all other nodes in the network. We show that the problem is NP-hard, but our optimization function is monotone and sub-modular which guarantees a constant approximation ratio for the greedy algorithm. We present a fast algorithm for computing the expected decrease caused by a set of recommendations which we use as a building block in our algorithms. We provide experimental results that evaluate the performance of our algorithms with respect to both the accuracy of the prediction and the improvement in the centrality of the nodes, and we study the tradeoff between the two.

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.

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

The small world phenomenon is a desirable property of social networks, since it guarantees short paths between the nodes of the social graph and thus efficient information spread on the network. It is thus in the benefit of both network users and network owners to enforce and maintain this property. In this work, we study the problem of finding a subset of k edges from a set of candidate edges whose addition to a network leads to the greatest reduction in its average shortest path length. We formulate the problem as a combinatorial optimization problem, and show that it is NP-hard and that known approximation techniques are not applicable. We describe an efficient method for computing the exact effect of a single edge insertion on the average shortest path length, as well as several heuristics for efficiently estimating this effect. We perform experiments on real data to study the performance of our algorithms in practice.

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.