TY - GEN
T1 - On the Exact Matching Problem in Dense Graphs
AU - Maalouly, Nicolas El
AU - Haslebacher, Sebastian
AU - Wulf, Lasse
N1 - Publisher Copyright:
© Nicolas El Maalouly, Sebastian Haslebacher, and Lasse Wulf; licensed under Creative Commons License CC-BY 4.0.
PY - 2024/3
Y1 - 2024/3
N2 - 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.
AB - 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.
KW - Bounded Color Matching
KW - Derandomization
KW - Exact Matching
KW - Local Search
KW - Perfect Matching
KW - Red-Blue Matching
UR - http://www.scopus.com/inward/record.url?scp=85187794259&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.STACS.2024.33
DO - 10.4230/LIPIcs.STACS.2024.33
M3 - Conference paper
AN - SCOPUS:85187794259
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024
A2 - Beyersdorff, Olaf
A2 - Kante, Mamadou Moustapha
A2 - Kupferman, Orna
A2 - Lokshtanov, Daniel
PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik
T2 - 41st International Symposium on Theoretical Aspects of Computer Science
Y2 - 12 March 2024 through 14 March 2024
ER -