We study the maximum flow problem in directed networks with real capacities in the parallel setting. For a network with n vertices and m arcs, we show that a randomized parallel implementation of a variant of the strongly polynomial max-flow algorithm of Dadush, Orlin, Sidford, and Végh [Dadush et al., 2026] runs in Õ(mn) work and Õ(m) depth. This improves upon the previously described tradeoffs between work and depth for strongly polynomial parallel maximum flow algorithms: earlier Õ(n³)-work algorithms have Õ(n²) depth [Goldberg and Tarjan, 1988; Shiloach and Vishkin, 1982], while the known Õ(m)-depth approach uses Õ(mn³) work [Orlin, 1993].

In this paper, we show new strongly polynomial work-depth tradeoffs for computing single-source shortest paths (SSSP) in non-negatively weighted directed graphs in parallel. Most importantly, we prove that directed SSSP can be solved within \(\tilde O(m+n^{2-\epsilon})\) work and \(\tilde O(n^{1-\epsilon})\) depth for some positive \(\epsilon \lt 0\). In particular, for dense graphs with non-negative real weights, we provide the first nearly work-efficient strongly polynomial algorithm with sublinear depth.

In this paper, we consider a perturbation-based metric of predictive faithfulness of feature rankings (or attributions) that we call PGI squared When applied to decision tree-based regression models, the metric can be computed exactly and efficiently for arbitrary independent feature perturbation distributions. In particular, the computation does not involve Monte Carlo sampling that has been typically used for computing similar metrics and which is inherently prone to inaccuracies. As a second contribution, we proposed a procedure for constructing feature ranking based on PGI squared. Our results indicate the proposed ranking method is comparable to the widely recognized SHAP explainer, offering a viable alternative for assessing feature importance in tree-based models.

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

In this paper, we show new data structures maintaining approximate shortest paths in sparse directed graphs with polynomially bounded non-negative edge weights under edge insertions. We give more efficient incremental $(1+ε)$-approximate APSP data structures that work against an adaptive adversary: a deterministic one with $\tilde{O}(m^{3/2}n^{3/4})$ total update time and a randomized one with $\tilde{O}(m^{4/3}n^{5/6})$ total update time. For sparse graphs, these both improve polynomially upon the best-known bound against an adaptive adversary. To achieve that, building on the ideas of [Chechik-Zhang, SODA'21] and [Kyng-Meierhans-Probst Gutenberg, SODA'22], we show a near-optimal $(1+ε)$-approximate incremental SSSP data structure for a special case when all edge updates are adjacent to the source, that might be of independent interest. We also describe a very simple and near-optimal \emph{offline} incremental $(1+ε)$-approximate SSSP data structure. While online near-linear partially dynamic SSSP data structures have been elusive so far (except for dense instances), our result excludes using certain types of impossibility arguments to rule them out. Additionally, our offline solution leads to near-optimal and deterministic all-pairs bounded-leg shortest paths data structure for sparse graphs.

In the restricted shortest paths problem, we are given a graph G whose edges are assigned two non-negative weights: lengths and delays, a source s, and a delay threshold D. The goal is to find, for each target t, the length of the shortest (s, t )-path whose total delay is at most D. While this problem is known to be NP-hard [GJ79], (1 + ε )-approximate algorithms running in Õ (mn ) time1 [GRKL01, LR01] given more than twenty years ago have remained the state-of-the-art for directed graphs. An open problem posed by [Ber12] — who gave a randomized m · no (1) time bicriteria (1 + ε, 1 + ε )-approximation algorithm for undirected graphs — asks if there is similarly an o (mn) time approximation scheme for directed graphs.

Le and Wulff-Nilsen [SODA ’24] initiated a systematic study of VC set systems to unweighted Kh-minor-free directed graphs. We extend their results in the following ways:

In this paper, we show the first deterministic parallel algorithm for computing the strongly connected components (SCCs) of a directed graph beyond the full transitive closure computation. For any parameter t ϵ [1, n], the algorithm can identify the SCCs within Õ(nt2 + m) work and Õ(n/t) depth. This matches (up to polylogarithmic factors) the state-of-the-art deterministic tradeoff for st-reachability and solves an open problem of Spencer [J. ACM '97].

In this paper we consider maintaining strongly connected components (SCCs) of a directed planar graph subject to edge insertions and deletions. We show a data structure maintaining an implicit representation of the SCCs within Õ(n^{6/7}) worst-case time per update. The data structure supports, in O(log²{n}) time, reporting vertices of any specified SCC (with constant overhead per reported vertex) and aggregating vertex information (e.g., computing the maximum label) over all the vertices of that SCC. Furthermore, it can maintain global information about the structure of SCCs, such as the number of SCCs, or the size of the largest SCC. To the best of our knowledge, no fully dynamic SCCs data structures with sublinear update time have been previously known for any major subclass of digraphs. Our result should be contrasted with the n^{1-o(1)} amortized update time lower bound conditional on SETH, which holds even for dynamically maintaining whether a general digraph has more than two SCCs.

We study the maximum s, t-flow oracle problem on planar directed graphs where the goal is to design a data structure answering max s, t-flow value (or equivalently, min s, t-cut value) queries for arbitrary source- target pairs (s, t). For the case of polynomially bounded integer edge capacities, we describe an exact max s, t-flow oracle with truly subquadratic space and preprocessing, and sublinear query time. Moreover, if (1 — ɛ)-approximate answers are acceptable, we obtain a static oracle with near-linear preprocessing and Õ(n3/4) query time and a dynamic oracle supporting edge capacity updates and queries in Õ(n6/7) worst-case time.

Exact computation of shortest paths in weighted graphs has been traditionally studied in one of two settings. First, one can assume that the edge weights are real numbers and all the performed operations on reals (typically comparisons and additions) take constant time. Classical Dijkstra's and Bellman-Ford algorithms have been described in this setting.

We study the problem of dynamically maintaining the connected components of an undirected graph subject to edge insertions and deletions. We give the first parallel algorithm for the problem that is work-efficient, supports batches of updates, runs in polylogarithmic depth, and uses only linear total space. The existing algorithms for the problem either use super-linear space, do not come with strong theoretical bounds, or are not parallel. On the empirical side, we provide the first implementation of the cluster forest algorithm , the first linear-space and polylogarithmic update time algorithm for dynamic connectivity. Experimentally, we find that our algorithm uses up to 19.7× less space and is up to 6.2× faster than the level-set algorithm of Holm, de Lichten-berg, and Thorup, arguably the most widely-implemented dynamic connectivity algorithm with strong theoretical guarantees.

We present the first non-trivial fully dynamic algorithm maintaining exact single-source distances in unweighted graphs. This resolves an open problem stated by Sankowski [COCOON 2005] and van den Brand and Nanongkai [FOCS 2019]. Previous fully dynamic single-source distances data structures were all approximate, but so far, non-trivial dynamic algorithms for the exact setting could only be ruled out for polynomially weighted graphs (Abboud and Vassilevska Williams, [FOCS 2014]). The exact unweighted case remained the main case for which neither a subquadratic dynamic algorithm nor a quadratic lower bound was known.Our dynamic algorithm works on directed graphs and is deterministic, and can report a single-source shortest paths tree in subquadratic time as well. Thus we also obtain the first deterministic fully dynamic data structure for reachability (transitive closure) with subquadratic update and query time. This answers an open problem of van den Brand, Nanongkai, and Saranurak [FOCS 2019]. Finally, using the same framework we obtain the first fully dynamic data structure maintaining all-pairs $(1+\epsilon)$-approximate distances within non-trivial sub-$n^{\omega}$ worst-case update time while supporting optimal-time approximate shortest path reporting at the same time. This data structure is also deterministic and therefore implies the first known non-trivial deterministic worst-case bound for recomputing the transitive closure of a digraph.

Algebraic techniques have had an important impact on graph algorithms so far. Porting them, e.g., the matrix inverse, into the dynamic regime improved best-known bounds for various dynamic graph problems. In this paper, we develop new algorithms for another cornerstone algebraic primitive, the Frobenius normal form (FNF). We apply our developments to dynamic and fault-tolerant exact distance oracle problems on directed graphs.For generic matrices A over a finite field accompanied by an FNF, we show (1) an efficient data structure for querying submatrices of the first $k \geq 1$ powers of A, and (2) a near-optimal algorithm updating the FNF explicitly under rank-1 updates.By representing an unweighted digraph using a generic matrix over a sufficiently large field (obtained by random sampling) and leveraging the developed FNF toolbox, we obtain:•a conditionally optimal distance sensitivity oracle (DSO) in the case of single-edge or single-vertex failures, providing a partial answer to the open question of Gu and Ren [ICALP 2021],•a multiple-failures DSO improving upon the state of the art (vd. Brand and Saranurak [FOCS 2019]) wrt. both preprocessing and query time,•improved dynamic distance oracles in the case of single-edge updates,•a dynamic distance oracle supporting vertex updates, i.e., changing all edges incident to a single vertex, in $\widetilde{O}\left(n^{2}\right)$ worst-case time and distance queries in $\widetilde{O}(n)$ time.

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

We study the exact fully dynamic shortest paths problem. For real-weighted directed graphs, we show a deterministic fully dynamic data structure with Õ(mn^{4/5}) worst-case update time processing arbitrary s,t-distance queries in Õ(n^{4/5}) time. This constitutes the first non-trivial update/query tradeoff for this problem in the regime of sparse weighted directed graphs. Moreover, we give a Monte Carlo randomized fully dynamic reachability data structure processing single-edge updates in Õ(n√m) worst-case time and queries in O(√m) time. For sparse digraphs, such a tradeoff has only been previously described with amortized update time [Roditty and Zwick, SIAM J. Comp. 2008].

We revisit the problem of finding optimal strategies for deterministic Markov Decision Processes (DMDPs), and a closely related problem of testing feasibility of systems of m linear inequalities on n real variables with at most two variables per inequality (2VPI). We give a randomized trade-off algorithm solving both problems and running in Õ(nmh + (n/h)3) time using Õ(n2/h + m) space for any parameter h ∊ [1,n]. In particular, using subquadratic space we get Õ(nm + n3/2m3/4) running time, which improves by a polynomial factor upon all the known upper bounds for non-dense instances with m = O(n2–∊). Moreover, using linear space we match the randomized Õ(nm + n3) time bound of Cohen and Megiddo [SICOMP'94] that required space. Additionally, we show a new algorithm for the Discounted All-Pairs Shortest Paths problem, introduced by Madani et al. [TALG'10], that extends the DMDPs with optional end vertices. For the case of uniform discount factors, we give a deterministic algorithm running in Õ(n3/2m3/4) time, which improves significantly upon the randomized bound of Madani et al.

We study reachability and shortest paths problems in dynamic directed graphs. Whereas algebraic dynamic data structures supporting edge updates and reachability/distance queries have been known for quite a long time, they do not, in general, allow reporting the underlying paths within the same time bounds, especially against an adaptive adversary.

The Shapley value – a fundamental game-theoretic solution concept – has recently become one of the main tools used to explain predictions of tree ensemble models. Another well-known game-theoretic solution concept is the Banzhaf value. Although the Banzhaf value is closely related to the Shapley value, its properties w.r.t. feature attribution have not been understood equally well. This paper shows that, for tree ensemble models, the Banzhaf value offers some crucial advantages over the Shapley value while providing similar feature attributions. In particular, we first give an optimal O(TL + n) time algorithm for computing the Banzhaf value-based attribution of a tree ensemble model’s output. Here, T is the number of trees, L is the maximum number of leaves in a tree, and n is the number of features. In comparison, the state-of-the-art Shapley value-based algorithm runs in O(TLD^2 + n) time, where D denotes the maximum depth of a tree in the ensemble. Next, we experimentally compare the Banzhaf and Shapley values for tree ensemble models. Both methods deliver essentially the same average importance scores for the studied datasets using two different tree ensemble models (the sklearn implementation of Decision Trees or xgboost implementation of Gradient Boosting Decision Trees). However, our results indicate that, on top of being computable faster, the Banzhaf is more numerically robust than the Shapley value.

We consider the problem of computing shortest paths in weighted unit-disk graphs in constant dimension d. Although the single-source and all-pairs variants of this problem are well-studied in the plane case, no non-trivial exact distance oracles for unit-disk graphs have been known to date, even for d = 2. The classical result of Sedgewick and Vitter [Algorithmica '86] shows that for weighted unit-disk graphs in the plane the A^* search has average-case performance superior to that of a standard shortest path algorithm, e.g., Dijkstra’s algorithm. Specifically, if the n corresponding points of a weighted unit-disk graph G are picked from a unit square uniformly at random, and the connectivity radius is r ∈ (0,1), A^* finds a shortest path in G in O(n) expected time when r = Ω(√{log n/n}), even though G has Θ((nr)²) edges in expectation. In other words, the work done by the algorithm is in expectation proportional to the number of vertices and not the number of edges. In this paper, we break this natural barrier and show even stronger sublinear time results. We propose a new heuristic approach to computing point-to-point exact shortest paths in unit-disk graphs. We analyze the average-case behavior of our heuristic using the same random graph model as used by Sedgewick and Vitter and prove it superior to A^*. Specifically, we show that, if we are able to report the set of all k points of G from an arbitrary rectangular region of the plane in O(k + t(n)) time, then a shortest path between arbitrary two points of such a random graph on the plane can be found in O(1/r² + t(n)) expected time. In particular, the state-of-the-art range reporting data structures imply a sublinear expected bound for all r = Ω(√{log n/n}) and O(√n) expected bound for r = Ω(n^{-1/4}) after only near-linear preprocessing of the point set. Our approach naturally generalizes to higher dimensions d ≥ 3 and yields sublinear expected bounds for all d = O(1) and sufficiently large r.

We consider the directed minimum weight cycle problem in the fully dynamic setting. To the best of our knowledge, so far no fully dynamic algorithms have been designed specifically for the minimum weight cycle problem in general digraphs. One can achieve $\tilde{O}(n^2)$ amortized update time by simply invoking the fully dynamic APSP algorithm of Demetrescu and Italiano [J. ACM'04]. This bound, however, yields no improvement over the trivial recompute-from-scratch algorithm for sparse graphs. Our first contribution is a very simple deterministic $(1+ε)$-approximate algorithm supporting vertex updates (i.e., changing all edges incident to a specified vertex) in conditionally near-optimal $\tilde{O}(m\log{(W)}/ε)$ amortized time for digraphs with real edge weights in $[1,W]$. Using known techniques, the algorithm can be implemented on planar graphs and also gives some new sublinear fully dynamic algorithms maintaining approximate cuts and flows in planar digraphs. Additionally, we show a Monte Carlo randomized exact fully dynamic minimum weight cycle algorithm with $\tilde{O}(mn^{2/3})$ worst-case update that works for real edge weights. To this end, we generalize the exact fully dynamic APSP data structure of Abraham et al. [SODA'17] to solve the ``multiple-pairs shortest paths problem'', where one is interested in computing distances for some $k$ (instead of all $n^2$) fixed source-target pairs after each update. We show that in such a scenario, $\tilde{O}((m+k)n^{2/3})$ worst-case update time is possible.

This paper bridges discrete and continuous optimization approaches for decomposable submodular function minimization, in both the standard and parametric settings. We provide improved running times for this problem by reducing it to a number of calls to a maximum flow oracle. When each function in the decomposition acts on O(1) elements of the ground set V and is polynomially bounded, our running time is up to polylogarithmic factors equal to that of solving maximum flow in a sparse graph with O(|V|) vertices and polynomial integral capacities. We achieve this by providing a simple iterative method which can optimize to high precision any convex function defined on the submodular base polytope, provided we can efficiently minimize it on the base polytope corresponding to the cut function of a certain graph that we construct. We solve this minimization problem by lifting the solutions of a parametric cut problem, which we obtain via a new efficient combinatorial reduction to maximum flow. This reduction is of independent interest and implies some previously unknown bounds for the parametric minimum s,t-cut problem in multiple settings.

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

In this paper we show a deterministic parallel all-pairs shortest paths algorithm for real-weighted directed graphs. The algorithm has Õ(nm + (n/d)3) work and Õ(d) depth for any depth parameter d ∊ [1, n]. To the best of our knowledge, such a trade-off has only been previously described for the real-weighted single-source shortest paths problem using randomization [Bringmann et al., ICALP'17]. Moreover, our result improves upon the parallelism of the state-of-the-art randomized parallel algorithm for computing transitive closure, which has Õ(nm + n3/d2) work and Õ(d) depth [Ullman and Yannakakis, SIAM J. Comput. '91]. Our APSP algorithm turns out to be a powerful tool for designing efficient planar graph algorithms in both parallel and sequential regimes. By suitably adjusting the depth parameter d and applying known techniques, we obtain: nearly work-efficient Õ(n1/6)-depth parallel algorithms for the real-weighted single-source shortest paths problem and finding a bipartite perfect matching in a planar graph, an Õ(n9/8)-time sequential strongly polynomial algorithm for computing a minimum mean cycle or a minimum cost-to-time-ratio cycle of a planar graph, a slightly faster algorithm for computing so-called external dense distance graphs of all pieces of a recursive decomposition of a planar graph. One notable ingredient of our parallel APSP algorithm is a simple deterministic Õ(nm)-work Õ(d)-depth procedure for computing Õ(n/d)-size hitting sets of shortest d-hop paths between all pairs of vertices of a real-weighted digraph. Such hitting sets have also been called d-hub sets. Hub sets have previously proved especially useful in designing parallel or dynamic shortest paths algorithms and are typically obtained via random sampling. Our procedure implies, for example, an Õ(nm)-time deterministic algorithm for finding a shortest negative cycle of a real-weighted digraph. Such a near-optimal bound for this problem has been so far only achieved using a randomized algorithm [Orlin et al., Discret. Appl. Math. '18].

Efficient algorithms for computing and processing additively weighted Voronoi diagrams on planar graphs have been instrumental in obtaining several recent breakthrough results, most notably the almost-optimal exact distance oracle for planar graphs [Charalampopoulos et al., STOC'19], and subquadratic algorithms for planar diameter [Cabello, SODA'17, Gawrychowski et al., SODA'18]. In this paper, we show how Voronoi diagrams can be useful in obtaining dynamic planar graph algorithms and apply them to classical problems such as dynamic single-source shortest paths and dynamic strongly connected components. First, we give a fully dynamic single-source shortest paths data structure for planar weighted digraphs with Õ(n^{4/5}) worst-case update time and O(log² n) query time. Here, a single update can either change the graph by inserting or deleting an edge, or reset the source s of interest. All known non-trivial planarity-exploiting exact dynamic single-source shortest paths algorithms to date had polynomial query time. Further, note that a data structure with strongly sublinear update time capable of answering distance queries between all pairs of vertices in polylogarithmic time would refute the APSP conjecture [Abboud and Dahlgaard, FOCS'16]. Somewhat surprisingly, the Voronoi diagram based approach we take for single-source shortest paths can also be used in the fully dynamic strongly connected components problem. In particular, we obtain a data structure maintaining a planar digraph under edge insertions and deletions, capable of returning the identifier of the strongly connected component of any query vertex. The worst-case update and query time bounds are the same as for our single-source distance oracle. To the best of our knowledge, this is the first fully dynamic strong-connectivity algorithm achieving both sublinear update time and polylogarithmic query time for an important class of digraphs.

We give new partially-dynamic algorithms for the all-pairs shortest paths problem in weighted directed graphs. Most importantly, we give a new deterministic incremental algorithm for the problem that handles updates in $\widetilde{O}(mn^{4/3}\log{W}/ε)$ total time (where the edge weights are from $[1,W]$) and explicitly maintains a $(1+ε)$-approximate distance matrix. For a fixed $ε>0$, this is the first deterministic partially dynamic algorithm for all-pairs shortest paths in directed graphs, whose update time is $o(n^2)$ regardless of the number of edges. Furthermore, we also show how to improve the state-of-the-art partially dynamic randomized algorithms for all-pairs shortest paths [Baswana et al. STOC'02, Bernstein STOC'13] from Monte Carlo randomized to Las Vegas randomized without increasing the running time bounds (with respect to the $\widetilde{O}(\cdot)$ notation). Our results are obtained by giving new algorithms for the problem of dynamically maintaining hubs, that is a set of $\widetilde{O}(n/d)$ vertices which hit a shortest path between each pair of vertices, provided it has hop-length $Ω(d)$. We give new subquadratic deterministic and Las Vegas algorithms for maintenance of hubs under either edge insertions or deletions.

In this paper we give an $\widetilde{O}((nm)^{2/3}\log C)$ time algorithm for computing min-cost flow (or min-cost circulation) in unit capacity planar multigraphs where edge costs are integers bounded by $C$. For planar multigraphs, this improves upon the best known algorithms for general graphs: the $\widetilde{O}(m^{10/7}\log C)$ time algorithm of Cohen et al. [SODA 2017], the $O(m^{3/2}\log(nC))$ time algorithm of Gabow and Tarjan [SIAM J. Comput. 1989] and the $\widetilde{O}(\sqrt{n}m \log C)$ time algorithm of Lee and Sidford [FOCS 2014]. In particular, our result constitutes the first known fully combinatorial algorithm that breaks the $\widetilde{O}(m^{3/2})$ time barrier for min-cost flow problem in planar graphs. To obtain our result we first give a very simple successive shortest paths based scaling algorithm for unit-capacity min-cost flow problem that does not explicitly operate on dual variables. This algorithm also runs in $\widetilde{O}(m^{3/2}\log{C})$ time for general graphs, and, to the best of our knowledge, it has not been described before. We subsequently show how to implement this algorithm faster on planar graphs using well-established tools: $r$-divisions and efficient algorithms for computing (shortest) paths in so-called dense distance graphs.

We present a decremental data structure for maintaining the SPQR-tree of a planar graph subject to edge contractions and deletions. The update time, amortized over Omega(n) operations, is O(log^2 n). Via SPQR-trees, we give a decremental data structure for maintaining 3-vertex connectivity in planar graphs. It answers queries in O(1) time and processes edge deletions and contractions in O(log^2 n) amortized time. The previous best supported deletions and insertions in O(sqrt{n}) time.

We study the problem of computing shortest paths in so-called dense distance graphs. Every planar graph $G$ on $n$ vertices can be partitioned into a set of $O(n/r)$ edge-disjoint regions (called an $r$-division) with $O(r)$ vertices each, such that each region has $O(\sqrt{r})$ vertices (called boundary vertices) in common with other regions. A dense distance graph of a region is a complete graph containing all-pairs distances between its boundary nodes. A dense distance graph of an $r$-division is the union of the $O(n/r)$ dense distance graphs of the individual pieces. Since the introduction of dense distance graphs by Fakcharoenphol and Rao, computing single-source shortest paths in dense distance graphs has found numerous applications in fundamental planar graph algorithms. Fakcharoenphol and Rao proposed an algorithm (later called FR-Dijkstra) for computing single-source shortest paths in a dense distance graph in $O\left(\frac{n}{\sqrt{r}}\log{n}\log{r}\right)$ time. We show an $O\left(\frac{n}{\sqrt{r}}\left(\frac{\log^2{r}}{\log^2\log{r}}+\log{n}\log^ε{r}\right)\right)$ time algorithm for this problem, which is the first improvement to date over FR-Dijkstra for the important case when $r$ is polynomial in $n$. In this case, our algorithm is faster by a factor of $O(\log^2{\log{n}})$ and implies improved upper bounds for such planar graph problems as multiple-source multiple-sink maximum flow, single-source all-sinks maximum flow, and (dynamic) exact distance oracles.

In this paper, we study the fundamental problem of maintaining a dynamic collection of strings under the following operations: •• make_string – add a string of constant length,•• concat – concatenate two strings,•• split – split a string into two at a given position,•• compare – find the lexicographical order (less, equal, greater) between two strings,•• LCP – calculate the longest common prefix of two strings. We develop a generic framework for dynamizing the recompression method recently introduced by Jeż [J. ACM, 2016]. It allows us to present an efficient data structure for the above problem, where an update requires only O(log n) worst-case time with high probability, with n being the total length of all strings in the collection, and a query takes constant worst-case time. On the lower bound side, we prove that even if the only possible query is checking equality of two strings, either updates or queries must take amortized Ω(log n) time; hence our implementation is optimal.

In this paper we show that the tools used to obtain the best state-of-the-art decremental algorithms for reachability and approximate shortest paths in directed graphs can be successfully combined with the existence of small separators in certain graph classes. In particular, for graph classes admitting balanced separators of size , such as planar, bounded-genus and minor-free graphs, we show that for both transitive closure and (1 + ε)-approximate all pairs shortest paths (where ∊ is constant), there exist decremental algorithms with Õ(n3/2) total update time and worst-case query time. Additionally, for the case of planar graphs, we show that for any t ∊ [1, n], there exists a decremental transitive closure algorithm with Õ(n2/t) total update time and worst-case query time. In particular, for t = n2/3, if all the edges are eventually deleted, we obtain Õ(n1/3) amortized update and query times. Most of the algorithms we obtain are correct with high probability against an oblivious adversary.

We present a data structure that can maintain a simple planar graph under edge contractions in linear total time. The data structure supports adjacency queries and provides access to neighbor lists in $O(1)$ time. Moreover, it can report all the arising self-loops and parallel edges. By applying the data structure, we can achieve optimal running times for decremental bridge detection, 2-edge connectivity, maximal 3-edge connected components, and the problem of finding a unique perfect matching for a static planar graph. Furthermore, we improve the running times of algorithms for several planar graph problems, including decremental 2-vertex and 3-edge connectivity, and we show that using our data structure in a black-box manner, one obtains conceptually simple optimal algorithms for computing MST and 5-coloring in planar graphs.

In this paper we show a new algorithm for the decremental single-source reachability problem in directed planar graphs. It processes any sequence of edge deletions in O(nlog2nloglogn) total time and explicitly maintains the set of vertices reachable from a fixed source vertex. Hence, if all edges are eventually deleted, the amortized time of processing each edge deletion is only O(log2 n loglogn), which improves upon a previously known O(√n) solution. We also show an algorithm for decremental maintenance of strongly connected components in directed planar graphs with the same total update time. These results constitute the first almost optimal (up to polylogarithmic factors) algorithms for both problems.