CS Paper Radar

A Note on the Hardness of Partially Dynamic Max Flow

Thatchaphol Saranurak, Benyu Wang

cs.DS ·submitted 2026-11-06 20:02 UTC · v1
theoryhot direction

Abstract

We study the fine-grained complexity of partially dynamic max flow in capacitated graphs. Assuming the combinatorial 4-clique hypothesis, combinatorial algorithms require $Ω(n^{2-o(1)})$ amortized update time. Thus, recomputing max flow after each update is optimal up to subpolynomial factors for combinatorial algorithms in dense graphs. The previous conditional lower bound was $Ω(n^{1-o(1)})$ amortized update time under SETH or the OMv hypothesis and applies to all algorithms [Dah16].

Comment
SOSA 2027

Closest papers

Nearest neighbours by meaning across the whole index.

Combinatorial Minimum Cost Flow in Almost-Linear Time on Dense Graphs

cs.DS ·2026-10-23 ·Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak
similarity 0.66
Abstract · 101 pages

We give a combinatorial algorithm that computes an exact minimum-cost flow in $n^{2+o(1)}$ time. This is the first combinatorial improvement since Goldberg-Tarjan [GT87], and is almost optimal in dense graphs. All previous faster algorithms, including the almost-linear-time algorithm of Chen et al. [CKL+22], rely on interior-point methods. Our main conceptual contribution is a black-box reduction from exact minimum-cost flow on general graphs to its approximation on DAGs, with only an $n^{o(1)}$ loss on the running time. This reduction allows future work on combinatorial minimum-cost flow to focus on DAGs, typically much easier to handle than general graphs. Our $n^{2+o(1)}$-time algorithm follows by combining this reduction with a simple augmenting-path-based approximation algorithm on DAGs. The reduction is based on a new structural result, called a flow-cost-preserving DAG projection. Given an arbitrary directed graph, this construction produces a DAG that approximately preserves both the congestion of flows and their cost up to a small loss.

0.48

Output-linear time enumeration of potential maximal cliques

cs.DS ·2026-10-14 ·Pierre Bergé, Vincent Limouzy, Nicolas Schivre
top venue similarity 0.65
Abstract · This paper was accepted at SODA 2027. 54 pages, 18 figures

First defined by Bouchitté and Todinca, Potential Maximal Cliques (PMC) are a well studied notion in graph theory due to its numerous applications. The PMCs of an undirected graph $G$ are defined as the maximal cliques of the minimal triangulations of $G$. Their number can be exponential in the size of the graph. PMCs were crucial in the design of a polynomial-time algorithm which solves Maximum Weight Independent Set on $P_6$-free graphs (Grzesik, Klimošová, Pilipczuk, Pilipczuk, 2020). They also play a central role in the proposal of a polynomial-time algorithm to solve Largest Induced Subgraph of treewidth $\le t$ (Fomin, Todinca, Villanger, 2013). Last but not least, certainly one of the main application of PMCs is the existence of an exact dynamic-programming algorithm to determine the treewidth of a graph (Fomin, Kratsch, Todinca, Villanger, 2008) which uses its list of PMCs as an input. In fact, the enumeration of PMCs stands as the bottleneck for the computation of treewidth with this method: the PMC-enumeration step takes output-quadratic time (Bouchitté, Todinca, 2002) while the dynamic-programming one takes a time linear in the number of PMCs. This two-step procedure was proven to be among the most performing approaches in practice to determine treewidth. Answering a longstanding open question, we propose an algorithm to enumerate PMCs in output-linear time, i.e. a running time linear in the number of PMCs. This offers nice perspectives not only from the theoretical viewpoint - better running time for the PMC-based methods determining treewidth, for Minimum Fill-In and Largest Induced Subgraph of treewidth $\le t$ - but also from the practical side, with the possibility to propose top-performance implementation.

0.68

Tight bounds and output sensitive algorithms for maximal clique enumeration in link streams

cs.DS ·2026-10-08 ·George Manoussakis
theory similarity 0.64
Abstract

A link stream is a set of interactions between pairs of vertices, each one lasting during some time interval, and a clique of a link stream is a set of vertices together with a time interval during which all of them interact. A clique is maximal if neither its vertex set nor its interval can be enlarged. All known algorithms listing the maximal cliques of a link stream may spend time exponential in the size of a clique for each clique they output. Here, we approach the question under the light of two parameters of the instantaneous graphs of the stream, their maximum degree $Δ$ and their degeneracy $k$. We prove that a link stream with $m$ links has $O(mΔ^2 3^{Δ/3})$ maximal cliques, and that a link stream with $n$ vertices and $|\mathcal{T}|$ distinct end times has $O(n|\mathcal{T}|k^2 3^{k/3})$ maximal cliques. Both bounds are tight up to a factor polynomial in $Δ$ and $k$ respectively, and the second one improves the factor $2^k$ of previous bounds to $3^{k/3}$. Then we present two algorithms. The first one has setup time $O(m\log m)$ and polynomial time delay $\mathrm{poly}(Δ)\log m$. The second one has setup time $O(m\log m+mk^2\log^3 n)$ and polynomial time delay $\mathrm{poly}(k)\log m$. To the best of our knowledge, these are the first algorithms with polynomial time delay for this problem. We also give an online version of the second algorithm, and we show that our results apply to the $Δ$-cliques and $(Δ,γ)$-cliques of temporal graphs.

0.42

Partially-Dynamic All-Pairs Maxflow and Effective Resistance via Stable Sparsifiers

cs.DS ·2026-08-26 ·Gramoz Goranci, Rasmus Kyng, Maximilian Probst Gutenberg, Yibin Zhao, Gernot Zöcklein
similarity 0.64
Abstract

We give a randomized data structure for undirected weighted graphs that are partially dynamic, i.e., that undergo either only edge insertions or only edge deletions. The data structure maintains $(1\pmε)$-approximations to the maxflow value and effective resistance between any queried pair of vertices, with total update time $\widetilde{O}_ε(n^2)$ and worst-case query time $\widetilde{O}_ε(1)$. Thus, for dense graphs where $m = Ω(n^2)$, our guarantees are near-optimal. Our algorithms succeed with high probability against an adaptive adversary. Our result follows from a simple stability principle for partially dynamic graphs. We show how to partition an online sequence of $m$ updates into $\widetilde{O}(n/ε)$ epochs such that every graph within an epoch is a $(1\pm O(ε))$-spectral approximation of the graph at the beginning of the epoch. The epochs are determined by the cumulative leverage score of the updated edges: small leverage-score mass implies small spectral change, while the total leverage-score mass over a monotone update sequence is $\widetilde{O}(n)$. Consequently, a spectral sparsifier needs to be recomputed only once per epoch. Applying known static all-pairs maxflow and effective-resistance oracles to these sparsifiers then yields the result.

0.09

Max Weight Independent Set in graphs with no long claws nor large induced bicliques

cs.DS ·2026-10-30 ·Maria Chudnovsky, Paweł Rzążewski
similarity 0.64
Abstract

The complexity of Max Weight Independent Set (MWIS) in graphs excluding a fixed subdivided claw is one of the central open problems in algorithmic graph theory. We show that MWIS can be solved in polynomial time in graphs excluding a fixed subdivided claw and a fixed biclique as an induced subgraph. This strengthens a result of Abrishami, Chudnovsky, Dibek, Pilipczuk, and Rzążewski [ACM TALG 2026] who showed an analogous result, but under a stronger assumption that some biclique is excluded as a subgraph.

0.19

Dynamic Edge Orientation on Low-Arboricity Graphs: Breaking the $\log n$ Barrier

cs.DS ·2026-11-06 ·Sam Hiken, Nicole Wein
theory similarity 0.64
Abstract · 29 pages, 3 figures

We study the dynamic edge orientation problem introduced in a seminal 1999 paper by Brodal and Fagerberg: given a fully dynamic graph $G$ with arboricity bounded by $α$, maintain an orientation on $G$'s edges so every vertex has out-degree upper bounded by a function of $α$. They provided an algorithm with $O(α+ \log n)$ amortized update time that maintains an orientation with maximum out-degree $O(α)$. In the decades since, this algorithm has found widespread applications in dynamic graph algorithms. Nevertheless, it has remained a stubborn open question whether, when $α= o(\log n)$, the $O(\log n)$ upper bound can be improved. We answer this 27-year-old question in the affirmative, showing that Brodal and Fagerberg's algorithm for maintaining an out-degree $O(α)$ orientation runs in $O(α\cdot \log \log n)$ amortized update time, which is an exponentially-improved dependence on $n$. This is the first improvement on Brodal and Fagerberg's upper bound even for the $α=1$ case of dynamic forests. Our crucial technical innovation is to construct a hierarchy of dynamic graphs with a property we call near isolation. We believe that this construction may be useful for related problems.

0.24

Maximum Flow Without the Outer IPM

cs.DS ·2026-08-18 ·Jason Li, Alex Wice
similarity 0.63
Abstract · 9 pages

We show that the balancing weights technique of Li (2026) actually produces an approximate *pseudo-circulation* of a directed, capacitated graph in $m^{1+o(1)}$ time. Together with standard flow techniques, we obtain an $m^{1+o(1)}$ time maximum flow algorithm that avoids the interior-point method framework of recent almost-linear time algorithms (Chen et al. FOCS 2022, van den Brand et al. FOCS 2024).

0.39

Maximum Edge Open Packing on AT-Free, Chordal, and Convex Bipartite Graphs

cs.DM math.CO ·2026-10-01 ·Gautam K. Das, Kamal Santra
similarity 0.63
Abstract

An edge open packing is a set of edges whose endpoints induce a disjoint union of stars. We study the problem of finding a maximum edge open packing in AT-free, chordal, and convex bipartite graphs. For AT-free graphs, we use the oriented star-conflict graph $A_G$, introduced by Das and Santra, for which $ρ_e^o(G)=α(A_G)$, and prove that $A_G$ is AT-free whenever $G$ is AT-free. Consequently, a known maximum independent set algorithm for AT-free graphs yields an $O(n^2+m^4)$-time algorithm for Maximum Edge Open Packing, where $n$ and $m$ denote the numbers of vertices and edges of $G$, respectively. For chordal graphs, we develop an $O(n^4)$-time dynamic programming algorithm over a nice tree decomposition derived from a clique tree, exploiting the structural fact that the endpoint set of an edge open packing intersects every clique in at most two vertices. Finally, for convex bipartite graphs, we obtain an $O(n^4)$-time dynamic programming algorithm based on two boundary indices that separate consecutive star components. This result extends the previously known algorithm for biconvex bipartite graphs and, in particular, provides an improved explicit running-time bound for that class.

0.07