Document Open Access Logo

Exact Matching: Algorithms and Related Problems

Author Nicolas El Maalouly

PDF
Thumbnail PDF

File

LIPIcs.STACS.2023.29.pdf
  • Filesize: 0.82 MB
  • 17 pages

Document Identifiers

Author Details

Nicolas El Maalouly
  • Department of Computer Science, ETH Zürich, Switzerland

Acknowledgements

I want to thank Ola Svensson for introducing me to the Exact Matching problem, for defining the Top-k Perfect Matching problem and for helpful discussions and feedback.

Cite AsGet BibTex

Nicolas El Maalouly. Exact Matching: Algorithms and Related Problems. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.STACS.2023.29

Abstract

In 1982, Papadimitriou and Yannakakis introduced the Exact Matching (EM) problem where given an edge colored graph, with colors red and blue, and an integer k, the goal is to decide whether or not the graph contains a perfect matching with exactly k red edges. Although they conjectured it to be NP-complete, soon after it was shown to be solvable in randomized polynomial time in the seminal work of Mulmuley et al., placing it in the complexity class RP. Since then, all attempts at finding a deterministic algorithm for EM have failed, thus leaving it as one of the few natural combinatorial problems in RP but not known to be contained in P, and making it an interesting instance for testing the hypothesis RP = P. Progress has been lacking even on very restrictive classes of graphs despite the problem being quite well known as evidenced by the number of works citing it. In this paper we aim to gain more insight into EM by studying a new optimization problem we call Top-k Perfect Matching (TkPM) which we show to be polynomially equivalent to EM. By virtue of being an optimization problem, it is more natural to approximate TkPM so we provide approximation algorithms for it. Some of the approximation algorithms rely on a relaxation of EM on bipartite graphs where the output is required to be a perfect matching with a number of red edges differing from k by at most k/2, which is of independent interest and generalizes to the Exact Weight Perfect Matching (EWPM) problem. We also consider parameterized algorithms and show that TkPM can be solved in FPT time parameterized by k and the independence number of the graph. This result again relies on new tools developed for EM which are also of independent interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Perfect Matching
  • Exact Matching
  • Approximation algorithms
  • Independence number
  • Parameterized complexity

Metrics

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

Related Versions

References

  1. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. Journal of the ACM (JACM), 42(4):844-856, 1995. Google Scholar
  2. Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, and Jacobo Torán. Solving linear equations parameterized by hamming weight. Algorithmica, 75(2):322-338, 2016. Google Scholar
  3. Richard Bellman. On a routing problem. Quarterly of applied mathematics, 16(1):87-90, 1958. Google Scholar
  4. André Berger, Vincenzo Bonifaci, Fabrizio Grandoni, and Guido Schäfer. Budgeted matching and budgeted matroid intersection via the gasoline puzzle. Mathematical Programming, 128(1):355-372, 2011. Google Scholar
  5. Jacek Błażewicz, Piotr Formanowicz, Marta Kasprzak, Petra Schuurman, and Gerhard J Woeginger. A polynomial time equivalence between DNA sequencing and the exact perfect matching problem. Discrete Optimization, 4(2):154-162, 2007. Google Scholar
  6. Daniel P Bovet and Pierluigi Crescenzi. Introduction to the Theory of Complexity. Prentice Hall International (UK) Ltd., GBR, 1994. Google Scholar
  7. Paolo M. Camerini, Giulia Galbiati, and Francesco Maffioli. Random pseudo-polynomial algorithms for exact matroid problems. Journal of Algorithms, 13(2):258-273, 1992. Google Scholar
  8. Deeparnab Chakrabarty and Chaitanya Swamy. Approximation algorithms for minimum norm and ordered optimization problems. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 126-137, 2019. Google Scholar
  9. Radu Curticapean and Mingji Xia. Parameterizing the permanent: Hardness for K_8-minor-free graphs. arXiv preprint, 2021. URL: http://arxiv.org/abs/2108.12879.
  10. Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms, volume 5. Springer, 2015. Google Scholar
  11. Jack Edmonds. Maximum matching and a polyhedron with 0, 1-vertices. Journal of research of the National Bureau of Standards B, 69(125-130):55-56, 1965. Google Scholar
  12. Nicolas El Maalouly. Exact matching: Algorithms and related problems. arXiv preprint, 2022. URL: http://arxiv.org/abs/2203.13899.
  13. Nicolas El Maalouly and Raphael Steiner. Exact Matching in Graphs of Bounded Independence Number. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), volume 241 of Leibniz International Proceedings in Informatics (LIPIcs), pages 46:1-46:14, 2022. Google Scholar
  14. Nicolas El Maalouly and Lasse Wulf. Exact matching and the top-k perfect matching problem. arXiv preprint, 2022. URL: http://arxiv.org/abs/2209.09661.
  15. Dennis Fischer, Tim A Hartmann, Stefan Lendl, and Gerhard J Woeginger. An investigation of the recoverable robust assignment problem. arXiv preprint, 2020. URL: http://arxiv.org/abs/2010.11456.
  16. Anna Galluccio and Martin Loebl. On the theory of Pfaffian orientations. I. Perfect matchings and permanents. Electronic Journal of Combinatorics, 6:R6, 1999. Google Scholar
  17. Hans-Florian Geerdes and Jácint Szabó. A unified proof for karzanov’s exact matching theorem. Technical Report QP-2011-02, Egerváry Research Group, Budapest, 2011. egres.elte.hu. Google Scholar
  18. Christopher David Godsil. Algebraic combinatorics. Routledge, 2017. Google Scholar
  19. Fabrizio Grandoni and Rico Zenklusen. Optimization with more than one budget. arXiv preprint, 2010. URL: http://arxiv.org/abs/1002.2147.
  20. Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, and Thomas Thierauf. Planarizing gadgets for perfect matching do not exist. In International Symposium on Mathematical Foundations of Computer Science, pages 478-490. Springer, 2012. Google Scholar
  21. Rohit Gurjar, Arpita Korwar, Jochen Messner, and Thomas Thierauf. Exact perfect matching in complete graphs. ACM Transactions on Computation Theory (TOCT), 9(2):1-20, 2017. Google Scholar
  22. Valentine Kabanets and Russell Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. computational complexity, 13(1-2):1-46, 2004. Google Scholar
  23. AV Karzanov. Maximum matching of given weight in complete and complete bipartite graphs. Cybernetics, 23(1):8-13, 1987. Google Scholar
  24. Monaldo Mastrolilli and Georgios Stamoulis. Constrained matching problems in bipartite graphs. In International Symposium on Combinatorial Optimization, pages 344-355. Springer, 2012. Google Scholar
  25. Monaldo Mastrolilli and Georgios Stamoulis. Bi-criteria and approximation algorithms for restricted matchings. Theoretical Computer Science, 540:115-132, 2014. Google Scholar
  26. Ketan Mulmuley, Umesh V Vazirani, and Vijay V Vazirani. Matching is as easy as matrix inversion. Combinatorica, 7(1):105-113, 1987. Google Scholar
  27. Christos H Papadimitriou and Mihalis Yannakakis. The complexity of restricted spanning tree problems. Journal of the ACM (JACM), 29(2):285-309, 1982. Google Scholar
  28. Irena Rusu. Maximum weight edge-constrained matchings. Discrete applied mathematics, 156(5):662-672, 2008. Google Scholar
  29. Georgios Stamoulis. Approximation algorithms for bounded color matchings via convex decompositions. In International Symposium on Mathematical Foundations of Computer Science, pages 625-636. Springer, 2014. Google Scholar
  30. Ola Svensson and Jakub Tarnawski. The matching problem in general graphs is in quasi-nc. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 696-707. Ieee, 2017. Google Scholar
  31. Tongnyoul Yi, Katta G Murty, and Cosimo Spera. Matchings in colored bipartite networks. Discrete Applied Mathematics, 121(1-3):261-277, 2002. Google Scholar
  32. Raphael Yuster. Almost exact matchings. Algorithmica, 63(1):39-50, 2012. 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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact