We give an algorithm that computes exact maximum flows and minimum-cost on directed graphs with m edges polynomially bounded integral demands, costs, capacities in $m^{1+o(1)}$ time. Our builds the flow through a sequence of approximate undirected minimum-ratio cycles, each which is computed processed amortized $m^{o(1)}$ time using new dynamic graph data structure. framework extends to algorithms running for computing minimize general edge-separable convex functions high accuracy. This...

We give the first almost-linear time algorithms for several problems in incremental graphs including cycle detection, strongly connected component maintenance, s-t shortest path, maximum flow, and minimum-cost flow. To solve these problems, we a deterministic data structure that returns mo(1)-approximate minimum-ratio fully dynamic amortized mo(1) per update. Combining this with interior point method framework of Brand-Liu-Sidford (STOC 2023) gives algorithm deciding update an graph after...

Designing dynamic graph algorithms against an adaptive adversary is a major goal in the field of algorithms. While few such are known for spanning trees, matchings, and single-source shortest paths, very little was important primitive like sparsifiers. The challenge how to approximately preserve so much information about (e.g., all-pairs distances all cuts) without revealing algorithms' underlying randomness adversary. In this paper we present first non-trivial efficient maintaining spanners...

In the decremental single-source shortest paths problem, goal is to maintain distances from a fixed source <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$s$</tex> every vertex xmlns:xlink="http://www.w3.org/1999/xlink">$v$</tex> in an m-edge graph undergoing edge deletions. this paper, we conclude long line of research on problem by showing near-optimal deterministic data structure that maintains (1 + E) -approximate distance estimates and...

Computing the Strongly-Connected Components (SCCs) in a graph G=(V,E) is known to take only O(m+n) time using an algorithm by Tarjan from 1972[SICOMP 72] where m = |E|, n=|V|. For fully-dynamic graphs, conditional lower bounds provide evidence that update cannot be improved polynomial factors over recomputing SCCs scratch after every update. Nevertheless, substantial progress has been made find algorithms with fast for decremental i.e. graphs undergo edge deletions.

Let G=(V, E, w) be a weighted, directed graph subject to sequence of adversarial edge deletions. In the decremental single-source reachability problem (SSR), we are given fixed source s and goal is maintain data structure that can answer path-queries s\rightarrowtail v for any ∈ V. more general shortest paths (SSSP) return an approximate path v, in SCC strongly connected components G queries within each component. All these problems have been very actively studied over past two decades, but...

We present an algorithm that computes exact maximum flows and minimum-cost on directed graphs with m edges polynomially bounded integral demands, costs, capacities in 1 + o (1) time. Our builds the flow through a sequence of approximate undirected minimum-ratio cycles, each which is computed processed amortized time using new dynamic graph data structure. framework extends to algorithms running for computing minimize general edge-separable convex functions high accuracy. This gives...

In the dynamic Single-Source Shortest Paths (SSSP) problem, we are given a graph G=(V,E) subject to edge insertions and deletions source vertex s∈ V, goal is maintain distance d(s,t) for all t∈ V.

We give a deterministic $m^{1+o(1)}$ time algorithm that computes exact maximum flows and minimum-cost on directed graphs with m edges polynomially bounded integral demands, costs, capacities. As consequence, we obtain the first running improvement for algorithms compute maximum-flow in polynomial capacities since work of Goldberg-Rao [J.ACM '98].Our builds framework Chen-Kyng-Liu-Peng-Gutenberg-Sachdeva [FOCS '22] an optimal flow by computing sequence $m^{1+o(1)}$-approximate undirected...

We present an algorithm that computes exact maximum flows and minimum-cost on directed graphs with m edges polynomially bounded integral demands, costs, capacities in 1+ o (1) time. Our builds the flow through a sequence of approximate undirected minimum-ratio cycles, each which is computed processed amortized time using new dynamic graph data structure. framework extends to algorithms running for computing minimize general edge-separable convex functions high accuracy. This gives...

In the decremental Single-Source Shortest Path problem (SSSP), we are given a weighted directed graph G = (V, E, w) undergoing edge deletions and source vertex r ∈ V; let n=|V|, m=|E| W be aspect ratio of graph. The goal is to obtain data structure that maintains shortest paths from all vertices in V can answer distance queries O(1) time, as well return corresponding path P O(|P|) time. This was first considered by Even Shiloach [JACM'81], who provided an algorithm with total update time...

Given an unweighted digraph G = (V,E), undergoing a sequence of edge deletions, with m |E|, n |V|, we consider the problem maintaining all-pairs shortest paths (APSP). Whilst this has been studied in long line research [ACM'81, FOCS'99, FOCS'01, STOC'02, STOC'03, SWAT'04, STOC'13] and (1+e)-approximate, weighted APSP was solved to near-optimal update time O(mn) by Bernstein [STOC'13], mainly context oblivious adversary which fixes before algorithm is started. In paper, make significant...

Given a directed graph $G = (V,E)$, undergoing an online sequence of edge deletions with $m$ edges in the initial version $G$ and $n |V|$, we consider problem maintaining all-pairs shortest paths (APSP) $G$. Whilst this has been studied long line research [ACM'81, FOCS'99, FOCS'01, STOC'02, STOC'03, SWAT'04, STOC'13] $(1+ε)$-approximate, weighted APSP was solved to near-optimal update time $\tilde{O}(mn)$ by Bernstein [STOC'13], mainly context oblivious adversaries, which assumes that...

We give an algorithm that computes exact maximum flows and minimum-cost on directed graphs with $m$ edges polynomially bounded integral demands, costs, capacities in $m^{1+o(1)}$ time. Our builds the flow through a sequence of approximate undirected minimum-ratio cycles, each which is computed processed amortized $m^{o(1)}$ time using new dynamic graph data structure. framework extends to algorithms running for computing minimize general edge-separable convex functions high accuracy. This...

In this article, we present the first deterministic directed Laplacian L systems solver that runs in time almost-linear number of non-zero entries L. Previous reductions imply algorithms for computing various fundamental quantities on graphs including stationary distributions, personalized PageRank, hitting times and escape probabilities.We obtain these results by introducing partial symmetrization, a new technique makes an Eulerian graph "less directed" useful sense, which may be...