Source author record

Maximilian Probst Gutenberg

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Machine Learning math.AT math.NA Numerical Analysis

Catalog footprint

Research overview

11works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

An Approximation Algorithm for Graph Label Selection

In the graph label selection problem, one is given an $n$ -vertex graph and a budget $k$ , and seeks to select $k$ vertices whose labels enable accurate prediction of the labels on the remaining vertices. This problem formalizes distilling a small representative set from the whole graph. We present the first $\tilde{O}(\log^{1.5} n)$ -approximation algorithm for graph label selection under the standard budget constraint. Prior work either relies on resource augmentation, allowing substantially more than $k$ labeled vertices, or consists primarily of heuristics without provable guarantees. Finally, we demonstrate that practical heuristic variants of our algorithm scale to significantly larger graphs than previous methods, while essentially retaining their quality.

preprint2022arXiv

Derandomizing Directed Random Walks in Almost-Linear Time

In this article, we present the first deterministic directed Laplacian L systems solver that runs in time almost-linear in the number of non-zero entries of L. Previous reductions imply the first deterministic almost-linear time algorithms for computing various fundamental quantities on directed graphs including stationary distributions, personalized PageRank, hitting times and escape probabilities. We obtain these results by introducing partial symmetrization, a new technique that makes the Laplacian of an Eulerian directed graph ``less directed'' in a useful sense, which may be of independent interest. The usefulness of this technique comes from two key observations: Firstly, the partially symmetrized Laplacian preconditions the original Eulerian Laplacian well in Richardson iteration, enabling us to construct a solver for the original matrix from a solver for the partially symmetrized one. Secondly, the undirected structure in the partially symmetrized Laplacian makes it possible to sparsify the matrix very crudely, i.e. with large spectral error, and still show that Richardson iterations convergence when using the sparsified matrix as a preconditioner. This allows us to develop deterministic sparsification tools for the partially symmetrized Laplacian. Together with previous reductions from directed Laplacians to Eulerian Laplacians, our technique results in the first deterministic almost-linear time algorithm for solving linear equations in directed Laplacians. To emphasize the generality of our new technique, we show that two prominent existing (randomized) frameworks for solving linear equations in Eulerian Laplacians can be derandomized in this way: the squaring-based framework of Cohen, Kelner, Peebles, Peng, Rao, Sidford and Vladu (STOC 2017) and the sparsified Cholesky-based framework of Peng and Song (STOC 2022).

preprint2022arXiv

Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets

We 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 \geq 1$ , if we can solve linear equations in combinatorial Laplacians of 2-complexes up to high accuracy in time $\tilde{O}((\# \text{ 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 $\tilde{O}((\# \text{ 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.

preprint2022arXiv

Maximum Flow and Minimum-Cost Flow in Almost-Linear Time

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

preprint2021arXiv

Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing

Let $G = (V,E,w)$ be a weighted, digraph subject to a sequence of adversarial edge deletions. In the decremental single-source reachability problem (SSR), we are given a fixed source $s$ and the goal is to maintain a data structure that can answer path-queries $s \rightarrowtail v$ for any $v \in V$ . In the more general single-source shortest paths (SSSP) problem the goal is to return an approximate shortest path to $v$ , and in the SCC problem the goal is to maintain strongly connected components of $G$ and to answer path queries within each component. All of these problems have been very actively studied over the past two decades, but all the fast algorithms are randomized and, more significantly, they can only answer path queries if they assume a weaker model: they assume an oblivious adversary which is not adaptive and must fix the update sequence in advance. This assumption significantly limits the use of these data structures, most notably preventing them from being used as subroutines in static algorithms. All the above problems are notoriously difficult in the adaptive setting. In fact, the state-of-the-art is still the Even and Shiloach tree, which dates back all the way to 1981 and achieves total update time $O(mn)$ . We present the first algorithms to break through this barrier: 1) deterministic decremental SSR/SCC with total update time $mn^{2/3 + o(1)}$ 2) deterministic decremental SSSP with total update time $n^{2+2/3+o(1)}$ . To achieve these results, we develop two general techniques of broader interest for working with dynamic graphs: 1) a generalization of expander-based tools to dynamic directed graphs, and 2) a technique that we call congestion balancing and which provides a new method for maintaining flow under adversarial deletions. Using the second technique, we provide the first near-optimal algorithm for decremental bipartite matching.

preprint2021arXiv

Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time

In the decremental single-source shortest paths problem, the goal is to maintain distances from a fixed source $s$ to every vertex $v$ in an $m$ -edge graph undergoing edge deletions. In this paper, we conclude a long line of research on this problem by showing a near-optimal deterministic data structure that maintains $(1+ε)$ -approximate distance estimates and runs in $m^{1+o(1)}$ total update time. Our result, in particular, removes the oblivious adversary assumption required by the previous breakthrough result by Henzinger et al. [FOCS'14], which leads to our second result: the first almost-linear time algorithm for $(1-ε)$ -approximate min-cost flow in undirected graphs where capacities and costs can be taken over edges and vertices. Previously, algorithms for max flow with vertex capacities, or min-cost flow with any capacities required super-linear time. Our result essentially completes the picture for approximate flow in undirected graphs. The key technique of the first result is a novel framework that allows us to treat low-diameter graphs like expanders. This allows us to harness expander properties while bypassing shortcomings of expander decomposition, which almost all previous expander-based algorithms needed to deal with. For the second result, we break the notorious flow-decomposition barrier from the multiplicative-weight-update framework using randomization.

preprint2020arXiv

Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary

Given a dynamic digraph $G = (V,E)$ undergoing edge deletions and given $s\in V$ and $ε>0$ , we consider the problem of maintaining $(1+ε)$ -approximate shortest path distances from $s$ to all vertices in $G$ over the sequence of deletions. Even and Shiloach (J.~ACM' $81$ ) give a deterministic data structure for the exact version of the problem with total update time $O(mn)$ . Henzinger et al. (STOC' $14$ , ICALP' $15$ ) give a Monte Carlo data structure for the approximate version with improved total update time $O(mn^{0.9 + o(1)}\log W)$ where $W$ is the ratio between the largest and smallest edge weight. A drawback of their data structure is that they only work against an oblivious adversary, meaning that the sequence of deletions needs to be fixed in advance. This limits its application as a black box inside algorithms. We present the following $(1+ε)$ -approximate data structures: (1) the first data structure is Las Vegas and works against an adaptive adversary; it has total expected update time $\tilde O(m^{2/3}n^{4/3})$ for unweighted graphs and $\tilde O(m^{3/4}n^{5/4}\log W)$ for weighted graphs, (2) the second data structure is Las Vegas and assumes an oblivious adversary; it has total expected update time $\tilde O(\sqrt m n^{3/2})$ for unweighted graphs and $\tilde O(m^{2/3}n^{4/3}\log W)$ for weighted graphs, (3) the third data structure is Monte Carlo and is correct w.h.p.~against an oblivious adversary; it has total expected update time $\tilde O((mn)^{7/8}\log W) = \tilde O(mn^{3/4}\log W)$ . Each of our data structures can be queried at any stage of $G$ in constant worst-case time; if the adversary is oblivious, a query can be extended to also report such a path in time proportional to its length. Our update times are faster than those of Henzinger et al.~for all graph densities.

preprint2020arXiv

Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler

In the decremental $(1+ε)$ -approximate Single-Source Shortest Path (SSSP) problem, we are given a graph $G=(V,E)$ with $n = |V|, m = |E|$ , undergoing edge deletions, and a distinguished source $s \in V$ , and we are asked to process edge deletions efficiently and answer queries for distance estimates $\widetilde{\mathbf{dist}}_G(s,v)$ for each $v \in V$ , at any stage, such that $\mathbf{dist}_G(s,v) \leq \widetilde{\mathbf{dist}}_G(s,v) \leq (1+ ε)\mathbf{dist}_G(s,v)$ . In the decremental $(1+ε)$ -approximate All-Pairs Shortest Path (APSP) problem, we are asked to answer queries for distance estimates $\widetilde{\mathbf{dist}}_G(u,v)$ for every $u,v \in V$ . In this article, we consider the problems for undirected, unweighted graphs. We present a new \emph{deterministic} algorithm for the decremental $(1+ε)$ -approximate SSSP problem that takes total update time $O(mn^{0.5 + o(1)})$ . Our algorithm improves on the currently best algorithm for dense graphs by Chechik and Bernstein [STOC 2016] with total update time $\tilde{O}(n^2)$ and the best existing algorithm for sparse graphs with running time $\tilde{O}(n^{1.25}\sqrt{m})$ [SODA 2017] whenever $m = O(n^{1.5 - o(1)})$ . In order to obtain this new algorithm, we develop several new techniques including improved decremental cover data structures for graphs, a more efficient notion of the heavy/light decomposition framework introduced by Chechik and Bernstein and the first clustering technique to maintain a dynamic \emph{sparse} emulator in the deterministic setting. As a by-product, we also obtain a new simple deterministic algorithm for the decremental $(1+ε)$ -approximate APSP problem with near-optimal total running time $\tilde{O}(mn /ε)$ matching the time complexity of the sophisticated but rather involved algorithm by Henzinger, Forster and Nanongkai [FOCS 2013].

preprint2020arXiv

Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds

Given a directed weighted graph $G=(V,E)$ undergoing vertex insertions \emph{and} deletions, the All-Pairs Shortest Paths (APSP) problem asks to maintain a data structure that processes updates efficiently and returns after each update the distance matrix to the current version of $G$ . In two breakthrough results, Italiano and Demetrescu [STOC '03] presented an algorithm that requires $\tilde{O}(n^2)$ \emph{amortized} update time, and Thorup showed in [STOC '05] that \emph{worst-case} update time $\tilde{O}(n^{2+3/4})$ can be achieved. In this article, we make substantial progress on the problem. We present the following new results: (1) We present the first deterministic data structure that breaks the $\tilde{O}(n^{2+3/4})$ worst-case update time bound by Thorup which has been standing for almost 15 years. We improve the worst-case update time to $\tilde{O}(n^{2+5/7}) = \tilde{O}(n^{2.71..})$ and to $\tilde{O}(n^{2+3/5}) = \tilde{O}(n^{2.6})$ for unweighted graphs. (2) We present a simple deterministic algorithm with $\tilde{O}(n^{2+3/4})$ worst-case update time ( $\tilde{O}(n^{2+2/3})$ for unweighted graphs), and a simple Las-Vegas algorithm with worst-case update time $\tilde{O}(n^{2+2/3})$ ( $\tilde{O}(n^{2 + 1/2})$ for unweighted graphs) that works against a non-oblivious adversary. Both data structures require space $\tilde{O}(n^2)$ . These are the first exact dynamic algorithms with truly-subcubic update time \emph{and} space usage. This makes significant progress on an open question posed in multiple articles [COCOON'01, STOC '03, ICALP'04, Encyclopedia of Algorithms '08] and is critical to algorithms in practice [TALG '06] where large space usage is prohibitive. Moreover, they match the worst-case update time of the best previous algorithms and the second algorithm improves upon a Monte-Carlo algorithm in a weaker adversary model with the same running time [SODA '17].

preprint2020arXiv

Near-Optimal Decremental SSSP in Dense Weighted Digraphs

In 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 = |V|, m = |E|$ 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(|P|)$ 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 it is possible to achieve total update time $mn^{0.9+o(1)}\log W$ if the algorithm is allowed to return $(1+ε)$ -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})$ . 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+ε)$ -approximate SSSP data structure with total update time $\tilde{O}(n^2 \log^4 W)$ . 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)$ . Our main technique allows us to convert SSSP algorithms for DAGs to ones for general graphs, which we believe has significant potential to influence future work.

preprint2020arXiv

New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs

In the dynamic Single-Source Shortest Paths (SSSP) problem, we are given a graph $G=(V,E)$ subject to edge insertions and deletions and a source vertex $s\in V$ , and the goal is to maintain the distance $d(s,t)$ for all $t\in V$ . Fine-grained complexity has provided strong lower bounds for exact partially dynamic SSSP and approximate fully dynamic SSSP [ESA'04, FOCS'14, STOC'15]. Thus much focus has been directed towards finding efficient partially dynamic $(1+ε)$ -approximate SSSP algorithms [STOC'14, ICALP'15, SODA'14, FOCS'14, STOC'16, SODA'17, ICALP'17, ICALP'19, STOC'19, SODA'20, SODA'20]. Despite this rich literature, for directed graphs there are no known deterministic algorithms for $(1+ε)$ -approximate dynamic SSSP that perform better than the classic ES-tree [JACM'81]. We present the first such algorithm. We present a \emph{deterministic} data structure for incremental SSSP in weighted digraphs with total update time $\tilde{O}(n^2 \log W)$ which is near-optimal for very dense graphs; here $W$ is the ratio of the largest weight in the graph to the smallest. Our algorithm also improves over the best known partially dynamic \emph{randomized} algorithm for directed SSSP by Henzinger et al. [STOC'14, ICALP'15] if $m=ω(n^{1.1})$ . We also provide improved conditional lower bounds. Henzinger et al. [STOC'15] showed that under the OMv Hypothesis, the partially dynamic exact $s$ - $t$ Shortest Path problem in undirected graphs requires amortized update or query time $m^{1/2-o(1)}$ , given polynomial preprocessing time. Under a hypothesis about finding Cliques, we improve the update and query lower bound for algorithms with polynomial preprocessing time to $m^{0.626-o(1)}$ . Further, under the $k$ -Cycle hypothesis, we show that any partially dynamic SSSP algorithm with $O(m^{2-ε})$ preprocessing time requires amortized update or query time $m^{1-o(1)}$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Maximilian Probst Gutenberg

Research overview

Is this your work?

11 publications

An Approximation Algorithm for Graph Label Selection

Derandomizing Directed Random Walks in Almost-Linear Time

Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets

Maximum Flow and Minimum-Cost Flow in Almost-Linear Time

Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing

Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time

Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary

Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler

Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds

Near-Optimal Decremental SSSP in Dense Weighted Digraphs

New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs

See the researcher in context

Building this map preview