2026-07-24T05:46:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19743 2024-03-11T06:37:04Z ddc:004 open_access

On the Exact Matching Problem in Dense Graphs El Maalouly, Nicolas Haslebacher, Sebastian Wulf, Lasse Exact Matching Perfect Matching Red-Blue Matching Bounded Color Matching Local Search Derandomization In the Exact Matching problem, we are given a graph whose edges are colored red or blue and the task is to decide for a given integer k, if there is a perfect matching with exactly k red edges. Since 1987 it is known that the Exact Matching Problem can be solved in randomized polynomial time. Despite numerous efforts, it is still not known today whether a deterministic polynomial-time algorithm exists as well. In this paper, we make substantial progress by solving the problem for a multitude of different classes of dense graphs. We solve the Exact Matching problem in deterministic polynomial time for complete r-partite graphs, for unit interval graphs, for bipartite unit interval graphs, for graphs of bounded neighborhood diversity, for chain graphs, and for graphs without a complete bipartite t-hole. We solve the problem in quasi-polynomial time for Erdős-Rényi random graphs G(n, 1/2). We also reprove an earlier result for bounded independence number/bipartite independence number. We use two main tools to obtain these results: A local search algorithm as well as a generalization of an earlier result by Karzanov. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nicolas El Maalouly and Sebastian Haslebacher and Lasse Wulf 2024 Is Part Of LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2024.33 urn:nbn:de:0030-drops-197437 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.33 eng https://creativecommons.org/licenses/by/4.0/legalcode