Document Open Access Logo

The Power of Linear-Time Data Reduction for Maximum Matching

Authors George B. Mertzios, André Nichterlein, Rolf Niedermeier

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.46.pdf
  • Filesize: 0.6 MB
  • 14 pages

Document Identifiers

Author Details

George B. Mertzios
André Nichterlein
Rolf Niedermeier

Cite As Get BibTex

George B. Mertzios, André Nichterlein, and Rolf Niedermeier. The Power of Linear-Time Data Reduction for Maximum Matching. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.MFCS.2017.46

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

Subject Classification

Keywords
  • Maximum-cardinality matching
  • bipartite graphs
  • linear-time algorithms
  • kernelization
  • parameterized complexity analysis
  • FPT in P

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Reuven Bar-Yehuda, Dan Geiger, Joseph Naor, and Ron M. Roth. Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference. SIAM Journal on Computing, 27(4):942-959, 1998. URL: http://dx.doi.org/10.1137/S0097539796305109.
  2. Norbert Blum. A new approach to maximum matching in general graphs. In Proceedings of the 17th International Colloquium on Automata, Languages, and Programming (ICALP '90), volume 443 of LNCS, pages 586-597. Springer, 1990. URL: http://dx.doi.org/10.1007/BFb0032060.
  3. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Preprocessing for treewidth: A combinatorial analysis through kernelization. SIAM Journal on Discrete Mathematics, 27(4):2108-2142, 2013. URL: http://dx.doi.org/10.1137/120903518.
  4. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernelization lower bounds by cross-composition. SIAM Journal on Discrete Mathematics, 28(1):277-305, 2014. URL: http://dx.doi.org/10.1137/120880240.
  5. Andreas Brandstädt, Van Bang Le, and Jeremy P. Spinrad. Graph Classes: a Survey, volume 3 of SIAM Monographs on Discrete Mathematics and Applications. SIAM, 1999. Google Scholar
  6. Leizhen Cai. Parameterized complexity of Vertex Colouring. Discrete Applied Mathematics, 127(1):415-429, 2003. URL: http://dx.doi.org/10.1016/S0166-218X(02)00242-1.
  7. Maw-Shang Chang. Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs. In Proceedings of the 7th International Symposium on Algorithms and Computation (ISAAC '96), volume 1178 of LNCS, pages 146-155. Springer, 1996. URL: http://dx.doi.org/10.1007/BFb0009490.
  8. Elias Dahlhaus and Marek Karpinski. Matching and multidimensional matching in chordal and strongly chordal graphs. Discrete Applied Mathematics, 84(1–3):79-91, 1998. URL: http://dx.doi.org/10.1016/S0166-218X(98)00006-7.
  9. Ran Duan and Seth Pettie. Linear-time approximation for maximum weight matching. Journal of the ACM, 61(1):1:1-1:23, 2014. URL: http://dx.doi.org/10.1145/2529989.
  10. Fedor V. Fomin, Daniel Lokshtanov, Michal Pilipczuk, Saket Saurabh, and Marcin Wrochna. Fully polynomial-time parameterized computations for graphs and matrices of low treewidth. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '17), pages 1419-1432. SIAM, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.92.
  11. Harold N. Gabow and Robert Endre Tarjan. A linear-time algorithm for a special case of disjoint set union. Journal of Computer and System Sciences, 30(2):209-221, 1985. URL: http://dx.doi.org/10.1016/0022-0000(85)90014-5.
  12. Harold N. Gabow and Robert Endre Tarjan. Faster scaling algorithms for general graph-matching problems. Journal of the ACM, 38(4):815-853, 1991. URL: http://dx.doi.org/10.1145/115234.115366.
  13. Archontia C. Giannopoulou, George B. Mertzios, and Rolf Niedermeier. Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs. Theoretical Computer Science, 2017. Available online. URL: http://dx.doi.org/10.1016/j.tcs.2017.05.017.
  14. Jiong Guo, Falk Hüffner, and Rolf Niedermeier. A structural view on parameterizing problems: Distance from triviality. In Proceedings of the 1st International Workshop on Parameterized and Exact Computation (IWPEC '04), volume 3162 of LNCS, pages 162-173. Springer, 2004. URL: http://dx.doi.org/10.1007/978-3-540-28639-4_15.
  15. Manoj Gupta and Richard Peng. Fully dynamic (1+ e)-approximate matchings. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS '13), pages 548-557. IEEE, 2013. URL: http://dx.doi.org/10.1109/FOCS.2013.65.
  16. John E. Hopcroft and Richard M. Karp. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 2(4):225-231, 1973. URL: http://dx.doi.org/10.1137/0202019.
  17. Richard M. Karp and Michael Sipser. Maximum matchings in sparse random graphs. In Proceedings of the 22nd Annual IEEE Symposium on Foundations of Computer Science (FOCS '81), pages 364-375. IEEE, 1981. URL: http://dx.doi.org/10.1109/SFCS.1981.21.
  18. Christian Komusiewicz and Rolf Niedermeier. New races in parameterized algorithmics. In Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science (MFCS '12), volume 7464 of LNCS, pages 19-30. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-32589-2_2.
  19. George B. Mertzios, André Nichterlein, and Rolf Niedermeier. Linear-time algorithm for maximum-cardinality matching on cocomparability graphs. CoRR, abs/1703.05598, 2017. Google Scholar
  20. Silvio Micali and Vijay V. Vazirani. 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), pages 17-27. IEEE, 1980. URL: http://dx.doi.org/10.1109/SFCS.1980.12.
  21. Marcin Mucha and Piotr Sankowski. Maximum matchings via Gaussian elimination. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS '04), pages 248-255. IEEE, 2004. URL: http://dx.doi.org/10.1109/FOCS.2004.40.
  22. Steven S. Skiena. The Algorithm Design Manual. Springer, 2010. Google Scholar
  23. G. Steiner and J. S. Yeomans. A linear time algorithm for maximum matchings in convex bipartite graphs. Comput. Math. Appl., 31:91-96, 1996. URL: http://dx.doi.org/10.1016/0898-1221(96)00079-X.
  24. Ryan Williams, Carla P. Gomes, and Bart Selman. Backdoors to typical case complexity. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI '03), pages 1173-1178. Morgan Kaufmann, 2003. Google Scholar
  25. Raphael Yuster. Maximum matching in regular and almost regular graphs. Algorithmica, 66(1):87-92, 2013. URL: http://dx.doi.org/10.1007/s00453-012-9625-7.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact