License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2023.29
URN: urn:nbn:de:0030-drops-176811
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17681/
Go to the corresponding LIPIcs Volume Portal

El Maalouly, Nicolas

Exact Matching: Algorithms and Related Problems

pdf-format:
LIPIcs-STACS-2023-29.pdf (0.8 MB)

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.

BibTeX - Entry

@InProceedings{elmaalouly:LIPIcs.STACS.2023.29,
  author =	{El Maalouly, Nicolas},
  title =	{{Exact Matching: Algorithms and Related Problems}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{29:1--29:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17681},
  URN =		{urn:nbn:de:0030-drops-176811},
  doi =		{10.4230/LIPIcs.STACS.2023.29},
  annote =	{Keywords: Perfect Matching, Exact Matching, Approximation algorithms, Independence number, Parameterized complexity}
}

Keywords: Perfect Matching, Exact Matching, Approximation algorithms, Independence number, Parameterized complexity
Collection: 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Issue Date: 2023
Date of publication: 03.03.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI