44 research outputs found
Near-Optimal Algorithm for Directed Expander Decompositions
Full text linkIn this work, we present the first algorithm to compute expander decompositions in an m-edge directed graph with near-optimal time Õ(m). Further, our algorithm can maintain such a decomposition in a dynamic graph and again obtains near-optimal update times. Our result improves over previous algorithms [Bernstein et al., 2020; Hua et al., 2023] that only obtained algorithms optimal up to subpolynomial factors.
In order to obtain our new algorithm, we present a new push-pull-relabel flow framework that generalizes the classic push-relabel flow algorithm [Goldberg and Tarjan, 1988] which was later dynamized for computing expander decompositions in undirected graphs [Henzinger et al., 2020; Saranurak and Wang, 2019]. We then show that the flow problems formulated in recent work [Hua et al., 2023] to decompose directed graphs can be solved much more efficiently in the push-pull-relabel flow framework.
Recently, our algorithm has already been employed to obtain the currently fastest algorithm to compute min-cost flows [Van Den Brand et al., 2024]. We further believe that our algorithm can be used to speed-up and simplify recent breakthroughs in combinatorial graph algorithms towards fast maximum flow algorithms [Chuzhoy and Khanna, 2024; Chuzhoy and Khanna, 2024; Bernstein et al., 2024]
Practical Expander Decomposition
Full text linkThe expander decomposition of a graph decomposes the set of vertices into clusters such that the induced subgraph of each cluster is a subgraph with high conductance, and there is only a small number of inter-cluster edges. Expander decompositions are at the forefront of recent theoretical developments in the area of efficient graph algorithms and act as a central component in several state-of-the-art graph algorithms for fundamental problems like maximum flow, min-cost flow, Gomory-Hu trees, global min-cut, and more. Despite this crucial role and the existence of theoretically efficient expander decomposition algorithms, little is known on their behavior in practice.
In this paper we explore the engineering design space in implementations for computing expander decompositions. We base our implementation on the near-linear time algorithm of Saranurak and Wang [SODA'19], and enhance it with practical optimizations that accelerate its running time in practice and at the same time preserve the theoretical runtime and approximation guarantees.
We evaluate our algorithm on real-world graphs with up to tens of millions of edges. We demonstrate significant speedups of up to two orders of magnitude over the only prior implementation. To the best of our knowledge, our implementation is the first to compute expander decompositions at this scale within reasonable time
A Simple and Near-Optimal Algorithm for Directed Expander Decompositions
Full text linkIn this work, we present the first algorithm to compute expander
decompositions in an -edge directed graph with near-optimal time
. Further, our algorithm can maintain such a decomposition in a
dynamic graph and again obtains near-optimal update times. Our result improves
over previous algorithms of Bernstein-Probst Gutenberg-Saranurak (FOCS 2020),
Hua-Kyng-Probst Gutenberg-Wu (SODA 2023) that only obtained algorithms optimal
up to subpolynomial factors. At the same time, our algorithm is much simpler
and more accessible than previous work. In order to obtain our new algorithm,
we present a new push-pull-relabel flow framework that generalizes the classic
push-relabel flow algorithm of Goldberg-Tarjan (JACM 1988), which was later
dynamized for computing expander decompositions in undirected graphs by
Henzinger-Rao-Wang (SIAM J. Comput. 2020), Saranurak-Wang (SODA 2019). We then
show that the flow problems formulated in recent work of Hua-Kyng-Probst
Gutenberg-Wu (SODA 2023) to decompose directed graphs can be solved much more
efficiently in the push-pull-relabel flow framework
Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets
Full text linkWe study linear equations in combinatorial Laplacians of k-dimensional simplicial complexes (k-complexes), a natural generalization of graph Laplacians. Combinatorial Laplacians play a crucial role in homology and are a central tool in topology. Beyond this, they have various applications in data analysis and physical modeling problems. It is known that nearly-linear time solvers exist for graph Laplacians. However, nearly-linear time solvers for combinatorial Laplacians are only known for restricted classes of complexes.
This paper shows that linear equations in combinatorial Laplacians of 2-complexes are as hard to solve as general linear equations. More precisely, for any constant c ≥ 1, if we can solve linear equations in combinatorial Laplacians of 2-complexes up to high accuracy in time Õ((# of nonzero coefficients)^c), then we can solve general linear equations with polynomially bounded integer coefficients and condition numbers up to high accuracy in time Õ((# of nonzero coefficients)^c). We prove this by a nearly-linear time reduction from general linear equations to combinatorial Laplacians of 2-complexes. Our reduction preserves the sparsity of the problem instances up to poly-logarithmic factors
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary
Full text linkDesigning efficient dynamic graph algorithms against an adaptive adversary is a major goal in the field of dynamic graph algorithms and has witnessed many exciting recent developments in, e.g., dynamic matching (Wajc STOC'20) and decremental shortest paths (Chuzhoy and Khanna STOC'19). Compared to other graph primitives (e.g. spanning trees and matchings), designing such algorithms for graph spanners and (more broadly) graph sparsifiers poses a unique challenge since there is no fast deterministic algorithm known for static computation and the lack of a way to adjust the output slowly (known as "small recourse/replacements").
This paper presents the first non-trivial efficient adaptive algorithms for maintaining many sparsifiers against an adaptive adversary. Specifically, we present algorithms that maintain
1) a polylog(n)-spanner of size Õ(n) in polylog(n) amortized update time,
2) an O(k)-approximate cut sparsifier of size Õ(n) in Õ(n^{1/k}) amortized update time, and
3) a polylog(n)-approximate spectral sparsifier in polylog(n) amortized update time. Our bounds are the first non-trivial ones even when only the recourse is concerned. Our results hold even against a stronger adversary, who can access the random bits previously used by the algorithms and the amortized update time of all algorithms can be made worst-case by paying sub-polynomial factors. Our spanner result resolves an open question by Ahmed et al. (2019) and our results and techniques imply additional improvements over existing results, including (i) answering open questions about decremental single-source shortest paths by Chuzhoy and Khanna (STOC'19) and Gutenberg and Wulff-Nilsen (SODA'20), implying a nearly-quadratic time algorithm for approximating minimum-cost unit-capacity flow and (ii) de-amortizing a result of Abraham et al. (FOCS'16) for dynamic spectral sparsifiers.
Our results are based on two novel techniques. The first technique is a generic black-box reduction that allows us to assume that the graph is initially an expander with almost uniform-degree and, more importantly, stays as an almost uniform-degree expander while undergoing only edge deletions. The second technique is called proactive resampling: here we constantly re-sample parts of the input graph so that, independent of an adversary’s computational power, a desired structure of the underlying graph can be always maintained. Despite its simplicity, the analysis of this sampling scheme is far from trivial, because the adversary can potentially create dependencies between the random choices used by the algorithm. We believe these two techniques could be useful for developing other adaptive algorithms
Near-optimal decremental sssp in dense weighted digraphs
No full textIn the decremental Single-Source Shortest Path problem (SSSP), we are given a weighted directed graph G= (V, E, w) undergoing edge deletions and a source vertex r in V; let n= vert V vert, m= vert E vert and W be the aspect ratio of the graph. The goal is to obtain a data structure that maintains shortest paths from r to all vertices in V and can answer distance queries in O(1) time, as well as return the corresponding path P in O(vert P vert) time. This problem was first considered by Even and Shiloach [JACM'81], who provided an algorithm with total update time O(mn) for unweighted undirected graphs; this was later extended to directed weighted graphs [FOCS'95, STOC'99]. There are conditional lower bounds showing that O(mn) is in fact near-optimal [ESA'04, FOCS'14, STOC'15, STOC'20]. In a breakthrough result, Forster et al. showed that total update time min {m{7/6}n{2/3+o(1)}, m{3/4}n{5/4+o(1)} } text{polylog}(W)= mn{0.9+o(1)} text{polylog} (W), is possible if the algorithm is allowed to return (1 + epsilon)-approximate paths, instead of exact ones [STOC'14, ICALP'15]. No further progress was made until Probst Gutenberg and Wulff-Nilsen [SODA'20] provided a new approach for the problem, which yields total time tilde{O}(min {m{2/3}n{4/3} log W, (mn){7/8} log W })= tilde{O}(min {n{8/3} log W, mn{3/4} log W }). Our result builds on this recent approach, but overcomes its limitations by introducing a significantly more powerful abstraction, as well as a different core subroutine. Our new framework yields a decremental (1+ epsilon)-approximate SSSP data structure with total update time tilde{O}(n{2} log{4}W epsilon). Our algorithm is thus near-optimal for dense graphs with polynomial edge-weights. Our framework can also be applied to sparse graphs to obtain total update time tilde{O}(mn{2/3} log{3}W epsilon). Combined, these data structures dominate all previous results. Like all previous o(mn) algorithms that can return a path (not just a distance estimate), our result is randomized and assumes an oblivious adversary. Our framework effectively allows us to reduce SSSP in general graphs to the same problem in directed acyclic graphs (DAGs). We believe that our framework has significant potential to influence future work on directed SSSP, both in the dynamic model and in others.</p
Near-Optimal Algorithms for Reachability, Strongly-Connected Components and Shortest Paths in Partially Dynamic Digraphs
No full textIn this thesis, we present new techniques to deal with fundamental algorithmic graph problems where graphs are directed and partially dynamic, i.e. undergo either a sequence of edge insertions or deletions:• Single-Source Reachability (SSR): given a distinct source vertex r in a graph, the objective is to maintain the set of vertices that r can reach throughout the entire update sequence.• Strongly-Connected Components (SCC): the goal is to maintain a partition of the vertex set X1,X2, . . . ,Xk, such that every two vertices in the same partition set Xi are on a common cycle, while no two vertices across different partition sets do.• Single-Source Shortest Paths (SSSP): given a dedicated source vertex s, the objective is to maintain the distance from s to every other vertex in the graph.These problems have recently received an extraordinary amount of attention due to their role as subproblems in various more complex and notoriously hard graph problems, especially to compute flows, bipartite matchings and cuts.Our techniques lead to the first near-optimal data structures for these problems in various different settings. Letting n denote the number of vertices in the graph and by m the maximum number of edges in any version of the graph, we obtain• the first randomized data structure to maintain SSR and SCCs in near-optimaltotal update time Õ(m) in a graph undergoing edge deletions.• the first randomized data structure to maintain SSSP in partially dynamic graphs in total update time Õ(n2) which is near-optimal in dense graphs.• the first deterministic data structures for SSR and SCC for graphs undergoing edge deletions, and for SSSP in partially dynamic graphs that improve upon the O(mn) total update time by Even and Shiloach from 1981 that is often considered to be a fundamental barrier
Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, - Shortest Path, and Minimum-Cost Flow
Full text linkWe give the first almost-linear time algorithms for several problems in
incremental graphs including cycle detection, strongly connected component
maintenance, - shortest path, maximum flow, and minimum-cost flow. To
solve these problems, we give a deterministic data structure that returns a
-approximate minimum-ratio cycle in fully dynamic graphs in amortized
time per update. Combining this with the interior point method
framework of Brand-Liu-Sidford (STOC 2023) gives the first almost-linear time
algorithm for deciding the first update in an incremental graph after which the
cost of the minimum-cost flow attains value at most some given threshold .
By rather direct reductions to minimum-cost flow, we are then able to solve the
problems in incremental graphs mentioned above.
At a high level, our algorithm dynamizes the oblivious routing of
Rozho\v{n}-Grunau-Haeupler-Zuzic-Li (STOC 2022), and develops a method to
extract an approximate minimum ratio cycle from the structure of the oblivious
routing. To maintain the oblivious routing, we use tools from concurrent work
of Kyng-Meierhans-Probst Gutenberg which designed vertex sparsifiers for
shortest paths, in order to maintain a sparse neighborhood cover in fully
dynamic graphs.
To find a cycle, we first show that an approximate minimum ratio cycle can be
represented as a fundamental cycle on a small set of trees resulting from the
oblivious routing. Then, we find a cycle whose quality is comparable to the
best tree cycle. This final cycle query step involves vertex and edge
sparsification procedures reminiscent of previous works, but crucially requires
a more powerful dynamic spanner which can handle far more edge insertions. We
build such a spanner via a construction that hearkens back to the classic
greedy spanner algorithm
