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 revisit the (\(f,q\))-Clustering problem that we introduced in a recent work [SODA’25]. Here, \(f\) and \(g\) are symmetric, monotone norms called inner and outer norms, respectively. The task is to partition a given set of points in a metric space into \(k\) clusters each represented by a cluster center. Each cluster is assigned a cluster cost, determined by the norm \(f\) applied to the vector of point-center distances in the cluster. The goal is to minimize the value of the norm \(g\) when applied to the vector of cluster costs. This problem subsumes fundamental clustering problems such as \(k\)-Center (i.e., \(\mathcal L_\infty, \mathcal L_\infty\)-Clustering), \(k\)-Median (i.e., \(\mathcal L_1, \mathcal L_1\)-Clustering), Min-Sum of Radii (i.e., \(\mathcal L_\infty, \mathcal L_1\)-Clustering), and Min-Load \(k\)-Clustering (i.e., \(\mathcal L_1, \mathcal L_\infty\)-Clustering). In our previous work, we focused on certain special cases of this problem for which we designed constant-factor approximation algorithms. Our bounds for more general settings left, however, large gaps to the known bounds for the basic problems they capture.

Fitting distances to tree metrics and ultrametrics are two widely used methods in hierarchical clustering, primarily explored within the context of numerical taxonomy. Given a positive distance function $D:\binom{V}{2}\rightarrow\mathbb{R}_{>0}$, the goal is to find a tree (or ultrametric) $T$ including all elements of set $V$ such that the difference between the distances among vertices in $T$ and those specified by $D$ is minimized. In this paper, we initiate the study of ultrametric and tree metric fitting problems in the semi-streaming model, where the distances between pairs of elements from $V$ (with $|V|=n$), defined by the function $D$, can arrive in an arbitrary order. We study these problems under various distance norms: For the $\ell_0$ objective, we provide a single-pass polynomial-time $\tilde{O}(n)$-space $O(1)$ approximation algorithm for ultrametrics and prove that no single-pass exact algorithm exists, even with exponential time. Next, we show that the algorithm for $\ell_0$ implies an $O(Δ/δ)$ approximation for the $\ell_1$ objective, where $Δ$ is the maximum and $δ$ is the minimum absolute difference between distances in the input. This bound matches the best-known approximation for the RAM model using a combinatorial algorithm when $Δ/δ=O(n)$. For the $\ell_\infty$ objective, we provide a complete characterization of the ultrametric fitting problem. We present a single-pass polynomial-time $\tilde{O}(n)$-space 2-approximation algorithm and show that no better than 2-approximation is possible, even with exponential time. We also show that, with an additional pass, it is possible to achieve a polynomial-time exact algorithm for ultrametrics. Finally, we extend the results for all these objectives to tree metrics by using only one additional pass through the stream and without asymptotically increasing the approximation factor.

In the Correlation Clustering problem, we are given an undirected graph and are tasked with computing a clustering (partition of the nodes) that minimizes the sum of the number of edges across different clusters and the number of non-edges within clusters. In the constrained version of this problem, the goal is to compute a clustering that satisfies additional hard constraints mandating certain pairs to be in the same cluster and certain pairs to be in different clusters. Constrained Correlation Clustering is APX-Hard, and the best known approximation factor is 3 (van Zuylen et al. [SODA '07]). In this work, we show that in order to obtain a better-than-2 approximation, solving the (exponentially large) Constrained Cluster LP would be sufficient. [The peer-reviewed version of this article claimed an efficient algorithm for solving the Constrained Cluster LP. An error in the proof, that the authors discovered after the review process, led them to revise the results to be conditional on the existence of a valid LP solution.]

We initiate the study of the following general clustering problem. We seek to partition a given set P of data points into k clusters by finding a set X of k centers and assigning each data point to one of the centers. The cost of a cluster, represented by a center x ∊ X, is a monotone, symmetric norm f (called inner norm) of the vector of distances of points assigned to x. The goal is to minimize a norm g (called outer norm) of the vector of cluster costs. This problem, which we call (f, g )-Clustering, generalizes many fundamental clustering problems such as k-Center (i.e., (𝓛∞, 𝓛∞)-Clustering), k-Median (i.e., (𝓛1, 𝓛1)-Clustering), Min-Sum of Radii (i.e., (𝓛∞, 𝓛1)-Clustering), and Min-Load k-Clustering (i.e., (𝓛1, L∞)-Clustering). A recent line of research (Byrka et al. [STOC’18], Chakrabarty, Swamy [ICALP’18, STOC’19], and Abbasi et al. [FOCS’23]) studies norm objectives that are oblivious to the cluster structure such as k-Median and k-Center. In contrast, our problem models cluster-aware objectives including Min-Sum of Radii and Min-Load k-Clustering.

In the Correlation Clustering problem we are given n nodes, and a preference for each pair of nodes indicating whether we prefer the two endpoints to be in the same cluster or not. The output is a clustering inducing the minimum number of violated preferences. In certain cases, however, the preference between some pairs may be too important to be violated. The constrained version of this problem specifies pairs of nodes that must be in the same cluster as well as pairs that must not be in the same cluster (hard constraints). The output clustering has to satisfy all hard constraints while minimizing the number of violated preferences. Constrained Correlation Clustering is APX-Hard and has been approximated within a factor 3 by van Zuylen et al. [SODA’07]. Their algorithm is based on rounding an LP with Θ(n3) constraints, resulting in an Ω(n3ω) running time. In this work, using a more combinatorial approach, we show how to approximate this problem significantly faster at the cost of a slightly weaker approximation factor. In particular, our algorithm runs in Oe(n3) time (notice that the input size is Θ(n2)) and approximates Constrained Correlation Clustering within a factor 16. To achieve our result we need properties guaranteed by a particular influential algorithm for (unconstrained) Correlation Clustering, the CC-PIVOT algorithm. This algorithm chooses a pivot node u, creates a cluster containing u and all its preferred nodes, and recursively solves the rest of the problem. It is known that selecting pivots at random gives a 3-approximation. As a byproduct of our work, we provide a derandomization of the CC-PIVOT algorithm that still achieves the 3-approximation; furthermore, we show that there exist instances where no ordering of the pivots can give a (3 − ε)-approximation, for any constant ε. Finally, we introduce a node-weighted version of Correlation Clustering, which can be approximated within factor 3 using our insights on Constrained Correlation Clustering. As the general weighted version of Correlation Clustering would require a major breakthrough to approximate within a factor o(log n), Node-Weighted Correlation Clustering may be a practical alternative.

The Dynamic Time Warping (DTW) distance is a popular similarity measure for polygonal curves (i.e., sequences of points). It finds many theoretical and practical applications, especially for temporal data, and is known to be a robust, outlier-insensitive alternative to the Fréchet distance. For static curves of at most n points, the DTW distance can be computed in O(n2) time in constant dimension. This tightly matches a SETH-based lower bound, even for curves in ℝ1.

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

In the $L_0$ Fitting Tree Metrics problem, we are given all pairwise distances among the elements of a set $V$ and our output is a tree metric on $V$. The goal is to minimize the number of pairwise distance disagreements between the input and the output. We provide an $O(1)$ approximation for $L_0$ Fitting Tree Metrics, which is asymptotically optimal as the problem is APX-Hard. For $p\ge 1$, solutions to the related $L_p$ Fitting Tree Metrics have typically used a reduction to $L_p$ Fitting Constrained Ultrametrics. Even though in FOCS '22 Cohen-Addad et al. solved $L_0$ Fitting (unconstrained) Ultrametrics within a constant approximation factor, their results did not extend to tree metrics. We identify two possible reasons, and provide simple techniques to circumvent them. Our framework does not modify the algorithm from Cohen-Addad et al. It rather extends any $ρ$ approximation for $L_0$ Fitting Ultrametrics to a $6ρ$ approximation for $L_0$ Fitting Tree Metrics in a blackbox fashion.

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.

Stochastic sample-based estimators are among the most fundamental and universally applied tools in statistics. Such estimators are particularly important when processing huge amounts of data, where we need to be able to answer a wide range of statistical queries reliably, yet cannot afford to store the data in its full length. In many applications we need the sampling to be coordinated which is typically attained using hashing. In previous work, a common strategy to obtain reliable sample-based estimators that work within certain error bounds with high probability has been to design one that works with constant probability, and then boost the probability by taking the median over r independent repetitions. Aamand et al. (STOC'20) recently proposed a fast and practical hashing scheme with strong concentration bounds , Tabulation-1Permutation, the first of its kind. In this paper, we demonstrate that using such a hash family for the sampling, we achieve the same high probability bounds without any need for repetitions. Using the same space, this saves a factor r in time, and simplifies the overall algorithms. We validate our approach experimentally on both real and synthetic data. We compare Tabulation-1Permutation with other hash functions such as strongly universal hash functions and various other hash functions such as MurmurHash3 and BLAKE3, both with and without resorting to repetitions. We see that if we want reliability in terms of small error probabilities, then Tabulation-1Permutation is significantly faster.

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

We consider the general problem of the Longest Common Subsequence (LCS) on weighted sequences. Weighted sequences are an extension of classical strings, where in each position every letter of the alphabet may occur with some probability. Previous results presented a PTAS and noticed that no FPTAS is possible unless P=NP. In this paper we essentially close the gap between upper and lower bounds by improving both. First of all, we provide an EPTAS for bounded alphabets (which is the most natural case), and prove that there does not exist any EPTAS for unbounded alphabets unless FPT=W[1]. Furthermore, under the Exponential Time Hypothesis, we provide a lower bound which shows that no significantly better PTAS can exist for unbounded alphabets. As a side note, we prove that it is sufficient to work with only one threshold in the general variant of the problem.