论文标题
确切的匹配：算法和相关问题
Exact Matching: Algorithms and Related Problems
论文作者
论文摘要
1982年，Papadimitriou和Yannakakis引入了确切的匹配（EM）问题，其中给定的边缘颜色图，红色和蓝色以及整数$ k $，目标是确定该图是否包含与$ K $ Red Edges完全匹配的完美匹配。尽管他们猜想它是$ \ textbf {np} $ - 完成，但在Mulmuley等人的开创性工作中被证明可以在随机多项式时间内解决后不久，将其放在复杂性类别$ \ textbf {rp {rp} $中。从那时起，所有寻找EM确定性算法的尝试都失败了，因此将其作为$ \ textbf {rp} $中的少数自然组合问题之一，但不知道在$ \ textbf {p} $中包含，并使其成为测试假设$ \ textbf fextbf} $ \ textbf {rp} $ fextbf {p} $ \ ppff textbf {p} $} $ \ rp} $ {rp} = {rp}}即使在非常限制的图形类别上，尽管问题被引用的数量证明了这一点，但仍缺乏进度。 在本文中，我们旨在通过研究一个新的优化问题，我们称其为TOP-K Perfect匹配（TKPM），从而获得更多的洞察力，我们表明这与EM相当。由于是一个优化问题，近似tkpm更自然，因此我们为其提供近似算法。某些近似算法依赖于双方图上的EM放松，在这些图形上，输出必须是完美的匹配，其中许多红色边缘与$ k $不同，最多是$ k/2 $，这是独立的利益，并且具有完全匹配（EWPM）的精确权重匹配（EWPM）问题。我们还考虑参数化算法，并表明可以在$ k $和图形的独立性数字中以fpt时间求解TKPM。该结果再次依赖于为EM开发的新工具，这些工具也具有独立的兴趣。
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 $\textbf{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 $\textbf{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 $\textbf{RP}$ but not known to be contained in $\textbf{P}$, and making it an interesting instance for testing the hypothesis $\textbf{RP}=\textbf{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.
