It is known that any n-point set in the d-dimensional Euclidean space ℝ^d, for d = O(1), admits: 1) A (1+ε)-spanner with maximum degree Õ(ε^{-d+1}) and with lightness Õ(ε^{-d}), for any ε > 0. 2) A (1+ε)-tree cover with Õ(n ⋅ ε^{-d+1}) trees and maximum degree of O(1) in each tree. Moreover, all the parameters in these constructions are optimal: For any 2 ≤ d = O(1), there exists an n-point set in ℝ^d, for which any (1+ε)-spanner has Ω̃(n⋅ε^{-d+1}) edges and lightness Ω̃(ε^{-d}). The upper bounds for Euclidean spanners rely heavily on the spatial property of cone partitioning in ℝ^d, which does not seem to extend to the wider family of doubling metrics, i.e., metric spaces of constant doubling dimension. In doubling metrics, a simple spanner construction from two decades ago, the net-tree spanner, has Õ(n⋅ε^{-d}) edges, and it could be transformed into a spanner of maximum degree Õ(ε^{-d}) and lightness Õ(n⋅ε^{-(d+1)}) by pruning redundant edges. Moreover, a careful refinement of the net-tree spanner yields a (1+ε)-tree cover with Õ(ε^{-d}) trees. Despite a large body of work, the problem of obtaining tight bounds for spanners and tree covers in the wider family of doubling metrics has remained elusive. We resolve this problem by presenting: 1) A surprisingly simple and tight lower bound, which shows that the net-tree spanner and its pruned version are optimal with respect to all the involved parameters. 2) A new construction of (1+ε)-tree covers with Õ(n⋅ε^{-d}) trees, with maximum degree O(1) in each tree. This construction is optimal with respect to the number of trees and maximum degree.

For a weighted graph $G = (V, E, w)$ and a designated source vertex $s \in V$, a spanning tree that simultaneously approximates a shortest-path tree w.r.t. source $s$ and a minimum spanning tree is called a shallow-light tree (SLT). Specifically, an $(α, β)$-SLT of $G$ w.r.t. $s \in V$ is a spanning tree of $G$ with root-stretch $α$ (preserving all distances between $s$ and the other vertices up to a factor of $α$) and lightness $β$ (its weight is at most $β$ times the weight of a minimum spanning tree of $G$). Despite the large body of work on SLTs, the basic question of whether a better approximation algorithm exists was left untouched to date, and this holds in any graph family. This paper makes a first nontrivial step towards this question by presenting two bicriteria approximation algorithms. For any $ε>0$, a set $P$ of $n$ points in constant-dimensional Euclidean space and a source $s\in P$, our first (respectively, second) algorithm returns, in $O(n \log n \cdot {\rm polylog}(1/ε))$ time, a non-Steiner (resp., Steiner) tree with root-stretch $1+O(ε\log ε^{-1})$ and weight at most $O(\mathrm{opt}_ε\cdot \log^2 ε^{-1})$ (resp., $O(\mathrm{opt}_ε\cdot \log ε^{-1})$), where $\mathrm{opt}_ε$ denotes the minimum weight of a non-Steiner (resp., Steiner) tree with root-stretch $1+ε$.

Graph coloring is a fundamental problem in computer science. In the semi-streaming model, an input graph G on n vertices and maximum degree Δ is presented as a stream of edges, and the goal is to compute a vertex coloring using a small number of colors while storing only Õ(n) bits of memory. Recent work has revealed an exponential separation between randomized and deterministic approaches in this setting: while randomized algorithms can achieve a (Δ+1)-coloring in a single pass [Assadi, Chen, and Khanna, 2019], any single-pass deterministic algorithm requires exp(Δ^Ω(1)) colors [Assadi, Chen, and Sun, 2022]. Consequently, deterministic algorithms that use few colors must necessarily make multiple passes over the stream. Prior to this work, the best known deterministic trade-offs were: an O(Δ²)-coloring in 2 passes, an O(Δ)-coloring in O(log Δ) passes [Assadi, Chen, and Sun, 2022], and a (Δ+1)-coloring in O(log Δ ⋅ log log Δ) passes [Assadi, Chakrabarti, Ghosh, and Stoeckl, 2023]. It remained open whether better trade-offs - particularly with sub-logarithmic pass complexity and linear-in-Δ palette size - were achievable. In this paper, we present a new deterministic semi-streaming algorithm that computes an O(Δ)-coloring in O(√{log Δ}) passes. This is the first deterministic streaming algorithm to achieve a coloring with palette size linear-in-Δ using sublogarithmic-in-Δ passes.

A \(t\)-stretch tree cover of a metric space \(M = (X, \delta)\), for a parameter \(t \ge 1\), is a collection of trees such that every pair of points has a \(t\)-stretch path in one of the trees. Tree covers provide an important sketching tool that has found various applications over the years. The celebrated Dumbbell Theorem by Arya et al. [STOC’95] states that any set of points in the Euclidean plane admits a \((1+\epsilon)\)-stretch tree cover with \(O_\epsilon(1)\) trees. This result extends to any (constant) dimension and was also generalized for arbitrary doubling metrics by Bartal et al. [ICALP’19].

In their seminal paper, Althöfer et al. (DCG 1993) introduced the greedy spanner and showed that, for any weighted planar graph \(G\), the weight of the greedy \((1+\epsilon)\)-spanner is at most \((1+\tfrac{2}{\epsilon})\cdot \textrm w(\mathsf{MST}(G))\), where \(\textrm w(\mathsf{MST}(G))\) is the weight of a minimum spanning tree \(\mathrm{MST}(G)\) of \(G\). This bound is optimal in an \(\textcolor{#ff6666}{existential\ sense}\): there exist planar graphs \(G\) for which any \((1+\epsilon)\)-spanner has a weight of at least \((1+\tfrac{2}{\epsilon})\cdot w(\mathrm{MST}(G))\).

Vizing’s theorem states that any \(n\)-vertex \(m\)-edge graph of maximum degree \(\Delta\) can be edge colored using at most \(\Delta + 1\) different colors. Vizing’s original proof is easily translated into a deterministic \(O(mn)\) time algorithm. This deterministic time bound was subsequently improved to \(\tilde{O}(m\sqrt{n})\) time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985].

Vizing’s theorem states that any n -vertex m -edge graph of maximum degree Δ can be edge colored using at most Δ + 1 different colors [Vizing, 1964]. Vizing’s original proof is algorithmic and shows that such an edge coloring can be found in O(mn) time. This was subsequently improved to \(\tilde{O}(m\sqrt {n})\) time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985]. 1 Very recently, independently and concurrently, using randomization, this runtime bound was further improved to \(\tilde{O}(n^2)\) by [Assadi, 2024] and \(\tilde{O}(mn^{1/3})\) by [Bhattacharya, Carmon, Costa, Solomon and Zhang, 2024] (and subsequently to \(\tilde{O}(mn^{1/4})\) by [Bhattacharya, Costa, Solomon and Zhang, 2024]). In this article, we present a randomized algorithm that computes a Δ + 1-edge coloring in near-linear time—in fact, only O(m log Δ) time—with high probability, giving a near-optimal algorithm for this fundamental problem .

Given a graph, an edge coloring assigns colors to edges so that no pairs of adjacent edges share the same color. We are interested in edge coloring algorithms under the W-streaming model. In this model, the algorithm does not have enough memory to hold the entire graph, so the edges of the input graph are read from a data stream one by one in an unknown order, and the algorithm needs to print a valid edge coloring in an output stream. The performance of the algorithm is measured by the amount of space and the number of different colors it uses. This streaming edge coloring problem has been studied by several works in recent years. When the input graph contains n vertices and has maximum vertex degree Δ, it is known that in the W-streaming model, an O(Δ²)-edge coloring can be computed deterministically with Õ(n) space [Ansari, Saneian, and Zarrabi-Zadeh, 2022], or an O(Δ^{1.5})-edge coloring can be computed by a Õ(n)-space randomized algorithm [Behnezhad, Saneian, 2024] [Chechik, Mukhtar, Zhang, 2024]. In this paper, we achieve polynomial improvement over previous results. Specifically, we show how to improve the number of colors to Õ(Δ^{4/3+ε}) using space Õ(n) deterministically, for any constant ε > 0. This is the first deterministic result that bypasses the quadratic bound on the number of colors while using near-linear space.

Vizing’s Theorem from 1964 states that any n-vertex m-edge graph with maximum degree Δ can be edge colored using at most Δ + 1 colors. For over 40 years, the state-of-the-art running time for computing such a coloring, obtained independently by Arjomandi [1982] and by Gabow, Nishizeki, Kariv, Leven and Terada [1985], was . Very recently, this time bound was improved in two independent works, by Bhattacharya, Carmon, Costa, Solomon and Zhang to , and by Assadi to Õ (n2).

The dynamic set cover problem has been subject to extensive research since the pioneering works of [BHI, ICALP’15] and [GKKP17, STOC’17]. The input is a set system (U, S ) on a fixed collection S of sets and a dynamic universe of elements, where each element appears in a most f sets and the cost of each set lies in the range [1/C, 1]; the ultimate goal is to maintain a set cover under insertions and deletions of elements, with optimal bounds on both the approximation factor and the update time.

Vizing’s theorem states that any n-vertex m-edge graph of maximum degree Δ can be edge colored using at most Δ + 1 different colors [Vizing, 1964]. Vizing’s original proof is algorithmic and shows that such an edge coloring can be found in O(mn) time. This was subsequently improved to Õ(m√n) time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985]. Very recently, independently and concurrently, using randomization, this runtime bound was further improved to Õ(n2) by [Assadi, 2024] and Õ(mn1/3) by [Bhattacharya, Carmon, Costa, Solomon and Zhang, 2024] (and subsequently to Õ(mn1/4) by [Bhattacharya, Costa, Solomon and Zhang, 2024]). In this paper, we present a randomized algorithm that computes a (Δ+1)-edge coloring in near-linear time—in fact, only O(mlogΔ) time—with high probability, giving a near-optimal algorithm for this fundamental problem.

Euclidean spanners are important geometric objects that have been extensively studied since the 1980s. The two most basic “compactness” measures of a Euclidean spanner$E$12We shall identify a graph$H = (X,E)$with its edge set$E$. All edge weights are given by the Euclidean distances. are the size (number of edges)$\vert E\vert$and the weight (sum of edge weights)$\Vert E\Vert$. The state-of-the-art constructions of Euclidean$(1+\epsilon)$-spanners in$\mathbb{R}^{d}$have$o_{d}(_{n\cdot\epsilon^{-d+1}})$edges (or sparsity$O_{d}(\epsilon^{-d+1}))$and weight$O_{d}(\epsilon^{-d} \log \epsilon^{-1}) \cdot\Vert E_{\text{mst}}\Vert$(or lightness$O_{d}(\epsilon^{-d}\log\epsilon^{-1}))$; here$O_{d}$suppresses a factor of$d^{O(d)}$and$\Vert E_{\text{mst}}\Vert$denotes the weight of a minimum spanning tree of the input point set. Importantly, these two upper bounds are (near-)optimal (up to the$d^{O(d)}$factor and disregarding the factor of$\log(\epsilon^{-1})$in the lightness bound) for some extremal instances [Le and Solomon, 2019], and therefore they are (near-)optimal in an existential sense. Moreover, both these upper bounds are attained by the same construction-the classic greedy spanner, whose sparsity and lightness are not only existentially optimal, but they also significantly outperform those of any other Euclidean spanner construction studied in an experimental study by [Farshi-Gudmundsson, 2009] for various practical point sets in the plane. This raises the natural question of whether the greedy spanner is (near-) optimal for any point set instance? Motivated by this question, we initiate the study of instance optimal Euclidean spanners. Our results are two-fold. •Rather surprisingly (given the aforementioned experimental study), we demonstrate that the greedy spanner is far from being instance optimal, even when allowing its stretch to grow. More concretely, we design two hard instances of point sets in the plane, where the greedy$(1+x\epsilon)$-spanner (for basically any parameter$x \geq 1$) has$\Omega_{x}(\epsilon^{-1/2})\cdot\vert E_{\text{spa}} \vert$edges and weight$\Omega_{x}(\epsilon^{-1})\cdot\Vert E_{\text{light}}\Vert$, where$E_{\text{spa}}$and$E_{\text{light}}$denote the per-instance sparsest and lightest$(1 +\epsilon)$-spanners, respectively, and the$\Omega_{x}$notation suppresses a polynomial dependence on$1/x$. •As our main contribution, we design a new construction of Euclidean spanners, which is inherently different from known constructions, achieving the following bounds: a stretch of$1+\epsilon\cdot 2^{O(\log^{*}(d/\epsilon)}$with$O(1)\cdot\vert E_{\text{spa}}\vert$edges and weight$O(1)$. $\Vert E_{ \text{light}}\Vert$. In other words, we show that a slight increase to the stretch suffices for obtaining instance optimality up to an absolute constant for both sparsity and lightness. Remarkably, there is only a log-star dependence on the dimension in the stretch, and there is no dependence on it whatsoever in the number of edges and weight. In general, for any integer$k\geq 1$, we can construct a Euclidean spanner in$\mathbb{R}^{d}$of stretch$1+\epsilon\cdot 2^{O(k)}$with$O(\log^{(k)}(\epsilon^{-1})+\log^{(k-1)}(d))\cdot\vert E_{\text{spa}}\vert$edges and weight$O(\log^{(k)}(\epsilon^{-1})+\log^{(k-1)}(d))\cdot\Vert E_{\text{light}}\Vert$, where$\log^{(k)}$denotes the k-iterated logarithm.

Vizing's theorem states that any n-vertex m-edge graph of maximum degree$\Delta$can be edge colored using at most$\Delta+1$different colors [Diskret. Analiz, '64]. Vizing's original proof is algorithmic and shows that such an edge coloring can be found in$\tilde{O}(mn)$time. This was subsequently improved to$\tilde{O}(m\sqrt{n})$, independently by Arjomandi [1982] and by Gabow et al. [1985]. In this paper we present an algorithm that computes such an edge coloring in$\tilde{O}(mn^{1/3})$, time, giving the first polynomial improvement for this fundamental problem in over 40 years.

The dynamic set cover problem has been subject to growing research attention in recent years. In this problem, we are given as input a dynamic universe of at most$n$elements and a fixed collection of$m$sets, where each element appears in a most$f$sets and the cost of each set is in [1/C, 1], and the goal is to efficiently maintain an approximate minimum set cover under element updates. Two algorithms that dynamize the classic greedy algorithm are known, providing$O(\log n)$and$((1+\epsilon)\ln n)$-approximation with amortized update times$O(f \log n)$and,$O(\frac{f \log n}{\epsilon})$, respectively [GKKP (STOC'17); SU (STOC'23)]. The question of whether one can get approximation$O(\log n)$(or even worse) with low worst-case update time has remained open — only the naive$O(f\cdot n)$time bound is known, even for unweighted instances. In this work we devise the first amortized greedy algorithm that is amenable to an efficient deamortization, and also develop a lossless deamortization approach suitable for the set cover problem, the combination of which yields a$((1+\epsilon)\ln n){-}$approximation algorithm with a worst-case update time of$O(\frac{f \log n}{\epsilon^{2}})$. Our worst-case time bound — the first to break the naive$O(f\cdot n)$bound — matches the previous best amortized bound, and actually improves its$\epsilon$-dependence. Further, to demonstrate the applicability of our deamortization approach, we employ it, in conjunction with the primal-dual amortized algorithm of [BHN (FOCS'19)], to obtain a$((1+\epsilon)f)$-approximation algorithm with a worst-case update time of$O(\frac{f \log n}{\epsilon^{2}})$, improving over the previous best bound of$O(\frac{f \cdot \log ^{2}(C n)}{-3})\ [$BHNW (SODA'21)]. Finally, as direct implications of our results for set cover, we (i) achieve the first nontrivial worst-case update time for the dominating set problem, and (ii) improve the state-of-the-art worst-case update time for the vertex cover problem.

Given a simple weighted directed graph $G = (V, E, ω)$ on $n$ vertices as well as two designated terminals $s, t\in V$, our goal is to compute the shortest path from $s$ to $t$ avoiding any pair of presumably failed edges $f_1, f_2\in E$, which is a natural generalization of the classical replacement path problem which considers single edge failures only. This dual failure replacement paths problem was recently studied by Vassilevska Williams, Woldeghebriel and Xu [FOCS 2022] who designed a cubic time algorithm for general weighted digraphs which is conditionally optimal; in the same paper, for unweighted graphs where $ω\equiv 1$, the authors presented an algebraic algorithm with runtime $\tilde{O}(n^{2.9146})$, as well as a conditional lower bound of $n^{8/3-o(1)}$ against combinatorial algorithms. However, it was unknown in their work whether fast matrix multiplication is necessary for a subcubic runtime in unweighted digraphs. As our primary result, we present the first truly subcubic combinatorial algorithm for dual failure replacement paths in unweighted digraphs. Our runtime is $\tilde{O}(n^{3-1/18})$. Besides, we also study algebraic algorithms for digraphs with small integer edge weights from $\{-M, -M+1, \cdots, M-1, M\}$. As our secondary result, we obtained a runtime of $\tilde{O}(Mn^{2.8716})$, which is faster than the previous bound of $\tilde{O}(M^{2/3}n^{2.9144} + Mn^{2.8716})$ from [Vassilevska Williams, Woldeghebriela and Xu, 2022].

In this paper, we study the problem of computing an edge-coloring in the (one-pass) W-streaming model. In this setting, the edges of an n-node graph arrive in an arbitrary order to a machine with a relatively small space, and the goal is to design an algorithm that outputs, as a stream, a proper coloring of the edges using the fewest possible number of colors. Behnezhad et al. [Behnezhad et al., 2019] devised the first non-trivial algorithm for this problem, which computes in Õ(n) space a proper O(Δ²)-coloring w.h.p. (here Δ is the maximum degree of the graph). Subsequent papers improved upon this result, where latest of them [Ansari et al., 2022] showed that it is possible to deterministically compute an O(Δ²/s)-coloring in O(ns) space. However, none of the improvements succeeded in reducing the number of colors to O(Δ^{2-ε}) while keeping the same space bound of Õ(n). In particular, no progress was made on the question of whether computing an O(Δ)-coloring is possible with roughly O(n) space, which was stated in [Behnezhad et al., 2019] to be an interesting open problem. In this paper we bypass the quadratic bound by presenting a new randomized Õ(n)-space algorithm that uses Õ(Δ^{1.5}) colors.

Given a directed graph G = (V, E, ω) on n vertices with positive edge weights as well as two designated terminals s, t ∈ V, our goal is to compute the shortest path from s to t avoiding any pair of presumably failed edges f1,f2 ∈ E, which is a natural generalization of the classical replacement path problem which considers single edge failures only.

Dynamic all-pairs shortest paths is a well-studied problem in the field of dynamic graph algorithms. More specifically, given a directed weighted graph G = (V, E, ω) on n vertices which undergoes a sequence of vertex or edge updates, the goal is to maintain distances between any pair of vertices in V. In a classical work by [Demetrscu and Italiano, 2004], the authors showed that all-pairs shortest paths can be maintained deterministically in amortized Õ(n2) time1, which is nearly optimal. For worst-case update time guarantees, so far the best randomized algorithm has Õ(n3-1/3) time [Abraham, Chechik, Krinninger, 2017], and the best deterministic algorithm needs Õ(n3-2/7) time [Probst Gutenberg, Wulff-Nilsen, 2020]. We provide a faster deterministic worst-case update time of Õ(n3-20/61) for fully dynamic all-pairs shortest paths. To achieve this improvement, we study a natural variant of this problem where a hop constraint is imposed on shortest paths between vertices; that is, given a parameter h, the h-hop shortest path between any pair of vertices s,t ∈ V is a path from s to t with at most h edges whose total weight is minimized. As a result which might be of independent interest, we give a deterministic algorithm that maintains all-pairs h-hop shortest paths under vertex deletions in total update time Õ(n3h + Kn2n2), where K bounds the total number of vertex deletions. * This publication is part of a project that has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 803118 UncertainENV). 1 Õ(·) hides poly-log factors.

Given an undirected unweighted graph G = (V, E) on n vertices and m edges, a subgraph H⊆ G is a spanner of G with stretch function f: ℝ+ → ℝ+, iff for every pair s, t of vertices in V, distH(s, t)≤ f(distG(s, t)). When f(d) = d + o(d), H is called a sublinear additive spanner; when f(d) = d + o(n), H is called an additive spanner, and f(d) − d is usually called the additive stretch of H.

In a weighed directed graph $G=(V, E, \omega)$ with m edges and n vertices, we are interested in its basic graph parameters such as diameter, radius and eccentricities, under the nonstandard measure of min-distance which is defined for every pair of vertices $u, v \in V$ as the minimum of the shortest path distances from u to v and from v to u. Similar to standard shortest paths distances, computing graph parameters exactly in terms of min-distances essentially requires $\tilde{\Omega}(m n)$ time under plausible hardness conjectures1. Hence, for faster running time complexities we have to tolerate approximations. Abboud, Vassilevska Williams and Wang [SODA 2016] were the first to study min-distance problems, and they obtained constant factor approximation algorithms in acyclic graphs, with running time $\tilde{O}(m)$ and $\tilde{O}(m \sqrt{n})$ for diameter and radius, respectively. The time complexity of radius in acyclic graphs was recently improved to $\tilde{O}(m)$ by Dalirrooyfard and Kaufmann [ICALP 2021], but at the cost of an $O(\log n)$ approximation ratio. For general graphs, the authors of [DWV+, ICALP 2019] gave the first constant factor approximation algorithm for diameter, radius and eccentricities which runs in time $\tilde{O}(m \sqrt{n})$; besides, for the diameter problem, the running time can be improved to $\tilde{O}(m)$ while blowing up the approximation ratio to $O(\log n)$. A natural question is whether constant approximation and near-linear time can be achieved simultaneously for diameter, radius and eccentricities; so far this is only possible for diameter in the restricted setting of acyclic graphs. In this paper, we answer this question in the affirmative by presenting near-linear time algorithms for all three parameters in general graphs.1As usual, the $\tilde{O}(\cdot)$ notation hides poly-logarithmic factors in n

Let $G = (V, E)$ be an undirected connected simple graph on $n$ vertices. A cut-equivalent tree of $G$ is an edge-weighted tree on the same vertex set $V$, such that for any pair of vertices $s, t\in V$, the minimum $(s, t)$-cut in the tree is also a minimum $(s, t)$-cut in $G$, and these two cuts have the same cut value. In a recent paper [Abboud, Krauthgamer and Trabelsi, 2021], the authors propose the first subcubic time algorithm for constructing a cut-equivalent tree. More specifically, their algorithm has $\widetilde{O}(n^{2.5})$ running time. In this paper, we improve the running time to $\hat{O}(n^2)$ if almost-linear time max-flow algorithms exist. Also, using the currently fastest max-flow algorithm by [van den Brand et al, 2021], our algorithm runs in time $\widetilde{O}(n^{17/8})$.

Graph spanners have been extensively studied in the literature of graph algorithms. In an undirected weighted graph G = (V, E,ω) on n vertices, a t-spanner of G is a subgraph that preserves pairwise distances up to a multiplicative stretch factor of t . It is well-known that, for any integer k, a (2k - 1)-spanner with O(n1+1/k ) edges always exists, and the stretch-sparsity balance is tight under the girth conjecture by Erdos. In this paper, we are interested in efficient algorithms for spanners in the distributed setting. Specifically, we present constant-round congested clique algorithms for spanners with nearly optimal stretch-sparsity trade-offs: (2k-1)-spanners with O(n1+1/k ) edges in unweighted graphs (i.e. ω ≡ 1). (1 + ε) (2k - 1)-spanners with O(n1+1/k ) edges in weighted graphs. (2k-1)-spanners withO(kn1+1/k ) edges in weighted graphs.

Let G = (V, E) be an unweighted undirected graph on n vertices and m edges. For a fixed pair of real values α ≥ 1, β ≥ 0, an (α, β) distance oracle of G is a space-efficient data structure that answers, in constant time, for any pair of vertices u,v ∊ V a distance estimate within the range of [dist(u, v), α·dist(u, v) + β]; here dist denotes distances in the graph G. Two main concerns in designing distance oracles are the approximation ratio (the stretch) and the construction time. A classical result was given in [Baswana, Goyaland and Sen 2005] which builds a (2, 3) distance oracle with Õ(n5/3) space in Õ(n2) time. Recently, [Akav and Roditty, 2020] broke the quadratic running time at the expense of increasing the stretch. More specifically, they obtained an algorithm that constructs a (2 + ∊, 5) distance oracle with space Õ(n11/6) in O(m + n2–Ω(∊)) time for any constant ∊ ∊ (0, 1/2). In this paper, we show that one can beat the quadratic running time without compromising on the stretch. More specifically, our algorithm constructs, with high probability, a (2, 3) distance oracle with Õ(n5/3) space in Õ(m+n1.987) time. As a secondary extension, we could further reduce the preprocessing time to Õ(m+n7/4+∊) by tolerating a (2, O(1/∊)) stretch, for any constant ∊ > 0. Finally, this preprocessing time could be pushed even further to Õ(m + n5/3+∊) if we allow a stretch of (2 + ∊, c), where c = c(∊) is a constant depending exponentially on 1/∊.

In this paper, we show that the time complexity of monotone min-plus product of two n× n matrices is Õ(n(3+ω)/2)=Õ(n2.687), where ω < 2.373 is the fast matrix multiplication exponent [Alman and Vassilevska Williams 2021]. That is, when A is an arbitrary integer matrix and B is either row-monotone or column-monotone with integer elements bounded by O(n), computing the min-plus product C where Ci,j=mink{Ai,k+Bk,j} takes Õ(n(3+ω)/2) time, which greatly improves the previous time bound of Õ(n(12+ω)/5)=Õ(n2.875) [Gu, Polak, Vassilevska Williams and Xu 2021]. Then by simple reductions, this means the case that A is arbitrary and the columns or rows of B are bounded-difference can also be solved in Õ(n(3+ω)/2) time, whose previous result gives time complexity of Õ(n2.922) [Bringmann, Grandoni, Saha and Vassilevska Williams 2016]. So the case that both of A and B are bounded-difference also has Õ(n(3+ω)/2) time algorithm, whose previous results give time complexities of Õ(n2.824) [Bringmann, Grandoni, Saha and Vassilevska Williams 2016] and Õ(n2.779) [Chi, Duan and Xie 2022]. Many problems are reducible to these problems, such as language edit distance, RNA-folding, scored parsing problem on BD grammars [Bringmann, Grandoni, Saha and Vassilevska Williams 2016]. Thus, their complexities are all improved.

In this paper we are interested in deterministically computing maximum flows in undirected simple graphs where edges have unit capacities. When the input graph has n vertices and m edges, and the maximum flow is known to be upper bounded by τ as prior knowledge, our algorithm has running time Õ(m + n^{5/3}τ^{1/2}); in the extreme case where τ = Θ(n), our algorithm has running time Õ(n^{2.17}). This always improves upon the previous best deterministic upper bound Õ(n^{9/4}τ^{1/8}) by [Duan, 2013]. Furthermore, when τ ≥ n^{0.67} our algorithm is faster than a classical upper bound of O(m + nτ^{3/2}) by [Karger and Levin, 1998].

Given a directed graph G = (V, E, ω) with positive integer edge weights that undergoes a sequence of edge insertions, we are interested in maintaining approximate single-source shortest paths in the incremental graph G. In a very recent paper, [Gutenberg et al., 2020] proposed a deterministic algorithm for this problem with Õ(n2 log W) total update time, where n = |V| and W denotes the maximum edge weight. When the underlying graph is super dense, namely, the total number of insertions m is , their upper bound is essentially optimal. For sparse graphs, the only known result is due to [Henzinger et al., 2014], whose algorithm is randomized and works in Õ(mn0.9 log W) total update time under the assumption of oblivious non-adaptive adversary. In this work, we provide two algorithms for this problem when the graph is sparse. The first one is a simple deterministic algorithm with Õ(m5/3 log W) total update time. The second one is a randomized algorithm with Õ ((mn1/2 + m7/5) log W) total update time, which improves over both previous results when m = O(n1.42); moreover, this randomized algorithm plays against adaptive adversaries. Our algorithms are the first to break the O(mn) bound with adaptive adversaries for sparse graphs.

We study the maximum weight perfect $f$-factor problem on any general simple graph $G=(V,E,w)$ with positive integral edge weights $w$, and $n=|V|$, $m=|E|$. When we have a function $f:V\rightarrow \mathbb{N}_+$ on vertices, a perfect $f$-factor is a generalized matching so that every vertex $u$ is matched to $f(u)$ different edges. The previous best algorithms on this problem have running time $O(m f(V))$ [Gabow 2018] or $\tilde{O}(W(f(V))^{2.373}))$ [Gabow and Sankowski 2013], where $W$ is the maximum edge weight, and $f(V)=\sum_{u\in V}f(u)$. In this paper, we present a scaling algorithm for this problem with running time $\tilde{O}(mn^{2/3}\log W)$. Previously this bound is only known for bipartite graphs [Gabow and Tarjan 1989]. The running time of our algorithm is independent of $f(V)$, and consequently it first breaks the $Ω(mn)$ barrier for large $f(V)$ even for the unweighted $f$-factor problem in general graphs.

Low-stretch spanning tree has been an important graphtheoretic object, as it is one of the building blocks for fast algorithms that solve symmetrically diagonally dominant linear systems, and a significant line of research has been devoted to finding constructions with optimal average stretch. In a very recent work by Goranci and Forster [STOC 2019], the authors initiated the study of low-stretch spanning trees in the dynamic setting, and they proposed a dynamic algorithm that maintains a spanning tree in amortized update time with subpolynomial stretch in an unweighted graph on n vertices undergoing edge insertions and deletions demanded by an oblivious adversary. Our main results are twofold. First, we substantially improve the update time of Goranci and Forster [STOC 2019] from to a subpolynomial of no(1). Second, we generalize our result to weighted graphs under the decremental setting. As far as we know, this is the first non trivial dynamic algorithm for maintaining low-stretch spanning tree for weighted graphs.

In the fully dynamic maximal independent set (MIS) problem our goal is to maintain an MIS in a given graph G while edges are inserted and deleted from the graph. The first non-trivial algorithm for this problem was presented by Assadi, Onak, Schieber, and Solomon [STOC 2018] who obtained a deterministic fully dynamic MIS with O(m3/4) update time. Later, this was independently improved by Du and Zhang and by Gupta and Khan [arXiv 2018] to Õ(m2/3) update time1Du and Zhang [arXiv 2018] also presented a randomized algorithm against an oblivious adversary with Õ(√m) update time. The current state of art is by Assadi, Onak, Schieber, and Solomon [SODA 2019] who obtained randomized algorithms against oblivious adversary with Õ(√n) and Õ(m1/3) update times. In this paper, we propose a dynamic randomized algorithm against oblivious adversary with expected worst-case update time of O(log4n). As a direct corollary, one can apply the black-box reduction from a recent work by Bernstein, Forster, and Henzinger [SODA 2019] to achieve O(log6n) worst-case update time with high probability. This is the first dynamic MIS algorithm with very fast update time of poly-log.

Given an undirected simple graph G = (V, E) that undergoes edge insertions and deletions, we wish to efficiently maintain an edge coloring with only a few colors. The previous best dynamic algorithm by [3] could deterministically maintain a valid edge coloring using 2Δ – 1 colors with O(log Δ) update time, where Δ stands for the current maximum vertex degree of graph G. In this paper, we first propose a new static (1 + ∊)Δ edge coloring algorithm that runs in near-linear time. Based on this static algorithm, we show that there is a randomized dynamic algorithm for this problem that only uses (1 + ∊)Δ colors with O(log8 n/∊4) amortized update time when Δ ≥ Ω(log2 n/∊2), where ∊ > 0 is an arbitrarily small constant.