# Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments

arXiv: https://arxiv.org/abs/1806.09683 · HTML: https://mlsanity.com/paper/1806.09683/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jun 2018.

## Built on by (most cited first, 1 of 1)

- [The Complexity of Optimizing Atomic Congestion](https://mlsanity.com/paper/2312.10219/) (2023)

## Abstract (arXiv)

Finding a maximum-cardinality or maximum-weight matching in (edge-weighted) undirected graphs is among the most prominent problems of algorithmic graph theory. For n-vertex and m-edge graphs, the best known algorithms run in widetildeO(m√n) time. We build on recent theoretical work focusing on linear-time data reduction rules for finding maximum-cardinality matchings and complement the theoretical results by presenting and analyzing (thereby employing the kernelization methodology of parameterized complexity analysis) new (near-)linear-time data reduction rules for both the unweighted and the positive-integer-weighted case. Moreover, we experimentally demonstrate that these data reduction rules provide significant speedups of the state-of-the art implementations for computing matchings in real-world graphs: the average speedup factor is 4.7 in the unweighted case and 12.72 in the weighted case.