2021/09/01 by Monika Henzinger, Billy Jin, Henzinger, Monika +5
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #Parallel Computing and Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2109.00653
openalex publication_date 2021/09/01 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
We study the problem of finding flows in undirected graphs so as to minimize\nthe weighted p-norm of the flow for any p > 1. When p=2, the problem is\nthat of finding an electrical flow, and its dual is equivalent to solving a\nLaplacian linear system. The case p = \∞ corresponds to finding a\nmin-congestion flow, which is equivalent to max-flows. A typical algorithmic\nconstruction for such problems considers vertex potentials corresponding to the\nflow conservation constraints, and has two simple types of update steps: cycle\ntoggling, which modifies the flow along a cycle, and cut toggling, which\nmodifies all potentials on one side of a cut. Both types of steps are typically\nperformed relative to a spanning tree T; then the cycle is a fundamental\ncycle of T, and the cut is a fundamental cut of T. In this paper, we show\nthat these simple steps can be used to give a novel efficient implementation\nfor the p = 2 case and to find near-optimal p-norm flows in a low number of\niterations for all values of p > 1. Compared to known faster algorithms for\nthese problems, our algorithms are simpler, more combinatorial, and also expose\nseveral underlying connections between these algorithms and dynamic graph data\nstructures that have not been formalized previously.\n