Abstract: Maximum cardinality matching in bipartite graphs is an important and well-studied problem. The fully dynamic version, in which edges are inserted and deleted over time has also been the subject of much attention. Existing algorithms for dynamic matching (in general graphs) seem to fall into two groups: there are fast (mostly randomized) algorithms that do not achieve a better than 2-approximation, and there slow algorithms with update time that achieve a better-than-2 approximation. Thus the obvious question is whether we can design an algorithm -- deterministic or randomized -- that achieves a tradeoff between these two: a approximation and a better-than-2 approximation simultaneously. We answer this question in the affirmative for bipartite graphs. Our main result is a fully dynamic algorithm that maintains a approximation in worst-case update time . We also give stronger results for graphs whose arboricity is at most , achieving a approximation in worst-case time for constant . When the arboricity is constant, this bound is and when the arboricity is polylogarithmic the update time is also polylogarithmic. The most important technical developement is the use of an intermediate graph we call an edge degree constrained subgraph (EDCS). This graph places constraints on the sum of the degrees of the endpoints of each edge: upper bounds for matched edges and lower bounds for unmatched edges. The main technical content of our paper involves showing both how to maintain an EDCS dynamically and that and EDCS always contains a sufficiently large matching. We also make use of graph orientations to help bound the amount of work done during each update.
Recommendations
Cites work
- AdWords and generalized online matching
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Deterministic fully dynamic data structures for vertex cover and matching
- Edge-Disjoint Spanning Trees of Finite Graphs
- Faster dynamic matchings and vertex connectivity
- Fully Dynamic Maximal Matching in O (log n) Update Time
- scientific article; zbMATH DE number 3099866 (Why is no real title available?)
- Linear-time approximation for maximum weight matching
- Maintaining a large matching and a small vertex cover
- Online stochastic packing applied to display ad allocation
- Orienting fully dynamic graphs with worst-case time bounds
- The Distribution of a Product from Several Sources to Numerous Localities
Cited in
(42)- Shortest augmenting paths for online matchings on trees
- A simple greedy algorithm for dynamic graph orientation
- Faster dynamic matchings and vertex connectivity
- Fast dynamic weight matchings in convex bipartite graphs
- Maintaining approximate maximum weighted matching in fully dynamic graphs
- Maintaining approximate maximum matching in an incremental bipartite graph in polylogarithmic update time
- Maintaining bipartite matchings in the presence of failures
- Dynamic Matchings in Left Weighted Convex Bipartite Graphs
- Dynamic matchings in left vertex weighted convex bipartite graphs
- Dynamic Matchings in Convex Bipartite Graphs
- Deterministic fully dynamic data structures for vertex cover and matching
- Faster fully dynamic matchings with small approximation ratios
- Dynamic \((1 + \epsilon)\)-approximate matchings: a density-sensitive approach
- On the hardness of partially dynamic graph problems and connections to diameter
- scientific article; zbMATH DE number 6866348 (Why is no real title available?)
- Fully dynamic maximal matching in O( n) update time (corrected version)
- Local algorithms for bounded degree sparsifiers in sparse graphs
- Dynamic matching: reducing integral algorithms to approximately-maximal fractional algorithms
- Fully dynamic almost-maximal matching: breaking the polynomial worst-case time barrier
- Improved dynamic graph coloring
- Improved algorithm for dynamic b-matching
- Round compression for parallel matching algorithms
- A simple greedy algorithm for dynamic graph orientation
- A fast dynamic optimum algorithm for maximum matching in bipartite graphs
- scientific article; zbMATH DE number 7651215 (Why is no real title available?)
- Approximating multistage matching problems
- Multiplicative auction algorithm for approximate maximum weight bipartite matching
- A Batch-dynamic Suitor Algorithm for Approximating Maximum Weighted Matching
- On regularity lemma and barriers in streaming and dynamic matching
- Stochastic minimum vertex cover in general graphs: a 3/2-approximation
- Sublinear algorithms for (1.5+)-approximate matching
- Sublinear time algorithms and complexity of approximate maximum matching
- Dynamic matching with better-than-2 approximation in polylogarithmic update time
- Improved bounds for matching in random-order streams
- Improved bounds for matching in random-order streams
- Weighted matching in the random-order streaming and robust communication models
- Maximum weight b-matchings in random-order streams
- Dynamic matching with better-than-2 approximation in polylogarithmic update time
- A generalized matching reconfiguration problem
- Beating two-thirds for random-order streaming matching
- Deterministic rounding of dynamic fractional matchings
- Tree-packing revisited: faster fully dynamic min-cut and arboricity
This page was built for publication: Fully dynamic matching in bipartite graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3448782)
