论文标题
在有限的独立编号的图中确切匹配
Exact Matching in Graphs of Bounded Independence Number
论文作者
论文摘要
在确切的匹配问题（EM）中，我们获得了一个配备了固定的边缘着色的图表，并具有两种颜色（红色和蓝色）以及一个正整数$ k $。然后，任务是确定给定图是否包含一个完美的匹配恰好$ k $，其边缘具有红色。 EM概括了几种重要的算法问题，例如完美匹配和限制最小重量跨越树问题。 Papadimitriou和Yannakakis在1982年引入该问题时，将EM猜想为$ \ textbf {np} $ - 完成。但是，后来，Mulmuley等人〜提出了EM的随机多项式时间算法，该算法将EM放入$ \ textbf {rp} $中。考虑到这一点是为了决定是否$ \ textbf {rp} = \ textbf {p} $代表复杂性理论中的一个很大的开放挑战，这使得em不太可能成为$ \ textbf {np} $完整，实际上表明了确定性的多努力时间algorithm的可能性。 EM仍然是$ \ textbf {rp} $中为数不多的自然组合问题之一，这些问题不知道在$ \ textbf {p} $中包含，这使其成为测试假设$ \ textbf {rp} = \ textbf {p textbf {p} $的有趣实例。尽管EM是众所周知的，但在过去的40年中，尝试设计确定性多项式算法的尝试仍然是虚幻的，即使对于非常限制的输入图，也缺乏进步。在本文中，我们最终通过证明可以在确定性的多项式时间内求解EM的前沿，以求解界数独立性数的输入图，以及对界有两部分独立性数字的两部分输入图。这概括了以前的（两分）图的正面结果，这是密集图上EM的唯一已知结果。
In the Exact Matching Problem (EM), we are given a graph equipped with a fixed coloring of its edges with two colors (red and blue), as well as a positive integer $k$. The task is then to decide whether the given graph contains a perfect matching exactly $k$ of whose edges have color red. EM generalizes several important algorithmic problems such as perfect matching and restricted minimum weight spanning tree problems. When introducing the problem in 1982, Papadimitriou and Yannakakis conjectured EM to be $\textbf{NP}$-complete. Later however, Mulmuley et al.~presented a randomized polynomial time algorithm for EM, which puts EM in $\textbf{RP}$. Given that to decide whether or not $\textbf{RP}=\textbf{P}$ represents a big open challenge in complexity theory, this makes it unlikely for EM to be $\textbf{NP}$-complete, and in fact indicates the possibility of a deterministic polynomial time algorithm. EM remains one of the few natural combinatorial problems in $\textbf{RP}$ which are not known to be contained in $\textbf{P}$, making it an interesting instance for testing the hypothesis $\textbf{RP}=\textbf{P}$. Despite EM being quite well-known, attempts to devise deterministic polynomial algorithms have remained illusive during the last 40 years and progress has been lacking even for very restrictive classes of input graphs. In this paper we finally push the frontier of positive results forward by proving that EM can be solved in deterministic polynomial time for input graphs of bounded independence number, and for bipartite input graphs of bounded bipartite independence number. This generalizes previous positive results for complete (bipartite) graphs which were the only known results for EM on dense graphs.
