research-article

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

Authors:

Tomohiro Koana,

Viatcheslav Korenwein,

André Nichterlein,

Rolf Niedermeier,

Philipp ZschocheAuthors Info & Claims

Journal of Experimental Algorithmics (JEA), Volume 26

Article No.: 1.3, Pages 1 - 30

https://doi.org/10.1145/3439801

Published: 23 April 2021 Publication History

Abstract

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 Õ(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.

References

[1]

Faisal N. Abu-Khzam, Michael R. Fellows, Michael A. Langston, and W. Henry Suters. 2007. Crown structures for vertex cover kernelization. Theory of Computing Systems 41, 3 (2007), 411--430.

Digital Library

[2]

Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. 1983. Data Structures and Algorithms. Addison-Wesley.

[3]

Takuya Akiba and Yoichi Iwata. 2016. Branch-and-reduce exponential/FPT algorithms in practice: A case study of vertex cover. Theoretical Computer Science 609 (2016), 211--225.

Digital Library

[4]

Miklós Bartha and Miklós Krész. 2009. A depth-first algorithm to reduce graphs in linear time. In Proceedings of the 11th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC’09). IEEE, 273--281.

Digital Library

[5]

Miklós Bartha and Miklós Krész. 2020. On the König deficiency of zero-reducible graphs. Journal of Combinatorial Optimization 39, 1 (2020), 273--292.

[6]

Matthias Bentert, Alexander Dittmann, Leon Kellerhals, André Nichterlein, and Rolf Niedermeier. 2020. An adaptive version of Brandes’ algorithm for betweenness centrality. Journal of Graph Algorithms and Applications 24, 3 (2020), 483--522.

[7]

Miroslav Chlebík and Janka Chlebíková. 2008. Crown reductions for the Minimum Weighted Vertex Cover problem. Discrete Applied Mathematics 156, 3 (2008), 292--312.

Digital Library

[8]

David Coudert, Guillaume Ducoffe, and Alexandru Popa. 2019. Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. ACM Transactions on Algorithms 15, 3 (2019), 33:1–33:57.

Digital Library

[9]

Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer.

[10]

Holger Dell and Dieter van Melkebeek. 2014. Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. Journal of the ACM 61, 4 (2014), 23:1–23:27.

Digital Library

[11]

Ran Duan and Seth Pettie. 2014. Linear-time approximation for maximum weight matching. Journal of the ACM 61, 1 (2014), 1:1–1:23.

Digital Library

[12]

Ran Duan, Seth Pettie, and Hsin-Hao Su. 2018. Scaling algorithms for weighted matching in general graphs. ACM Transactions on Algorithms 14, 1 (2018), 8:1–8:35.

Digital Library

[13]

Jack Edmonds. 1965. Maximum matching and a polyhedron with 0,1-vertices. Journal of Research of the National Bureau of Standards B 69, 125–130 (1965), 55--56.

[14]

Jack Edmonds. 1965. Paths, trees, and flowers. Canadian Journal of Mathematics 17, 3 (1965), 449--467.

[15]

Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Michal Pilipczuk, and Marcin Wrochna. 2018. Fully polynomial-time parameterized computations for graphs and matrices of low treewidth. ACM Transactions on Algorithms 14, 3 (2018), 34:1–34:45.

Digital Library

[16]

Archontia C. Giannopoulou, George B. Mertzios, and Rolf Niedermeier. 2017. Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs. Theoretical Computer Science 689 (2017), 67--95.

[17]

Falko Hegerfeld and Stefan Kratsch. 2019. On adaptive algorithms for maximum matching. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP’19) (LIPIcs), Vol. 132. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 71:1–71:16.

[18]

Demian Hespe, Sebastian Lamm, Christian Schulz, and Darren Strash. 2020. WeGotYouCovered: The winning solver from the PACE 2019 challenge, vertex cover track. In Proceedings of the SIAM Workshop on Combinatorial Scientific Computing (CSC’20). SIAM, 1--11.

[19]

Dorit S. Hochbaum. 2002. Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations. European Journal of Operational Research 140, 2 (2002), 291--321.

[20]

John E. Hopcroft and Richard M. Karp. 1973. An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing 2, 4 (1973), 225--231.

[21]

Michael Huang and Clifford Stein. 2017. Extending search phases in the Micali-Vazirani algorithm. In Proceedings of the 16th International Symposium on Experimental Algorithms (SEA’17) (LIPIcs), Vol. 75. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 10:1–10:19.

[22]

Yoichi Iwata, Tomoaki Ogasawara, and Naoto Ohsaka. 2018. On the power of tree-depth for fully polynomial FPT algorithms. In Proceedings of the 35th International Symposium on Theoretical Aspects of Computer Science (STACS’18) (LIPIcs), Vol. 96. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 41:1–41:14.

[23]

Yoichi Iwata, Keigo Oka, and Yuichi Yoshida. 2014. Linear-time FPT algorithms via network flow. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’14). SIAM, 1749--1761.

Digital Library

[24]

David Juedes, Benny Chor, and Michael R. Fellows. 2004. Linear kernels in linear time, or how to save k colors in O(n2) steps. In Proceedings of the 30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG ’04) (Lecture Notes in Computer Science). Springer.

[25]

Richard M. Karp and Michael Sipser. 1981. Maximum matchings in sparse random graphs. In Proceedings of the 22nd Annual IEEE Symposium on Foundations of Computer Science (FOCS’81). IEEE, 364--375.

[26]

Kamer Kaya, Johannes Langguth, Ioannis Panagiotas, and Bora Uçar. 2020. Karp-Sipser based kernels for bipartite graph matching. In Proceedings of the 22th Symposium on Algorithm Engineering and Experiments (ALENEX’20). SIAM, 134--145.

[27]

John D. Kececioglu and A. Justin Pecqueur. 1998. Computing maximum-cardinality matchings in sparse general graphs. In Proceedings of the 2nd International Workshop on Algorithm Engineering (WAE’92). 121--132.

[28]

Vladimir Kolmogorov. 2009. Blossom V: A new implementation of a minimum cost perfect matching algorithm. Mathematical Programming Computation 1, 1 (2009), 43--67.

[29]

Viatcheslav Korenwein, André Nichterlein, Rolf Niedermeier, and Philipp Zschoche. 2018. Data reduction for maximum matching on real-world graphs: Theory and experiments. In Proceedings of the 26th Annual European Symposium on Algorithms (ESA’18) (LIPIcs), Vol. 112. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 53:1–53:13.

[30]

Bernd Korte and Jens Vygen. 2018. Combinatorial Optimization – Theory and Algorithms. Springer.

[31]

Stefan Kratsch and Florian Nelles. 2018. Efficient and adaptive parameterized algorithms on modular decompositions. In Proceedings of the 26th Annual European Symposium on Algorithms (ESA’18) (LIPIcs), Vol. 112. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 55:1–55:15.

[32]

Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection.

[33]

George B. Mertzios, André Nichterlein, and Rolf Niedermeier. 2020. The power of linear-time data reduction for maximum matching. Algorithmica 82, 12 (2020), 3521--3565.

[34]

Silvio Micali and Vijay V. Vazirani. 1980. An O(√|V||E|) algorithm for finding maximum matching in general graphs. In Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science (FOCS’80). IEEE, 17--27.

[35]

Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani. 1987. Matching is as easy as matrix inversion. Combinatorica 7, 1 (1987), 105--113.

Digital Library

[36]

George L. Nemhauser and Leslie E. Trotter. 1975. Vertex packings: Structural properties and algorithms. Mathematical Programming 8 (1975), 232--248.

Digital Library

[37]

Rolf Niedermeier. 2010. Reflections on multivariate algorithmics and problem parameterization. In Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS’07) (LIPIcs), Vol. 5. IBFI Dagstuhl, Germany, 17--32.

[38]

Vijay V. Vazirani. 2020. A proof of the MV matching algorithm. CoRR abs/2012.03582 (2020). arxiv:2012.03582 https://arxiv.org/abs/2012.03582

Cited By

Brand CGanian RKalyanasundaram SMc Inerney F(2025)The complexity of optimizing atomic congestionArtificial Intelligence10.1016/j.artint.2024.104241338(104241)Online publication date: Jan-2025
https://doi.org/10.1016/j.artint.2024.104241
Brand CGanian RKalyanasundaram SMc Inerney FWooldridge MDy JNatarajan S(2024)The complexity of optimizing atomic congestionProceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v38i18.29982(20044-20052)Online publication date: 20-Feb-2024
https://dl.acm.org/doi/10.1609/aaai.v38i18.29982
Himmel AMertzios GNichterlein ANiedermeier R(2024)Fast Parameterized Preprocessing for Polynomial-Time Solvable Graph ProblemsCommunications of the ACM10.1145/362471367:4(70-79)Online publication date: 25-Mar-2024
https://dl.acm.org/doi/10.1145/3624713
Show More Cited By

Index Terms

Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Matchings and factors
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
    2. Parameterized complexity and exact algorithms
      1. Fixed parameter tractability

Recommendations

The Power of Linear-Time Data Reduction for Maximum Matching
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 \sqrt{n})$ time; however, for several applications this running time is ...
Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
STOC '10: Proceedings of the forty-second ACM symposium on Theory of computing

Consider the following two-player communication process to decide a language L: The first player holds the entire input x but is polynomially bounded; the second player is computationally unbounded but does not know any part of x; their goal is to ...
Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
Structural decompositions, width parameters, and graph labelings (DAS 5)

Many NP-complete problems on planar graphs are ''fixed-parameter tractable:'' Recent theoretical work provided tree decomposition-based fixed-parameter algorithms exactly solving various parameterized problems on planar graphs, among others VERTEX COVER,...

Comments

Information & Contributors

Information

Published In

cover image ACM Journal of Experimental Algorithmics

ACM Journal of Experimental Algorithmics Volume 26, Issue

December 2021

479 pages

ISSN:1084-6654

EISSN:1084-6654

DOI:10.1145/3446425

Issue’s Table of Contents

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 April 2021

Accepted: 01 November 2020

Revised: 01 September 2020

Received: 01 November 2019

Published in JEA Volume 26

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Deutsche Forschungsgemeinschaft

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
185
Total Downloads

Downloads (Last 12 months)22
Downloads (Last 6 weeks)1

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Brand CGanian RKalyanasundaram SMc Inerney F(2025)The complexity of optimizing atomic congestionArtificial Intelligence10.1016/j.artint.2024.104241338(104241)Online publication date: Jan-2025
https://doi.org/10.1016/j.artint.2024.104241
Brand CGanian RKalyanasundaram SMc Inerney FWooldridge MDy JNatarajan S(2024)The complexity of optimizing atomic congestionProceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v38i18.29982(20044-20052)Online publication date: 20-Feb-2024
https://dl.acm.org/doi/10.1609/aaai.v38i18.29982
Himmel AMertzios GNichterlein ANiedermeier R(2024)Fast Parameterized Preprocessing for Polynomial-Time Solvable Graph ProblemsCommunications of the ACM10.1145/362471367:4(70-79)Online publication date: 25-Mar-2024
https://dl.acm.org/doi/10.1145/3624713
Wolf RHeeger KNichterlein A(2024)Effective Data Reduction for Strongly Stable Matching in Very Sparse GraphsInformation Processing Letters10.1016/j.ipl.2024.106534(106534)Online publication date: Oct-2024
https://doi.org/10.1016/j.ipl.2024.106534
Mertzios GMolter HNiedermeier RZamaraev VZschoche P(2023)Computing maximum matchings in temporal graphsJournal of Computer and System Sciences10.1016/j.jcss.2023.04.005137:C(1-19)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1016/j.jcss.2023.04.005
Bentert MNichterlein A(2022)Parameterized Complexity of DiameterAlgorithmica10.1007/s00453-022-01032-985:2(325-351)Online publication date: 5-Sep-2022
https://dl.acm.org/doi/10.1007/s00453-022-01032-9
Langguth JPanagiotas IUcar B(2021)Shared-memory implementation of the Karp-Sipser kernelization process2021 IEEE 28th International Conference on High Performance Computing, Data, and Analytics (HiPC)10.1109/HiPC53243.2021.00021(71-80)Online publication date: Dec-2021
https://doi.org/10.1109/HiPC53243.2021.00021

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents