Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time

2022/05/03 by Sally Dong, Dong, Sally, Yu Gao +11 · 2 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.2205.01562

openalex publication_date 2022/05/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a nearly-linear time algorithm for finding a minimum-cost flow in planar graphs with polynomially bounded integer costs and capacities. The previous fastest algorithm for this problem is based on interior point methods (IPMs) and works for general sparse graphs in O(n^1.5poly(log n)) time [Daitch-Spielman, STOC'08]. Intuitively, Ω(n^1.5) is a natural runtime barrier for IPM-based methods, since they require √(n) iterations, each routing a possibly-dense electrical flow. To break this barrier, we develop a new implicit representation for flows based on generalized nested-dissection [Lipton-Rose-Tarjan, JSTOR'79] and approximate Schur complements [Kyng-Sachdeva, FOCS'16]. This implicit representation permits us to design a data structure to route an electrical flow with sparse demands in roughly √(n) update time, resulting in a total running time of O(n\cdotpoly(log n)). Our results immediately extend to all families of separable graphs.

Cited by

• Fully Dynamic Spectral Sparsification for Directed Hypergraphs
• Hierarchical Forecast Reconciliation on Networks: A Network Flow Optimization Formulation

Related

• Faster Sparse Minimum Cost Flow by Electrical Flow Localization
• A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow
• Min-Cost Flow in Unit-Capacity Planar Graphs
• Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances
• Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao