Faster approximate matching algorithms for large dynamic graphs
Faster Semi-Streaming and Dynamic Approximate Maximum Weight Matchings in General Graphs: A Unified Framework
Data Structures and Algorithms
Summary
Finding the largest possible set of matched edges in a network is an important problem in computer science. This paper presents faster algorithms to find approximate solutions for weighted matchings in large graphs, even when the graph changes over time by adding or removing edges. The authors introduce a unified approach that breaks down the problem into easier parts and uses a smoothing technique to handle complex constraints efficiently. Their methods work well in streaming data and dynamic graph updates, improving speed while maintaining good approximation quality.
What this means in practice
- •For network engineers: Improve routing and resource allocation in large evolving networks by faster approximate matching of network connections.
- •For database system developers: Speed up query optimization and join processing by using fast approximate weighted matchings on dynamic join graphs.
Authors
Jiale Chen
Abstract
We study the $(1-\varepsilon)$-approximate maximum weight matching problem in general graphs with $n$ vertices and integer edge weights in $[1,W]$. For $W=n^{O(1)}$, we obtain faster algorithms in the semi-streaming and dynamic settings: (1) Semi-streaming: Deterministic $O(\varepsilon^{-2})$-pass and $O(\varepsilon^{-2}\log(1/\varepsilon))$-pass algorithms for unweighted and weighted matching. (2) Incremental: A deterministic algorithm for weighted matching processing $m$ edge insertions in total time $O((m\varepsilon^{-3}+n\varepsilon^{-6})\log^3 n)$. (3) Decremental: A randomized algorithm for weighted matching processing all edge deletions from an $m$-edge graph in total time $O((m\varepsilon^{-8}+n\varepsilon^{-47})\log^{O(1)}n)$ with high probability. (4) Fully dynamic: A deterministic reduction from weighted matching in general graphs to unweighted matching in bipartite graphs incurring $O(\varepsilon^{-4}\log^{O(1)}(1/\varepsilon))$ multiplicative update-time overhead, independent of $n$. Underlying these results is a unified framework that reduces the problem to repeatedly solving two simpler matching subproblems: a $(1-\varepsilon)$-approximate maximum weight matching on a sparse subgraph with $O(n/\varepsilon)$ edges, and a constant approximation on the remaining edges. The framework builds on dual entropy regularization, a smoothing technique underlying efficient solvers for packing linear programs. To handle the exponentially many odd-set constraints, we adapt the smoothing technique to regularize only the vertex duals and develop a new cut partition that preserves odd-set feasibility during optimization.