The reachability diameter (ReachDiam) of a directed graph is the maximum distance over all pairs u,v where v is reachable from u. This notion is present in the definition of shortcut sets, and the name was recently coined in that context by Haeupler, Jiang, and Saranurak [SOSA 2026]. While this is a very natural notion of diameter in directed graphs, and especially DAGs, it is so far not computationally explored. Other definitions of diameter in directed graphs are either trivial (infinite) in graphs that are not strongly connected (e.g., the classical definition) or are non-trivial only in highly restrictive graph classes (e.g., Min-Diameter). We initiate the problem of computing the (approximate) reachability diameter from a fine-grained complexity point of view. Under certain fine-grained assumptions, we prove that there is no algorithm in time 𝒪(n^{ω - ε}) that gives any approximation of ReachDiam in weighted graphs. Similarly, there is no algorithm with better than 2-approximation for unweighted graphs in this time. To supplement this, we provide algorithmic upper bounds that lead to additive approximation of ReachDiam for unweighted graphs. Hence, we establish a strong separation between the weighted and unweighted cases, which makes this type of diameter different in nature than other known notions. Considering the hardness in general weighted graphs, we also study special graph classes and get small constant approximations for DAGs with bounded width or graphs with bounded treewidth. Interestingly, our techniques also lead to exact hopsets with hopbound 2 for bounded treewidth graphs. This and some of our upper bounds for general graphs show technical connections between approximating ReachDiam and computing shortcut sets and hopsets.

We consider submodular maximization under increasing cardinality constraint and ask for a good incremental solution, i.e., an ordering of the ground set such that each prefix of the ordering yields a good solution for its respective cardinality. A classical result in this setting is that the greedy algorithm achieves a competitive ratio, i.e., an approximation guarantee across all cardinalities, of e/(e-1) ≈ 1.582. No better general guarantee was previously known. We present an adaptive scaling algorithm achieving a competitive ratio of 1.373. We complement our result by a lower bound of 1.25 on the best possible deterministic competitive ratio for incremental submodular maximization.

As the main contribution of this work we present deterministic edge coloring algorithms in the CONGEST model. In particular, we present an algorithm that edge colors any n-node graph with maximum degree Δ with (1+ε)Δ+O(log⁡n) colors in Õ(log2.5 n + log2 Δ log n) rounds. This brings the upper bound polynomially close to the lower bound of Ω(log n/log log n) rounds that also holds in the more powerful LOCAL model [Chang, He, Li, Pettie, Uitto; SODA'l8]. As long as Δ≥clog⁡n our algorithm uses fewer than 2Δ - 1 colors and to the best of our knowledge is the first polylogarithmic-round CONGEST algorithm achieving this for any range of Δ.

We give a combinatorial algorithm for computing exact maximum flows in directed graphs with n vertices and edge capacities from {1, …, U} in $\tilde O\left({{n^2}\log U}\right)$ time, which is near-optimal on dense graphs. This shaves an no(1)factor from the recent result of [Bernstein–Blikstad–Saranurak–Tu FOCS’24] and, more importantly, greatly simplifies their algorithm. We believe that ours is by a significant margin the simplest of all algorithms that go beyond $\tilde O(m\sqrt n )$ time in general graphs. To highlight this relative simplicity, we provide a full implementation of the algorithm in C++.The only randomized component of our work is the cut-matching game. Via existing tools, we show how to derandomize it for vertex-capacitated max flow and obtain a deterministic $\tilde O\left({{n^2}}\right)$ time algorithm. This marks the first deterministic near-linear time algorithm for this problem (or even for the special case of bipartite matching) in any density regime.

Vizing’s theorem guarantees that every graph with maximum degree $\Delta$ admits an edge coloring using $\Delta+1$ colors. In online settings-where edges arrive one at a time and must be colored immediately-a simple greedy algorithm uses at most $2 \Delta-1$ colors. Over thirty years ago, Bar-Noy, Motwani, and Naor [IPL’92] proved that this guarantee is optimal among deterministic algorithms when $\Delta=O(\log n)$, and among randomized algorithms when $\Delta=O(\sqrt{\log n})$. While deterministic improvements seemed out of reach, they conjectured that for graphs with $\Delta=\omega(\log n)$, randomized algorithms can achieve $(1+o(1)) \Delta$ edge coloring. This conjecture was recently resolved in the affirmative: a $(1+o(1)) \Delta$ coloring is achievable online using randomization for all graphs with $\Delta=\omega(\log n)$ [BSVW STOC’24]. Our results go further, uncovering two findings not predicted by the original conjecture. First, we give a deterministic online algorithm achieving $(1+o(1)) \Delta$-colorings for all $\Delta=\omega(\log n)$. Second, we give a randomized algorithm achieving $(1+o(1)) \Delta$ colorings already when $\Delta=\omega(\sqrt{\log n})$. Our results establish sharp thresholds for when greedy can be surpassed, and nearoptimal guarantees can be achieved - matching the impossibility results of [BNMN IPL’92], both deterministically and randomly.

We study online bipartite edge coloring, with nodes on one side of the graph revealed sequentially.

A recent breakthrough by [LNPSY STOC'21] showed that solving s-t vertex connectivity is sufficient (up to polylogarithmic factors) to solve (global) vertex connectivity in the sequential model. This raises a natural question: What is the relationship between s-t and global vertex connectivity in other computational models? In this paper, we demonstrate that the connection between global and s-t variants behaves very differently across computational models. In parallel and distributed models, we obtain almost tight reductions from global to s-t vertex connectivity. In PRAM, this leads to a $n^{ω+o(1)}$-work and $n^{o(1)}$-depth algorithm for vertex connectivity, improving over the 35-year-old $Õ(n^{ω+1})$-work $O(\mathrm{log}^2n)$-depth algorithm by [LLW FOCS'86], where $ω$ is the matrix multiplication exponent and $n$ is the number of vertices. In CONGEST, the reduction implies the first sublinear-round vertex connectivity algorithm when the diameter is moderately small. This answers an open question in [JM STOC'23]. In contrast, we show that global vertex connectivity is strictly harder than s-t vertex connectivity in the two-party communication setting, requiring $n^{1.5}$ bits of communication. The s-t variant was known to be solvable in $Õ(n)$ communication [BvdBEMN FOCS'22]. Our results resolve open problems raised by [MN STOC'20, BvdBEMN FOCS'22, AS SOSA'23]. At the heart of our results is a new graph decomposition framework we call common-neighborhood clustering, which can be applied in multiple models. Finally, we observe that global vertex connectivity cannot be solved without using s-t vertex connectivity by proving an s-t to global reduction in dense graphs in the PRAM and communication models.

We present a combinatorial algorithm for computing exact maximum flows in directed graphs with$n$vertices and edge capacities from$\{1, \ldots, U\}$in$n^{2+o(1)}\log U$time, which is almost optimal in dense graphs. Our algorithm is a novel implementation of the classical augmenting-path framework; we list augmenting paths more efficiently using a new variant of the push-relabel algorithm that uses additional edge weights to guide the algorithm, and we derive the edge weights by constructing a directed expander hierarchy. Even in unit-capacity graphs, this breaks the long-standing$O(m \cdot\min\{\sqrt{m},n^{2/3}\})$time bound of the previous combinatorial algorithms by Karzanov (1973) and Even and Tarjan (1975) when the graph has$m=\omega(n^{4/3})$edges. Notably, our approach does not rely on continuous optimization nor heavy dynamic graph data structures, both of which are crucial in the recent developments that led to the almost-linear time algorithm by Chen et al. (FOCS 2022). Our running time also matches the$n^{2+o(1)}$time bound of the independent combinatorial algorithm by Chuzhoy and Khanna (STOC 2024) for computing the maximum bipartite matching, a special case of maximum flow.

We devise a polynomial-time algorithm for partitioning a simple polygon P into a minimum number of star-shaped polygons. The question of whether such an algorithm exists has been open for more than four decades [Avis and Toussaint, Pattern Recognit., 1981] and it has been repeated frequently, for example in O’Rourke’s famous book [Art Gallery Theorems and Algorithms, 1987]. In addition to its strong theoretical motivation, the problem is also motivated by practical domains such as CNC pocket milling, motion planning, and shape parameterization.

The classic theorem of Vizing (Diskret. Analiz.’64) asserts that any graph of maximum degree Δ can be edge colored (offline) using no more than Δ+1 colors (with Δ being a trivial lower bound). In the online setting, Bar-Noy, Motwani and Naor (IPL’92) conjectured that a (1+o(1))Δ-edge-coloring can be computed online in n-vertex graphs of maximum degree Δ=ω(logn). Numerous algorithms made progress on this question, using a higher number of colors or assuming restricted arrival models, such as random-order edge arrivals or vertex arrivals (e.g., AGKM FOCS’03, BMM SODA’10, CPW FOCS’19, BGW SODA’21, KLSST STOC’22). In this work, we resolve this longstanding conjecture in the affirmative in the most general setting of adversarial edge arrivals. We further generalize this result to obtain online counterparts of the list edge coloring result of Kahn (J. Comb. Theory. A’96) and of the recent “local” edge coloring result of Christiansen (STOC’23).

In the dynamic approximate maximum bipartite matching problem we are given bipartite graph $G$ undergoing updates and our goal is to maintain a matching of $G$ which is large compared the maximum matching size $μ(G)$. We define a dynamic matching algorithm to be $α$ (respectively $(α, β)$)-approximate if it maintains matching $M$ such that at all times $|M | \geq μ(G) \cdot α$ (respectively $|M| \geq μ(G) \cdot α- β$). We present the first deterministic $(1-ε)$-approximate dynamic matching algorithm with $O(poly(ε^{-1}))$ amortized update time for graphs undergoing edge insertions. Previous solutions either required super-constant [Gupta FSTTCS'14, Bhattacharya-Kiss-Saranurak SODA'23] or exponential in $1/ε$ [Grandoni-Leonardi-Sankowski-Schwiegelshohn-Solomon SODA'19] update time. Our implementation is arguably simpler than the mentioned algorithms and its description is self contained. Moreover, we show that if we allow for additive $(1, ε\cdot n)$-approximation our algorithm seamlessly extends to also handle vertex deletions, on top of edge insertions. This makes our algorithm one of the few small update time algorithms for $(1-ε)$-approximate dynamic matching allowing for updates both increasing and decreasing the maximum matching size of $G$ in a fully dynamic manner.

We initiate the study of matroid problems in a new oracle model called dynamic oracle. Our algorithms in this model lead to new bounds for some classic problems, and a “unified” algorithm whose performance matches previous results developed in various papers for various problems. We also show a lower bound that answers some open problems from a few decades ago. Concretely, our results are as follows.

We settle the complexities of the maximum-cardinality bipartite matching problem (BMM) up to polylogarithmic factors in five models of computation: the two-party communication, AND query, OR query, XOR query, and quantum edge query models. Our results answer open problems that have been raised repeatedly since at least three decades ago [Hajnal, Maass, and Turan STOC’88; Ivanyos, Klauck, Lee, Santha, and de Wolf FSTTCS’12; Dobzinski, Nisan, and Oren STOC’14; Nisan SODA’21] and tighten the lower bounds shown by Beniamini and Nisan [STOC’21] and Zhang [ICALP’04]. We also settle the communication complexity of the generalizations of BMM, such as maximum-cost bipartite b-matching and transshipment; and the query complexity of unique bipartite perfect matching (answering an open question by Beniamini [2022]). Our algorithms and lower bounds follow from simple applications of known techniques such as cutting planes methods and set disjointness.

Despite a lot of recent progress in obtaining faster sequential matroid intersection algorithms, the fastest parallel poly(n)-query algorithm was still the straightforward O(n)-round parallel implementation of Edmonds' augmenting paths algorithm from the 1960s. Very recently, Chakrabarty-Chen-Khanna [FOCS'21] showed the lower bound that any, possibly randomized, parallel matroid intersection algorithm making poly(n) rank-queries requires Ω̃(n^{1/3}) rounds of adaptivity. They ask, as an open question, if the lower bound can be improved to Ω̃(n), or if there can be sublinear-round, poly(n)-query algorithms for matroid intersection. We resolve this open problem by presenting the first sublinear-round parallel matroid intersection algorithms. Perhaps surprisingly, we do not only break the Õ(n)-barrier in the rank-oracle model, but also in the weaker independence-oracle model. Our rank-query algorithm guarantees O(n^{3/4}) rounds of adaptivity, while the independence-query algorithm uses O(n^{7/8}) rounds of adaptivity, both making a total of poly(n) queries.

The matroid intersection problem is a fundamental problem that has been extensively studied for half a century. In the classic version of this problem, we are given two matroids M1 = (V, I1) and M2 = (V, I2) on a comment ground set V of n elements, and then we have to find the largest common independent set S ∈ I1 ∩ I2 by making independence oracle queries of the form ”Is S ∈ I1?” or ”Is S ∈ I2?” for S ⊆ V. The goal is to minimize the number of queries.