2022/09/17 by Nicolas El Maalouly, Maalouly, Nicolas El, Lasse Wulf +1 · 2 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2209.09661
openalex publication_date 2022/09/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The aim of this note is to provide a reduction of the Exact Matching problem to the Top-k Perfect Matching Problem. Together with earlier work by El Maalouly, this shows that the two problems are polynomial-time equivalent. The Exact Matching Problem is a well-known 40 years old problem for which a randomized, but no deterministic poly-time algorithm has been discovered. The Top-k Perfect Matching Problem is the problem of finding a perfect matching which maximizes the total weight of the k heaviest edges contained in it.