We study differentially private algorithms for graph cut sparsification, a fundamental problem in algorithms, privacy, and machine learning. While significant progress has been made, the best-known private and efficient cut sparsifiers on $n$-node graphs approximate each cut within $\widetilde{O}(n^{1.5})$ additive error and $1+\gamma$ multiplicative error for any $\gamma > 0$ [Gupta, Roth, Ullman TCC'12]. In contrast, \emph{inefficient} algorithms, i.e., those requiring exponential time, can achieve an $\widetilde{O}(n)$ additive error and $1+\gamma$ multiplicative error [Eliáš, Kapralov, Kulkarni, Lee SODA'20]. In this work, we break the $n^{1.5}$ additive error barrier for private and efficient cut sparsification. We present an $(\varepsilon,\delta)$-DP polynomial time algorithm that, given a non-negative weighted graph, outputs a private synthetic graph approximating all cuts with multiplicative error $1+\gamma$ and additive error $n^{1.25 + o(1)}$ (ignoring dependencies on $\varepsilon, \delta, \gamma$). At the heart of our approach lies a private algorithm for expander decomposition, a popular and powerful technique in (non-private) graph algorithms.

We present a new Correlation Clustering algorithm for a dynamic setting where nodes are added one at a time. In this model, proposed by Cohen-Addad, Lattanzi, Maggiori, and Parotsidis (ICML 2024), the algorithm uses database queries to access the input graph and updates the clustering as each new node is added. Our algorithm has the amortized update time of $\log^{O(1)}(n)$. Its approximation factor is $20+\varepsilon$, which is a substantial improvement over the approximation factor of the algorithm by Cohen-Addad et al. We complement our theoretical findings by empirically evaluating the approximation guarantee of our algorithm. The results show that it outperforms the algorithm by Cohen-Addad et al.~in practice.

Many forms of sensitive data, such as web traffic, mobility data, or hospital occupancy, are inherently sequential. The standard method for training machine learning models while ensuring privacy for units of sensitive information, such as individual hospital visits, is differentially private stochastic gradient descent (DP-SGD). However, we observe in this work that the formal guarantees of DP-SGD are incompatible with time series specific tasks like forecasting, since they rely on the *privacy amplification* attained by training on small, unstructured batches sampled from an unstructured dataset. In contrast, batches for forecasting are generated by (1) sampling sequentially structured time series from a dataset, (2) sampling contiguous subsequences from these series, and (3) partitioning them into context and ground-truth forecast windows. We theoretically analyze the privacy amplification attained by this *structured subsampling* to enable the training of forecasting models with sound and tight event- and user-level privacy guarantees. Towards more private models, we additionally prove how data augmentation amplifies privacy in self-supervised training of sequence models. Our empirical evaluation demonstrates that amplification by structured subsampling enables the training of forecasting models with strong formal privacy guarantees.

Given an undirected, weighted $n$-vertex graph $G = (V, E, w)$, a Gomory-Hu tree $T$ is a weighted tree on $V$ that preserves the Min-$s$-$t$-Cut between any pair of vertices $s, t \in V$. Finding cuts in graphs is a key primitive in problems such as bipartite matching, spectral and correlation clustering, and community detection. We design a differentially private (DP) algorithm that computes an approximate Gomory-Hu tree. Our algorithm is $\varepsilon$-DP, runs in polynomial time, and can be used to compute $s$-$t$ cuts that are $\tilde{O}(n/\varepsilon)$-additive approximations of the Min-$s$-$t$-Cuts in $G$ for all distinct $s, t \in V$ with high probability. Our error bound is essentially optimal, since [Dalirrooyfard, Mitrovic and Nevmyvaka, Neurips 2023] showed that privately outputting a single Min-$s$-$t$-Cut requires $\Omega(n)$ additive error even with $(\varepsilon, \delta)$-DP and allowing for multiplicative error. Prior to our work, the best additive error bounds for approximate all-pairs Min-$s$-$t$-Cuts were $O(n^{3/2}/\varepsilon)$ for $\varepsilon$-DP [Gupta, Roth, Ullman, TCC 2009] and $\tilde{O}(\sqrt{mn}/ \varepsilon)$ for $(\varepsilon, \delta)$-DP [Liu, Upadhyay and Zou, SODA 2024], both achieved by DP algorithms that preserve all cuts in the graph. To achieve our result, we develop an $\varepsilon$-DP algorithm for the Minimum Isolating Cuts problem with near-linear error, and introduce a novel privacy composition technique combining elements of both parallel and basic composition to handle `bounded overlap' computational branches in recursive algorithms, which maybe of independent interest.

This work establishes conditional lower bounds for average-case parity -counting versions of the problems k-XOR, k- SUM, and k-OV. The main contribution is a set of self-reductions for the problems, providing the first specific distributions, for which:

Approximating the graph diameter is a basic task of both theoretical and practical interest. A simple folklore algorithm can output a 2-approximation to the diameter in linear time by running BFS from an arbitrary vertex. It has been open whether a better approximation is possible in near-linear time. A series of articles on fine-grained complexity have led to strong hardness results for diameter in directed graphs, culminating in a recent tradeoff curve independently discovered by [Li, STOC’21] and [Dalirrooyfard and Wein, STOC’21], showing that under the Strong Exponential Time Hypothesis (SETH), for any integer k ≥ 2 and δ > 0, a \(2-\frac{1}{k}-\delta\) approximation for diameter in directed m -edge graphs requires \(m^{1+1/(k-1)-o(1)}\) time. In particular, the simple linear time 2-approximation algorithm is optimal for directed graphs. In this article, we prove that the same tradeoff lower bound curve is possible for undirected graphs as well, extending results of [Roditty and Vassilevska W., STOC’13], [Li’20] and [Bonnet, ICALP’21] who proved the first few cases of the curve, k =2,3, and 4, respectively. Our result shows in particular that the simple linear time 2-approximation algorithm is conditionally optimal for undirected graphs. To obtain our result, we extract the core ideas in known reductions and introduce a unification and generalization that could be useful for proving SETH-based hardness for other problems in undirected graphs related to distance computation.

In many real world networks, there already exists a (not necessarily optimal) $k$-partitioning of the network. Oftentimes, for such networks, one aims to find a $k$-partitioning with a smaller cut value by moving only a few nodes across partitions. The number of nodes that can be moved across partitions is often a constraint forced by budgetary limitations. Motivated by such real-world applications, we introduce and study the $r$-move $k$-partitioning problem, a natural variant of the Multiway cut problem. Given a graph, a set of $k$ terminals and an initial partitioning of the graph, the $r$-move $k$-partitioning problem aims to find a $k$-partitioning with the minimum-weighted cut among all the $k$-partitionings that can be obtained by moving at most $r$ non-terminal nodes to partitions different from their initial ones. Our main result is a polynomial time $3(r+1)$ approximation algorithm for this problem. We further show that this problem is $W[1]$-hard, and give an FPTAS for when $r$ is a small constant.

Given a graph with positive and negative edge labels, the correlation clustering problem aims to cluster the nodes so to minimize the total number of between-cluster positive and within-cluster negative edges. This problem has many applications in data mining, particularly in unsupervised learning. Inspired by the prevalence of large graphs and constantly changing data in modern applications, we study correlation clustering in dynamic, parallel (MPC), and local computation (LCA) settings. We design an approach that improves state-of-the-art runtime complexities in all these settings. In particular, we provide the first fully dynamic algorithm that runs in an expected amortized constant time, without any dependence on the graph size. Moreover, our algorithm essentially matches the approximation guarantee of the celebrated Pivot algorithm.

We study the problem of finding and listing k-cliques in an m-edge, n-vertex graph, for constant k≥ 3. This is a fundamental problem of both theoretical and practical importance.

Computing the diameter of a graph, i.e. the largest distance, is a fundamental problem that is central in fine-grained complexity. In undirected graphs, the Strong Exponential Time Hypothesis (SETH) yields a lower bound on the time vs. approximation trade-off that is quite close to the upper bounds. In \emph{directed} graphs, however, where only some of the upper bounds apply, much larger gaps remain. Since $d(u,v)$ may not be the same as $d(v,u)$, there are multiple ways to define the problem, the two most natural being the \emph{(one-way) diameter} ($\max_{(u,v)} d(u,v)$) and the \emph{roundtrip diameter} ($\max_{u,v} d(u,v)+d(v,u)$). In this paper we make progress on the outstanding open question for each of them. -- We design the first algorithm for diameter in sparse directed graphs to achieve $n^{1.5-\varepsilon}$ time with an approximation factor better than $2$. The new upper bound trade-off makes the directed case appear more similar to the undirected case. Notably, this is the first algorithm for diameter in sparse graphs that benefits from fast matrix multiplication. -- We design new hardness reductions separating roundtrip diameter from directed and undirected diameter. In particular, a $1.5$-approximation in subquadratic time would refute the All-Nodes $k$-Cycle hypothesis, and any $(2-\varepsilon)$-approximation would imply a breakthrough algorithm for approximate $\ell_{\infty}$-Closest-Pair. Notably, these are the first conditional lower bounds for diameter that are not based on SETH.

We propose a new conjecture on hardness of 2-CSP’s, and show that new hardness of approximation results for Densest k-Subgraph and several other problems, including a graph partitioning problem, and a variation of the Graph Crossing Number problem, follow from this conjecture. The conjecture can be viewed as occupying a middle ground between the d-to-1 conjecture, and hardness results for 2-CSP’s that can be obtained via standard techniques, such as Parallel Repetition combined with standard 2-prover protocols for the 3SAT problem. We hope that this work will motivate further exploration of hardness of 2-CSP’s in the regimes arising from the conjecture. We believe that a positive resolution of the conjecture will provide a good starting point for other hardness of approximation proofs. Another contribution of our work is proving that the problems that we consider are roughly equivalent from the approximation perspective. Some of these problems arose in previous work, from which it appeared that they may be related to each other. We formalize this relationship in this work.

Finding min $s$-$t$ cuts in graphs is a basic algorithmic tool, with applications in image segmentation, community detection, reinforcement learning, and data clustering. In this problem, we are given two nodes as terminals and the goal is to remove the smallest number of edges from the graph so that these two terminals are disconnected. We study the complexity of differential privacy for the min $s$-$t$ cut problem and show nearly tight lower and upper bounds where we achieve privacy at no cost for running time efficiency. We also develop a differentially private algorithm for the multiway $k$-cut problem, in which we are given $k$ nodes as terminals that we would like to disconnect. As a function of $k$, we obtain privacy guarantees that are exponentially more efficient than applying the advanced composition theorem to known algorithms for multiway $k$-cut. Finally, we empirically evaluate the approximation of our differentially private min $s$-$t$ cut algorithm and show that it almost matches the quality of the output of non-private ones.

Detecting out-of-distribution (OOD) samples is a problem of practical importance for a reliable use of deep neural networks (DNNs) in production settings. The corollary to this problem is the detection in-distribution (ID) samples, which is applicable to domain adaptation scenarios for augmenting a train set with ID samples from other data sets, or to continual learning for replay from the past. For both ID or OOD detection, we propose a principled yet simple approach of (empirically) estimating KL-Divergence, in its dual form, for a given test set w.r.t. a known set of ID samples in order to quantify the contribution of each test sample individually towards the divergence measure and accordingly detect it as OOD or ID. Our approach is compute-efficient and enjoys strong theoretical guarantees. For WideResnet101 and ViT-L-16, by considering ImageNet-1k dataset as the ID benchmark, we evaluate the proposed OOD detector on 51 test (OOD) datasets, and observe drastically and consistently lower false positive rates w.r.t. all the competitive methods. Moreover, the proposed ID detector is evaluated, using ECG and stock price datasets, for the task of data augmentation in domain adaptation and continual learning settings, and we observe higher efficacy compared to relevant baselines.

Information-theoretic clustering is one of the most promising and principled approaches to finding clusters with minimal apriori assumptions. The key criterion therein is to maximize the mutual information between the data points and their cluster labels. Such an approach, however, does not explicitly promote any type of inter-cluster behavior. We instead propose to maximize the Kullback-Leibler divergence between the underlying data distributions associated to clusters (referred to as cluster distributions). We show it to entail the mutual information criterion along with maximizing cross entropy between the cluster distributions. For practical efficiency, we propose to empirically estimate the objective of KL-D between clusters in its dual form leveraging deep neural nets as a dual function approximator. Remarkably, our theoretical analysis establishes that estimating the divergence measure in its dual form simplifies the problem of clustering to one of optimally finding k-1 cut points for k clusters in the 1-D dual functional space. Overall, our approach enables linear-time clustering algorithms with theoretical guarantees of near-optimality, owing to the submodularity of the objective. We show the empirical superiority of our approach w.r.t. current state-of-the-art methods on the challenging task of clustering noisy timeseries as observed in domains such as neuroscience, healthcare, financial markets, spatio-temporal environmental dynamics, etc.

We study the approximability of two related problems on graphs with n nodes and m edges: n-Pairs Shortest Paths (n-PSP), where the goal is to find a shortest path between O(n) prespecified pairs, and All Node Shortest Cycles (ANSC), where the goal is to find the shortest cycle passing through each node. Approximate n-PSP has been previously studied, mostly in the context of distance oracles. We ask the question of whether approximate n-PSP can be solved faster than by using distance oracles or All Pair Shortest Paths (APSP). ANSC has also been studied previously, but only in terms of exact algorithms, rather than approximation.We provide a thorough study of the approximability of n PSP and ANSC, providing a wide array of algorithms and conditional lower bounds that trade off between running time and approximation ratio.A highlight of our conditional lower bounds results is that for any integer k$\geq$1, under the combinatorial 4k-clique hypothesis, there is no combinatorial algorithm for unweighted undirected n-PSP with approximation ratio better than $1+1/k$ that runs in $O(m^{2-2/(k+1)}n^{1/(k+1)-\varepsilon})$ time. This nearly matches an upper bound implied by the result of Agarwal (2014).Our algorithms use a surprisingly wide range of techniques, including techniques from the girth problem, distance oracles, approximate APSP, spanners, fault-tolerant spanners, and link-cut trees.A highlight of our algorithmic results is that one can solve both n-PSP and ANSC in $O(m+n^{3/2+\in})$ time1with approximation factor $2+\varepsilon$ (and additive error that is function of $\varepsilon$), for any constant $\varepsilon\lt 0$. For n-PSP, our conditional lower bounds imply that this approximation ratio is nearly optimal for any subquadratic-time combinatorial algorithm. We further extend these algorithms for n-PSP and ANSC to obtain a time/accuracy trade-off that includes near-linear time algorithms.1$\tilde{O}$ hides sub-polynomial factors.Additionally, for ANSC, for all integers $k\geq 1$, we extend the very recent almost k-approximation algorithm for the girth problem that works in $\tilde{O}(n^{1+1/k})$ time [Kadria et al. SODA’22], and obtain an almost k-approximation algorithm for ANSC in $\tilde{O}(mn^{1/k})$ time.

The goal of the paper is to give fine-grained hardness results for the Subgraph Isomorphism (SI) problem for fixed size induced patterns H, based on the k-Clique hypothesis that the current best algorithms for Clique are optimal. Our first main result is that for any pattern graph H that is a core, the SI problem for H is at least as hard as t-Clique, where t is the size of the largest clique minor of H. This improves (for cores) the previous known results [Dalirrooyfard-Vassilevska W. STOC’20] that the SI for H is at least as hard as k-clique where k is the size of the largest clique subgraph in H, or the chromatic number of H (under the Hadwiger conjecture). For detecting any graph pattern H, we further remove the dependency of the result of [Dalirrooyfard-Vassilevska W. STOC’20] on the Hadwiger conjecture at the cost of a sub-polynomial decrease in the lower bound. The result for cores allows us to prove that the SI problem for induced k-Path and k-Cycle is harder than previously known. Previously [Floderus et al. Theor. CS 2015] had shown that k-Path and k-Cycle are at least as hard to detect as a $\lfloor$k/2$\rfloor -$Clique. We show that they are in fact at least as hard as 3k/4-O(1)-Clique, improving the conditional lower bound exponent by a factor of 3/2. This shoivs for instance that the knoivn $O(n^{5})$ combinatorial algorithm for 7-cycle detection is conditionally tight. Finally, we provide a new conditional lower bound for detecting induced 4-cycles: $n^{2-o(1)}$ time is necessary even in graphs with n nodes and $O(n^{15})$ edges. The 4-cycle is the smallest induced pattern whose running time is not well-understood. It can be solved in matrix multiplication, $O(n^{\omega})$ time, but no conditional lower bounds were known until ours. We provide evidence that certain types of reductions from triangle detection to 4-Cycle would not be possible. We do this by studying a new problem called Paired Pattern Detection.

Approximating the graph diameter is a basic task of both theoretical and practical interest. A simple folklore algorithm can output a 2-approximation to the diameter in linear time by running BFS from an arbitrary vertex. It has been open whether a better approximation is possible in near-linear time. A series of papers on fine-grained complexity have led to strong hardness results for diameter in directed graphs, culminating in a recent tradeoff curve independently discovered by [Li, STOC'21] and [Dalirrooyfard and Wein, STOC'21], showing that under the Strong Exponential Time Hypothesis (SETH), for any integer$k\geq 2$and$\delta > 0$, a$2-\frac{1}{k}-\delta$approximation for diameter in directed$m$-edge graphs requires$mn^{1+1/(k-1)-o(1)}$time. In particular, the simple linear time 2-approximation algorithm is optimal for directed graphs. In this paper we prove that the same tradeoff lower bound curve is possible for undirected graphs as well, extending results of [Roditty and Vassilevska W., STOC'13], [Li'20] and [Bonnet, ICALP'21] who proved the first few cases of the curve,$k=2,3$and 4, respectively. Our result shows in particular that the simple linear time 2-approximation algorithm is also optimal for undirected graphs. To obtain our result we develop new tools for fine-grained reductions that could be useful for proving SETH-based hardness for other problems in undirected graphs related to distance computation.

Graph parameters such as the diameter, radius, and vertex eccentricities are not defined in a useful way in Directed Acyclic Graphs (DAGs) using the standard measure of distance, since for any two nodes, there is no path between them in one of the two directions. So it is natural to consider the distance between two nodes as the length of the shortest path in the direction in which this path exists, motivating the definition of the min-distance. The min-distance between two nodes u and v is the minimum of the shortest path distances from u to v and from v to u. As with the standard distance problems, the Strong Exponential Time Hypothesis [Impagliazzo-Paturi-Zane 2001, Calabro-Impagliazzo-Paturi 2009] leaves little hope for computing min-distance problems faster than computing All Pairs Shortest Paths, which can be solved in Õ(mn) time. So it is natural to resort to approximation algorithms in Õ(mn^{1-ε}) time for some positive ε. Abboud, Vassilevska W., and Wang [SODA 2016] first studied min-distance problems achieving constant factor approximation algorithms on DAGs, and Dalirrooyfard et al [ICALP 2019] gave the first constant factor approximation algorithms on general graphs for min-diameter, min-radius and min-eccentricities. Abboud et al obtained a 3-approximation algorithm for min-radius on DAGs which works in Õ(m√n) time, and showed that any (2-δ)-approximation requires n^{2-o(1)} time for any δ > 0, under the Hitting Set Conjecture. We close the gap, obtaining a 2-approximation algorithm which runs in Õ(m√n) time. As the lower bound of Abboud et al only works for sparse DAGs, we further show that our algorithm is conditionally tight for dense DAGs using a reduction from Boolean matrix multiplication. Moreover, Abboud et al obtained a linear time 2-approximation algorithm for min-diameter along with a lower bound stating that any (3/2-δ)-approximation algorithm for sparse DAGs requires n^{2-o(1)} time under SETH. We close this gap for dense DAGs by obtaining a 3/2-approximation algorithm which works in O(n^{2.350}) time and showing that the approximation factor is unlikely to be improved within O(n^{ω - o(1)}) time under the high dimensional Orthogonal Vectors Conjecture, where ω is the matrix multiplication exponent.

Among the most fundamental graph parameters is the Diameter, the largest distance between any pair of vertices in a graph. Computing the Diameter of a graph with m edges requires m2−o(1) time under the Strong Exponential Time Hypothesis (SETH), which can be prohibitive for very large graphs, so efficient approximation algorithms for Diameter are desired.

We consider the pattern detection problem in graphs: given a constant size pattern graph $H$ and a host graph $G$, determine whether $G$ contains a subgraph isomorphic to $H$. We present the following new improved upper and lower bounds: We prove that if a pattern $H$ contains a $k$-clique subgraph, then detecting whether an $n$ node host graph contains a not necessarily induced copy of $H$ requires at least the time for detecting whether an $n$ node graph contains a $k$-clique. The previous result of this nature required that $H$ contains a $k$-clique which is disjoint from all other $k$-cliques of $H$. We show that if the famous Hadwiger conjecture from graph theory is true, then detecting whether an $n$ node host graph contains a not necessarily induced copy of a pattern with chromatic number $t$ requires at least the time for detecting whether an $n$ node graph contains a $t$-clique. This implies that (1) under Hadwiger's conjecture for every $k$-node pattern $H$, finding an induced copy of $H$ requires at least the time of $\sqrt k$-clique detection and size $\omega(n^{\sqrt{k}/4})$ for any constant depth circuit, and (2) unconditionally, detecting an induced copy of a random $G(k,p)$ pattern with high probability requires at least the time of $\Theta(k/\log k)$-clique detection, and hence also at least size $n^{\Omega(k/\log k)}$ for circuits of constant depth. We show that for every $k$, there exists a $k$-node pattern that contains a $k-1$-clique and that can be detected as an induced subgraph in $n$ node graphs in the best known running time for $k-1$-clique detection. Previously such a result was only known for infinitely many $k$. Finally, we consider the case when the pattern is a directed cycle on $k$ nodes, and we would like to detect whether a directed $m$-edge graph $G$ contains a $k$-cycle as a not necessarily induced subgraph. We resolve a 14- year-old conjecture of [Yuster and Zwick, Proceedings of SODA, 2004, pp. 247--253] on the complexity of $k$-cycle detection by giving a tight analysis of their $k$-cycle algorithm. Our analysis improves the best bounds for $k$-cycle detection in directed graphs for all $k>5$.

The recent emergence of fine-grained cryptography strongly motivates developing an average-case analogue of Fine-Grained Complexity (FGC). Prior work [Goldreich-Rothblum 2018, Boix-Adserà et al. 2019, Ball et al. 2017] developed worst-case to average-case fine-grained reductions (WCtoACFG) for certain algebraic and counting problems over natural distributions and used them to obtain a limited set of cryptographic primitives. To obtain stronger cryptographic primitives based on standard FGC assumptions, ideally, one would like to develop WCtoACFG reductions from the core hard problems of FGC, Orthogonal Vectors (OV), CNF-SAT, 3SUM, All-Pairs Shortest Paths (APSP) and zero- k clique. Unfortunately, it is unclear whether these problems actually are hard for any natural distribution. It is known, that e.g. OV can be solved quickly for very natural distributions [Kane-Williams 2019], and in this paper we show that even counting the number of OV pairs on average has a fast algorithm. This paper defines new versions of OV, kSUM and zero- k-clique that are both worst-case and average-case fine-grained hard assuming the core hypotheses of FGC. We then use these as a basis for fine-grained hardness and average-case hardness of other problems. The new problems represent their inputs in a certain “factored” form. We call them “factored”-OV, “factored”-zero- k-clique and “factored”-3SUM. We show that factored- k-OV and factored kSUM are equivalent and are complete for a class of problems defined over Boolean functions. Factored zero- k-clique is also complete, for a different class of problems. Our hard factored problems are also simple enough that we can reduce them to many other problems, e.g. to edit distance, k-LCS and versions of Max-Flow. We further consider counting variants of the factored problems and give WCtoACFG reductions for them for a natural distribution. Through FGC reductions we then get average-case hardness for well-studied problems like regular expression matching from standard worst-case FGC assumptions. To obtain our WCtoACFG reductions, we formalize the framework of [Boix-Adserà et al. 2019] that was used to give a WCtoACFG reduction for counting k-cliques. We define an explicit property of problems such that if a problem has that property one can use the framework on the problem to get a WCtoACFG self reduction. We then use the framework to slightly extend Bolx-Adserà et al.'s average-case counting k-cliques result to average-case hardness for counting arbitrary subgraph patterns of constant size in -partite graphs. The fine-grained public-key encryption scheme of [LaVigne et al.'20] is based on an average-case hardness hypothesis for the decision problem, zero- k-clique, and the known techniques for building such schemes break down for algebraic/counting problems. Meanwhile, the WCtoACFG reductions so far have only been for counting problems. To bridge this gap, we show that for a natural distribution, an algorithm that detects a zero- k-clique with high enough probability also implies an algorithm that can count zero- k-cliques with high probability. This gives hope that the FGC cryptoscheme of [LaVigne et al.'20] can be based on standard FGC assumptions.

It is known that a better than $2$-approximation algorithm for the girth in dense directed unweighted graphs needs $n^{3-o(1)}$ time unless one uses fast matrix multiplication. Meanwhile, the best known approximation factor for a combinatorial algorithm running in $O(mn^{1-ε})$ time (by Chechik et al.) is $3$. Is the true answer $2$ or $3$? The main result of this paper is a (conditionally) tight approximation algorithm for directed graphs. First, we show that under a popular hardness assumption, any algorithm, even one that exploits fast matrix multiplication, would need to take at least $mn^{1-o(1)}$ time for some sparsity $m$ if it achieves a $(2-ε)$-approximation for any $ε>0$. Second we give a $2$-approximation algorithm for the girth of unweighted graphs running in $\tilde{O}(mn^{3/4})$ time, and a $(2+ε)$-approximation algorithm (for any $ε>0$) that works in weighted graphs and runs in $\tilde{O}(m\sqrt n)$ time. Our algorithms are combinatorial. We also obtain a $(4+ε)$-approximation of the girth running in $\tilde{O}(mn^{\sqrt{2}-1})$ time, improving upon the previous best $\tilde{O}(m\sqrt n)$ running time by Chechik et al. Finally, we consider the computation of roundtrip spanners. We obtain a $(5+ε)$-approximate roundtrip spanner on $\tilde{O}(n^{1.5}/ε^2)$ edges in $\tilde{O}(m\sqrt n/ε^2)$ time. This improves upon the previous approximation factor $(8+ε)$ of Chechik et al. for the same running time.

Diameter, radius and eccentricities are fundamental graph parameters, which are extensively studied in various computational settings. Typically, computing approximate answers can be much more efficient compared with computing exact solutions. In this paper, we give a near complete characterization of the trade-offs between approximation ratios and round complexity of distributed algorithms for approximating these parameters, with a focus on the weighted and directed variants. Furthermore, we study bi-chromatic variants of these parameters defined on a graph whose vertices are colored either red or blue, and one focuses only on distances for pairs of vertices that are colored differently. Motivated by applications in computational geometry, bi-chromatic diameter, radius and eccentricities have been recently studied in the sequential setting [Backurs et al. STOC'18, Dalirrooyfard et al. ICALP'19]. We provide the first distributed upper and lower bounds for such problems. Our technical contributions include introducing the notion of approximate pseudo-center, which extends the pseudo-centers of [Choudhary and Gold SODA'20], and presenting an efficient distributed algorithm for computing approximate pseudo-centers. On the lower bound side, our constructions introduce the usage of new functions into the framework of reductions from 2-party communication complexity to distributed algorithms.

We study fundamental graph parameters such as the Diameter and Radius in directed graphs, when distances are measured using a somewhat unorthodox but natural measure: the distance between $u$ and $v$ is the minimum of the shortest path distances from $u$ to $v$ and from $v$ to $u$. The center node in a graph under this measure can for instance represent the optimal location for a hospital to ensure the fastest medical care for everyone, as one can either go to the hospital, or a doctor can be sent to help. By computing All-Pairs Shortest Paths, all pairwise distances and thus the parameters we study can be computed exactly in $\tilde{O}(mn)$ time for directed graphs on $n$ vertices, $m$ edges and nonnegative edge weights. Furthermore, this time bound is tight under the Strong Exponential Time Hypothesis [Roditty-Vassilevska W. STOC 2013] so it is natural to study how well these parameters can be approximated in $O(mn^{1-ε})$ time for constant $ε>0$. Abboud, Vassilevska Williams, and Wang [SODA 2016] gave a polynomial factor approximation for Diameter and Radius, as well as a constant factor approximation for both problems in the special case where the graph is a DAG. We greatly improve upon these bounds by providing the first constant factor approximations for Diameter, Radius and the related Eccentricities problem in general graphs. Additionally, we provide a hierarchy of algorithms for Diameter that gives a time/accuracy trade-off.

Some of the most fundamental and well-studied graph parameters are the Diameter (the largest shortest paths distance) and Radius (the smallest distance for which a "center" node can reach all other nodes). The natural and important $ST$-variant considers two subsets $S$ and $T$ of the vertex set and lets the $ST$-diameter be the maximum distance between a node in $S$ and a node in $T$, and the $ST$-radius be the minimum distance for a node of $S$ to reach all nodes of $T$. The bichromatic variant is the special case in which $S$ and $T$ partition the vertex set. In this paper we present a comprehensive study of the approximability of $ST$ and Bichromatic Diameter, Radius, and Eccentricities, and variants, in graphs with and without directions and weights. We give the first nontrivial approximation algorithms for most of these problems, including time/accuracy trade-off upper and lower bounds. We show that nearly all of our obtained bounds are tight under the Strong Exponential Time Hypothesis (SETH), or the related Hitting Set Hypothesis. For instance, for Bichromatic Diameter in undirected weighted graphs with $m$ edges, we present an $\tilde{O}(m^{3/2})$ time $5/3$-approximation algorithm, and show that under SETH, neither the running time, nor the approximation factor can be significantly improved while keeping the other unchanged.