Document Open Access Logo

Diverse Pairs of Matchings

Authors Fedor V. Fomin , Petr A. Golovach , Lars Jaffke , Geevarghese Philip , Danil Sagunov

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2020.26.pdf
  • Filesize: 0.55 MB
  • 12 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
  • Mathematics of computing → Matchings and factors
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Graph algorithms analysis
Keywords
  • Matching
  • Solution Diversity
  • Fixed-Parameter Tractability

Metrics

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

Abstract

We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matchings problems which given a graph G and an integer k, ask whether G has two (maximum/perfect) matchings whose symmetric difference is at least k. Diverse Pair of Matchings (asking for two not necessarily maximum or perfect matchings) is NP-complete on general graphs if k is part of the input, and we consider two restricted variants. First, we show that on bipartite graphs, the problem is polynomial-time solvable, and second we show that Diverse Pair of Maximum Matchings is FPT parameterized by k. We round off the work by showing that Diverse Pair of Matchings has a kernel on 𝒪(k²) vertices.

Cite As Get BibTex

Fedor V. Fomin, Petr A. Golovach, Lars Jaffke, Geevarghese Philip, and Danil Sagunov. Diverse Pairs of Matchings. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 26:1-26:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ISAAC.2020.26

Author Details

Fedor V. Fomin
  • University of Bergen, Norway
Petr A. Golovach
  • University of Bergen, Norway
Lars Jaffke
  • University of Bergen, Norway
Geevarghese Philip
  • Chennai Mathematical Institute, India
  • UMI ReLaX, Chennai, India
Danil Sagunov
  • St. Petersburg Department of V. A. Steklov Institute of Mathematics, Russia
  • JetBrains Research, St. Petersburg, Russia

Funding

  • Fomin, Fedor V.: Supported by the Research Council of Norway via the project "MULTIVAL", grant number 263317.
  • Golovach, Petr A.: Supported by the Research Council of Norway via the project "MULTIVAL", grant number 263317.
  • Jaffke, Lars: Supported by the Trond Mohn Foundation (TMS).
  • Philip, Geevarghese: Supported by the European Research Council grant number 819416 and the Research Council of Norway via grants MULTIVAL and CLASSIS.

Acknowledgements

We thank Günter Rote for pointing out to us that, given a maximum matching M, we can find a maximum matching M' such that |M △ M'| is maximum in polynomial time by the reduction to the Minimum Cost Maximum Matching problem.

References

  1. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844-856, 1995. URL: https://doi.org/10.1145/210332.210337.
  2. Julien Baste, Michael R. Fellows, Lars Jaffke, Tomáš Masařík, Mateus de Oliveira Oliveira, Geevarghese Philip, and Frances A. Rosamond. Diversity of solutions: An exploration through the lens of fixed-parameter tractability theory. In IJCAI 2020, pages 1119-1125, 2020. Google Scholar
  3. Julien Baste, Lars Jaffke, Tomáš Masařík, Geevarghese Philip, and Günter Rote. FPT algorithms for diverse collections of hitting sets. Algorithms, 12(12):254, 2019. Google Scholar
  4. Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia. Handbook of computational social choice. Cambridge University Press, 2016. Google Scholar
  5. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  6. Reinhard Diestel. Graph Theory. Springer, 2005. Google Scholar
  7. Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Springer-Verlag, New York, 1999. Google Scholar
  8. Jack Edmonds. Paths, trees, and flowers. Can. J. Math., 17(3):449-467, 1965. Google Scholar
  9. Uriel Feige, Eran Ofek, and Udi Wieder. Approximating maximum edge coloring in multigraphs. In APPROX 2002, pages 108-121. Springer, 2002. Google Scholar
  10. Michael R. Fellows. The Diverse X paradigm. manuscript, 2018. Google Scholar
  11. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization. Theory of Parameterized Preprocessing. Cambridge University Press, 2018. Google Scholar
  12. Harold N. Gabow and Robert Endre Tarjan. Faster scaling algorithms for general graph-matching problems. J. ACM, 38(4):815-853, 1991. Google Scholar
  13. Philip Hall. On representatives of subsets. J. London Math. Soc., 10:26-30, 1935. Google Scholar
  14. Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, and Yota Otachi. Finding diverse trees, paths, and more. CoRR, abs/2009.03687, 2020. URL: http://arxiv.org/abs/2009.03687.
  15. Ian Holyer. The NP-completeness of edge-coloring. SIAM Journal on Computing, 10(4):718-720, 1981. Google Scholar
  16. John E. Hopcroft and Richard M. Karp. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 2:225-231, 1973. Google Scholar
  17. Marcin Jakub Kamiński and Lukasz Kowalik. Beyond the Vizing’s bound for at most seven colors. SIAM Journal on Discrete Mathematics, 28(3):1334-1362, 2014. Google Scholar
  18. A. V. Karzanov. The problem of finding the maximal flow in a network by the method of preflows. Dokl. Akad. Nauk SSSR, 215:49-52, 1974. Google Scholar
  19. Dénes Kőnig. Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Math. Ann., 77(4):453-465, 1916. Google Scholar
  20. László Lovász. On determinants, matchings, and random algorithms. In Fundamentals of Computation Theory, pages 565-574. Akademie Verlag, 1979. Google Scholar
  21. László Lovász and Michael D. Plummer. Matching Theory. AMS, 2009. Google Scholar
  22. Aleksander Mądry. Navigating central path with electrical flows: From flows to matchings, and back. In FOCS 2013, pages 253-262. IEEE Computer Society, 2013. Google Scholar
  23. Marcin Mucha and Piotr Sankowski. Maximum matchings via Gaussian elimination. In FOCS 2004, pages 248-255. IEEE Computer Society, 2004. Google Scholar
  24. Moni Naor, Leonard J. Schulman, and Aravind Srinivasan. Splitters and near-optimal derandomization. In FOCS 1995, pages 182-191, 1995. Google Scholar
  25. Thomas Olsson, Jukka Huhtamäki, and Hannu Kärkkäinen. Directions for professional social matching systems. Commun. ACM, 63(2):60-69, 2020. Google Scholar
  26. Gregg O'Malley. Algorithmic aspects of stable matching problems. PhD thesis, University of Glasgow, 2007. Google Scholar
  27. Michael O. Rabin and Vijay V. Vazirani. Maximum matchings in general graphs through randomization. J. Algorithms, 10(4):557-567, 1989. Google Scholar
  28. Alexander Schrijver. Combinatorial Optimization. Polyhedra and Efficiency. Vol. A. Springer-Verlag, Berlin, 2003. Google Scholar
  29. Jukka Suomela. Complexity of two perfect matchings with minimum shared edges? Theoretical Computer Science Stack Exchange, 2010. https://cstheory.stackexchange.com/q/1291 (version: 2010-09-14).
  30. William Thomas Tutte. A short proof of the factor theorem for finite graphs. Can. J. Math., 6:347-352, 1954. Google Scholar
  31. Vijay V. Vazirani. A proof of the MV matching algorithm, 2014. Google Scholar
  32. Vadim G. Vizing. On an estimate of the chromatic class of a p-graph. Discret Analiz, 3:25-30, 1964. Google Scholar
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact