The Power of Linear-Time Data Reduction for Maximum Matching
- PDF / 3,345,508 Bytes
- 45 Pages / 439.37 x 666.142 pts Page_size
- 97 Downloads / 273 Views
The Power of Linear‑Time Data Reduction for Maximum Matching George B. Mertzios1 · André Nichterlein2 · Rolf Niedermeier2 Received: 18 January 2019 / Accepted: 13 June 2020 © The Author(s) 2020
Abstract Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph √ primitives. For m-edge and n-vertex graphs, it is well-known to be solvable in O(m n) time; however, for several applications this running time is still too slow. We investigate how linear-time (and almost linear-time) data reduction (used as preprocessing) can alleviate the situation. More specifically, we focus on linear-time kernelization. We start a deeper and systematic study both for general graphs and for bipartite graphs. Our data reduction algorithms easily comply (in form of preprocessing) with every solution strategy (exact, approximate, heuristic), thus making them attractive in various settings. Keywords Maximum-cardinality matching · Bipartite graphs · Linear-time algorithms · Kernelization · Parameterized complexity analysis · FPT in P
A short version of this article appeared in the Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS ’17), pages 46:1–46:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. This article now contains all proofs in full detail. Supported by the EPSRC grant EP/P020372/1, by the DFG project FPTinP, NI 369/16, and by a postdoc fellowship of the German Academic Exchange Service (DAAD) while the second author was at Durham University. * André Nichterlein andre.nichterlein@tu‑berlin.de George B. Mertzios [email protected] Rolf Niedermeier rolf.niedermeier@tu‑berlin.de 1
Department of Computer Science, Durham University, Durham, UK
2
Algorithmics and Computational Complexity, Faculty IV, TU Berlin, Berlin, Germany
13
Vol.:(0123456789)
Algorithmica
1 Introduction “Matching is a powerful piece of algorithmic magic” [24]. In the Maximum Matching problem, given an undirected graph, one has to compute a maximum-cardinality set of nonoverlapping edges. Maximum matching is arguably among the most fundamental graph-algorithmic primitives allowing for a polynomial-time algorithm. More specifically, √ on an n-vertex and m-edge graph a maximum matching can be found in O(m n) time [21]. Improving this upper time bound resisted decades of research. Recently, however, Duan and Pettie [8] presented a linear-time algorithm that computes a (1 − 𝜖)-approximate maximum-weight matching, where the √ running time dependency on 𝜖 is 𝜖 −1 log(𝜖 −1 ) . For the unweighted case, the O(m n) algorithm of Micali and Vazirani [21] implies a linear-time (1 − 𝜖)-approximation, where in this case the running time dependency on 𝜖 is 𝜖 −1 [8]. We take a different route: First, we do not give up the quest for optimal solutions. Second, we focus on efficient—more specifically, linear-time executable—data reduction rules, that is, not solving an instance but significantly shrinking its size before actually solving the problem.1 I
Data Loading...
