Almost Exact Matchings
Almost Exact Matchings
复制标题
几乎完全匹配
作者：
R. Yuster
在精确匹配问题中，我们给出一个图G，它的一些边是红色的，还有一个正整数k。我们的目标是确定G是否有一个完美匹配，它的k条边是红色的。更一般地说，如果G的匹配数为m=m(G)，则目标是找到具有m条边的匹配，其中恰好有k条边是红色的，或者确定不存在这样的匹配。这个问题是为数不多的具有高效随机算法的问题之一（事实上，这个问题是在RNC中），但是没有已知的多项式时间确定性算法。我们的第一个结果表明，在某种意义上，这个问题是最接近P的。我们给出了一个多项式时间确定性算法，该算法要么正确地决定没有最大匹配具有恰好k条红边，要么显示具有恰好k条红边的m(G)−1条边的匹配。因此，加性误差为1。我们还提出了一种有效的算法来解决图族中的精确匹配问题，该问题已知是可处理的。我们展示了如何在0 （n3.19）的最坏情况时间内计算K3,3-minor自由图（包括所有平面图以及许多其他图）中的精确完美匹配的数量。我们的算法还可以在O（n2.19）时间内统计K3,3-minor free图的完美匹配个数。
In the exact matching problem we are given a graph G, some of whose edges are colored red, and a positive integer k. The goal is to determine if G has a perfect matching, exactly k edges of which are red. More generally if the matching number of G is m=m(G), the goal is to find a matching with m edges, exactly k edges of which are red, or determine that no such matching exists. This problem is one of the few remaining problems that have efficient randomized algorithms (in fact, this problem is in RNC), but for which no polynomial time deterministic algorithm is known.Our first result shows that, in a sense, this problem is as close to being in P as one can get. We give a polynomial time deterministic algorithm that either correctly decides that no maximum matching has exactly k red edges, or exhibits a matching with m(G)−1 edges having exactly k red edges. Hence, the additive error is one.We also present an efficient algorithm for the exact matching problem in families of graphs for which this problem is known to be tractable. We show how to count the number of exact perfect matchings in K3,3-minor free graphs (these include all planar graphs as well as many others) in O(n3.19) worst case time. Our algorithm can also count the number of perfect matchings in K3,3-minor free graphs in O(n2.19) time.