ACM通信

研究突出了

二部完美匹配的确定性并行算法

作者:Stephen Fenner, Rohit Gurjar, Thomas Thierauf
ACM通讯，2019年3月，第62卷第3期，109-115页
10.1145 / 3306208
评论

计算理论的一个基本探索是理解随机性的力量。我们不知道是否每个有效随机算法的问题也有一个不使用随机性的问题。这一主题下广泛研究的问题之一是完美匹配问题。完美匹配问题是基于Mulmuley、Vazirani和Vazirani的隔离引理的随机并行(NC)算法。这个算法是否可以被随机化是一个长期悬而未决的问题。在这篇文章中，我们给出了二部图中完美匹配的隔离引理的一个几乎完全解随机化。这给我们提供了一个求解二部完美匹配问题的确定性并行(准nc)算法。

隔离引理的去随机化意味着我们确定地构造一个权分配，使最小权完美匹配是唯一的。我们提出了三种不同的方法来构建这种结构，但其主要思想是相同的。

回到顶部

1.简介

图中的完美匹配是边的子集，每个顶点都有一条边与这个子集(图1)．完美匹配问题PM询问给定图是否包含完美匹配。该问题在算法和复杂度的研究中发挥了重要作用。Edmonds给出了该问题的第一个多项式时间算法，⁷事实上，这促使他提出用多项式时间来衡量高效计算。

图1。图中粗体的边表示完美匹配。

完美匹配也是首先从并行算法的角度来研究的问题之一。并行算法是一种允许使用多项式多个处理器并行运行的算法。为了使并行算法有效，我们要求它的运行时间要比多项式算法小得多。特别地，将复杂类NC定义为可以由多处理器并行计算机在多对数时间内解决的问题集。

Lovasz¹⁹给出了一种高效的随机并行匹配算法，并将其归入复杂度类RNC (randomnc)。他的并行算法的本质是将匹配问题随机化简为行列式计算。行列式的计算反过来又简化为矩阵乘法(参见⁴)，众所周知，它具有高效的并行算法。

计算理论的中心主题之一是理解随机性的力量，也就是说，是否一个有效的随机算法的所有问题都有一个确定性问题。在这一主题下，匹配问题得到了广泛的研究。并行匹配算法是否需要随机性，即问题是否在NC中，这是一个长期悬而未决的问题。

如果存在的话，还可以要求一个并行算法来构造图中的完美匹配(Search-PM)。注意，对于匹配问题有一个标准的搜索到决策简化，但它不能并行工作。卡普、厄普法尔和威格森¹⁸然后是mulmulley, Vazirani，和Vazirani²¹给出了Search-PM的RNC算法。后者引入了著名的隔离引理，并利用它解决了RNC中的Search-PM问题。他们给图的边赋值，称为图的权值隔离G如果有独特的最小权重完美匹配G。在这里，一个完美匹配的权值就是其中所有边的权值之和。给定一个多项式有界整数权值的隔离权值，它们可以在中找到最小权值完美匹配G在NC中(同样通过行列式计算)。

请注意，如果我们允许指数级大的权重，那么构造一个独立的权重分配就很简单:分配权重2^我到我第1条边我米,在那里米是边的数量。事实上，这确保了每一个完美匹配的不同权重。然而，挑战是找到一个具有多项式有界权值的隔离权值分配。这就是隔离引理的作用:它指出，如果每条边从多项式有界的范围分配一个随机权重，那么这样的权重分配是高概率隔离的。

注意，由于图中可以有指数级的完美匹配，在多项式有界权值分配下肯定会有很多碰撞，也就是说，许多完美匹配会得到相同的权值。隔离引理的美妙之处在于，对于最小权值，会有一个具有高概率的唯一完美匹配。

引理mulmulley, Vazirani和Vazirani²¹)．让克（V E）是一个图、|E| =米,和w{1,2，…，公里｝^E是一个均匀随机的权值分配到它的边上，对于某个k2.那么w是与至少的概率隔离的1 1 /k。

证明。让e成为图中的一条边。我们首先给出两个最小权重完美匹配的概率的上界，其中一个包含e其他不包含e。对于这个，我们说其他每条边的权值e已经固定。让W为避免任何完美匹配的最小权重e,让W' +w（e)为包含的任何完美匹配的最小权重e。

现在，这两个最小权值相等的概率是多少?自W和W已经被其他边固定住了，而且w（e)在1和之间均匀随机选择公里，

在联盟的约束下，

现在，为了完成证明，观察当且仅当不存在具有上述性质的边时，存在唯一的最小权值完美匹配。

得到完美匹配问题的确定性并行(NC)算法的一种方法是对该引理进行去随机化。也就是说,确定性在NC中构造一个多项式有界的隔离权值分配。这仍然是一个具有挑战性的悬而未决的问题。

孤立引理的去随机化在一些特殊的图类中已经得到了应用，例如平面二部图，^6，26强烈的弦的图表,⁵以及只有少量完美匹配的图。^1，14在这里，我们给出了二部图的隔离引理的一个几乎完全的解随机化。在完美匹配的研究中，二部图的类很自然地出现了。如果一个图的顶点集被划分为两个部分，其中每条边将一个顶点从一个部分连接到另一个顶点，那么这个图就是二部图(图1中的图就是二部图)。因此，二部图中的完美匹配将一个部分的每个顶点精确地匹配到另一个部分的一个顶点。

在第3节中，我们构造了拟多项式大(n^O(日志n）)权重,n是图中顶点的数量。注意，这比我们理想中的多项式有界权值稍微差一些。因此，我们没有得到NC算法。相反，我们得到对于二部图，问题PM和Search-PM是准nc的²。也就是说，问题可以在O(日志²n)时间使用n^O(日志n）并行处理器。更详细的阐述在会议版的文章。¹⁰

定理1.2。对由两部分构成的图下午,和Search-PM在准数控²。

1.1.隔离技术

我们隔离方法的核心是循环消除技术。很容易看到，如果我们取两个完美匹配的并集，我们会得到一组不相交的环和单边(参见图2)．这些循环中的每一个都是偶数长度，并且有两条完美匹配的边交替出现。因此，周期在分离完美匹配方面发挥着重要作用。给定边缘的权值，让我们定义循环偶数周期C为奇数条边的集合和偶数条边的集合按循环顺序的权值之差C。显然，如果两个完美匹配并集中的所有循环都为零，那么这两个完美匹配集将具有相同的权值。事实证明，当考虑的两个完美匹配的权重最小时，反过来也是正确的。⁶这个观察结果是我们循环消除技术的起点。

图2。两个完美的搭配，分别是红边和蓝边。它们的结合形成了一组不相交的环和边。

在二部图的情况下，这个观察结果可以进一步推广。我们证明了对于任何权重分配w在二部图的边缘上，如果我们考虑所有最小权值完美匹配的并集，那么它只有那些循环为零的环(引理2.1)。这意味着如果我们设计重量w这样一个特定的循环C有一个非零循环,然后C是否出现在最小权值完美匹配的并集中，即至少有一条边在C不参与任何最小权重完美匹配。这就是我们消除循环的方法。

如果我们用这种方法消除所有的环，我们将得到一个唯一的最小权完美匹配，因为如果有两个最小权完美匹配，它们的并集将包含一个环。然而，事实证明，图中有太多的循环，在保持边缘权值小的同时，不可能同时保证所有循环的非零循环(证明在¹⁷)．相反，可以实现的是任何非零循环多项式大使用著名的散列技术的一组循环。简而言之，我们可以一次消除任何想要的少量循环集。有了这个工具，我们想要消除所有的周期，它们的数量可以在少量的轮数中呈指数增长。

我们提出了三种不同的实现方法。前两个问题已经在我们文章的不同版本中出现过。¹⁰第三种以前从未出现过。

1. 在第一种方法中我第一轮，我们消除所有长度不超过2的循环^我＋1。因此，我们消除了log中的所有循环n轮。每一轮都是有效的，因为如果一个图最多没有任何周期长度，则循环的个数达到2多项式是有界的。^25，23
2. 在第二种方法中，首先我们消除所有长度不超过4 log的循环n。这样的循环数的界是在的准多项式n。阿隆，霍利和利尼奥尔²已经证明了任何不包含任何长度为4log的循环的图n平均度必须不超过2.5，因此必须至少有一个恒定分数的节点的度为2或更少。从结果图中，我们移除所有的1度节点，并逐个收缩2度节点(确定两个相邻节点)，直到没有2度节点剩余。这将在图中创建新的小循环。然后我们重复消除长度不超过4 log的循环的过程n从新的图表。在每一轮中，节点的数量减少一个常数分数。因此,后0(日志n)轮，我们消除所有节点，因此，所有周期。
3. 在第三种方法中，我们不考虑循环的长度，而是尽可能多地选取不相交边的循环并将其消去。请注意，边不相交确保我们将消除至少与循环一样多的边。鄂尔多斯和Posa⁹证明了任何带有米边缘和n节点包含edge-disjoint周期。仔细的论证表明，在0(日志²n)圆，我们去掉了足够多的边，这样就不会留下圆了。

正如我们稍后将看到的，第一种方法比其他两种方法更有效。我们仍然认为看到实现隔离的不同方法是很有趣的，因为它们可能会引出用多项式有界权获得隔离或在其他设置中获得隔离的更好想法。另一个有趣的点是，我们的第二种方法被用于设计pseudo-deterministic二部匹配的RNC算法。¹³

我们关于消环的关键技术结果(引理2.1)基于线性规划(LP)对偶得到了证明。在下一节中，我们描述了一个二部完美匹配的LP公式及其对偶，然后用它来证明我们的结果。最后，在第3节中，我们正式地描述了权重的构造和消除所有循环的三种方法。

回到顶部

2.通过非零循环消除循环

在本节中，我们将正式描述实现循环消除的主要技术工具。让我们先给循环循环一个正式的定义。对于权重分配w在图的边缘上G,循环保监会_w（C)为偶数周期C= (v₁，v₂，……v_k)定义为周围边权值的交替和C：

这个定义与我们开始的边无关因为我们取交替和的绝对值。

下面这个关于循环循环的引理给了我们一种消除循环的方法。对于权重分配w在图的边缘上G,让G_w是最小权值完全匹配的并集，即是的子图G也就是那些存在于最小权值完美匹配中的边G。

引理2.1(零循环)。设w为二部图G边上的权函数，设C为子图G中的一个环_w。然后中国保监会_w（C) = 0。

下面的推论是直接的，它显示了如何使用上述引理来消除循环。

推论2.2(周期消除)。设C是二部图G中的一个环，w是其边上的一个权函数，使环_w（C) 0。那么C不存在于G中_w。

有几种方法可以证明引理2.1。

1. 在我们最初的文章中，¹⁰我们给出了一个基于性质的证明完美匹配的多面体。在论证中，多面体的中心点沿周期轻微移动C，这样这个点就会留在多边形中。这意味着循环C必须是零。
2. 在我们文章的第一个版本发表后，Rao, Shpilka和Wigderson(见Goldwasser和Grossman，¹³引理2.4])提出了引理2.1的另一种证明，与我们的类似，但基于大厅定理而不是匹配的多面体。
3. 在SIGACT新闻的专栏中，¹¹我们做了一个几何证明，我们通过向量相互平行或垂直来论证。人们可能会认为这是最简短和最优雅的证明。
4. 尽管如此，在下面的2.1节中，我们提出了第四个证明，我们觉得非常好。它是基于LP二元性。

2.1.完美搭配的LP配方

二部图上的最小权完美匹配问题有一个简单而广为人知的LP公式。让G是具有顶点集的二部图V和边集E。然后下面的线性程序捕获最小权重完美匹配问题(参见，例如，Lovász和Plummer^20.)．

在哪里（v)表示关联于一个顶点的边集v。线性规划只有一个变量x_e对于图中的每条边。直观地说,x_e= 1表示该边e现在是完美的匹配和x_e= 0表示e不是在完美的匹配。那么，式(2)简单地说，完美匹配只包含与某个特定顶点相关的一组边中的一条边。目标函数要求使一次完美匹配中出现的边缘的权值之和最小，即一次完美匹配的权值。

这里需要注意的一点是，上面的LP公式只适用于二部图，这也是我们的证明不适用于一般图的原因。

从LP对偶的标准理论出发，给出了最小权值完全匹配的对偶线性规划。因为在上面的原始LP中，我们对每个顶点都有一个等式约束，这里我们对每个顶点都有一个变量。

注意对偶变量没有任何非负性约束，因为原始约束是等式。

由强LP对偶性可知，这两个线性规划的最优值相等。这对于引理2.1的证明至关重要。

引理2.1的证明。让e= (u, v)为参与最小权重完美匹配的任何边，换句话说，e是一种优势G_w。让y^V是对偶最优解。我们断言对偶约束(3)对应于e紧，即，

这可以看出如下:对于任何最小权重的完美匹配米，其权重根据定义为原始最优值，因此，强对偶性必然等于对偶最优值。也就是说,

注意，在完美匹配中，所有顶点的和与所有边的端点的和是相同的。因此,

结合(3)，由(5)式可得(4)式。

现在,让C= (u₁，u₂、……u_2k)是一个循环G_w。因为每条边C某个最小权值的部分完全匹配，由(4)，的所有边C紧w.r.t是对偶最优解吗y。因此,

因此，每一个循环G_w为零循环。

回到顶部

3.构造一个独立的权重分配

推论2.2为我们提供了消除循环的方法。假设C在图上是一个循环吗G。如果我们构造一个权重分配w这样中国保监会_w（C) 0则循环C将不出席G_w，即至少有一条边C将丢失。

我们将在一小部分选定的周期上应用这项技术。如前所述，有一些标准的方法来构造一个权重函数，以确保任何小的循环集同时非零循环，参见示例。¹²

引理3.1。设C是图G中任意s个环的集合（V E）让E= {e₁，e₂，……e_米}。为j，我们定义权重

然后存在aj女士,

注意，上面的引理实际上给出了一个权重函数列表，这样对于任何想要的环集，列表中至少有一个权重函数是有效的。还可以观察到，这些函数下的任何边的权值都是有界的ms。即，只要周期数为，权值就多项式有界。

隔离重量分配现在以轮为单位进行。策略是通过赋予它们非零循环，在每一轮中持续消除一小部分循环(多边形或准多边形)。这样重复，直到没有循环为止。在每一轮中，我们都在较小的范围内将新的权重函数添加到现有的权重函数上。这是为了确保新的砝码不会明显干扰前几轮已经取消的循环。

更详细地说，如果w_我当前权重函数在我第一轮，那么在下一轮，我们将考虑权重函数w_我＋1＝西北_我+w，对于某个权重函数w而且是一个足够大的数目N。数量N被选为大于n·马克斯_ew”(e)，这就确保了这一点西北_我。得到优先于w”。权重函数w'的设计，以确保非零循环所需的一组循环G_w我。这些周期将不会出现在G_{w我+ 1}。我们将继续用这种方法消去循环，直到得到aw这样G_w没有周期。回想一下,G_w的最小权值完美匹配的并集w，因此，至少包含一个完美的匹配。自G_w没有循环，就一定有一个独特的完美匹配，所以，w是孤立的G。图3显示了一个图表，其中使用我们的方法1在三轮中构建了一个隔离权重分配，如下所述。

图3。二部图上分离权值赋值的迭代构造。

被重物捆绑。如果我们想将非零循环最多赋值为年代每一轮的循环，那么权值的界限是女士由引理3.1。如果有k这样的圆，就变成了负重的束缚O((nms）^k)．我们稍后会看到，数量(nms）^k将是准多项式有界的。

回想一下引理3.1给出了一个列表女士候选权重函数，使其中至少有一个给所有的非零循环年代周期选择在一个轮。我们需要尽一切可能女士）^k这些候选函数的组合来自每一轮。我们的准nc算法并行地尝试所有这些组合。

现在，在我们的隔离权重构建中留下的关键问题是:如何在少量的回合中消除所有的循环，这些循环可能是指数级的，同时在每一轮中只消除少量的循环。为此，我们提出了三种不同的方法。每一种方法将有一个不同的标准来选择一个小的循环集，这些循环将在一轮中被淘汰。其余的过程对于这三种方法都是相同的。下表给出了每种方法在每轮中选择的循环数以及消除所有循环所需的循环数。在这里,我们使用米n²。

表格

3.1.方法1:将周期长度加倍

这里的想法是将每一轮中我们想要消除的循环的长度增加一倍。会有日志n轮。在我第一轮，我们消除所有长度不超过2的循环^我＋1，这样我们就消去了log中的所有循环n轮。下面的引理表明，如果我们已经消除了长度不超过2的所有循环^我然后是长度为2的循环数^我＋1多项式有界吗我。

引理3.2(萨勃拉曼尼亚²³)．设H是一个有n个节点的图，它没有最长为r的环，对于某个偶数r4.那么H不超过n⁴周期长度最多2r。

证明。让C是一个长度为2的循环r在G。我们选择四个顶点u₀，u₁，u₂，u_3.在C，它把它分成几乎相等的四部分。我们联系元组(u₀，u₁，u₂，u_3.),C。我们声称C是唯一与(相关的循环u₀，u₁，u₂，u_3.)．为了矛盾，再来一次这样的循环吧C”。让pp是…的路径C和C，分别连接同一u节点。的四个部分C和C'长度相等，我们有|p| |,p”|r/ 2。因此,p和p创造一个长度的循环r，这是一个矛盾。因此，一个元组只与一个循环相关联。由四个节点组成的元组的数量被限定为n⁴长度为2的循环的数量也是如此r。

3.2.方法2:消除小周期意味着较小的平均度

这里的想法是使用Alon, Hoory和Linial的结果，²它表明一个没有小环的图必须有很多次2的节点。为了直观地理解这一点，考虑一个图，其中每个节点的度至少为3:从任意节点开始对图进行宽度优先搜索，直到深度日志n。当到达一个节点时v通过一个边缘e，至少有两条边重合v除了e。搜索树包含了一棵深度日志的二叉树n。树中的节点不可能都是不同的，否则就会严格大于2^日志n＝n节点。如果一个节点在搜索树中出现两次，那么它的循环长度最多为2 logn。换句话说，如果没有长度不超过2 log的循环n，则图必须有一个度为2或更小的节点。阿隆，霍利和利尼奥尔²将这种直觉推广到显示随着最短周期的长度增加，平均次数变得更接近2。

引理3.3 (Alon, Hoory和Linial)。设H是一个没有长度环的图< 4日志n，那么H是平均度< 2.5。

在这种方法中，我们从消除图中的所有循环开始G长度为4 logn。很容易看出，这种循环的数量是有界的n^4日志n。引理3.3表明，在此之后，中节点的常数分式G有学位2。

当我们对完美匹配感兴趣时，有许多次为2的节点是非常有用的，因为它们提供了一种在保持完美匹配的同时缩小图的方法。

1. 让v中的1度节点G和u成为独一无二的邻居v。回想一下，我们的图在每一轮之后总是一个完美匹配的并集。因此,u也有1级。因此，我们可以简单地删除u和v从G。
2. 让v为2度的节点G与邻国u和w。现在，构造一个新的图G“从G通过删除v和识别u和w获取单个节点{u, w}(见图4)．我们把这个操作称为崩溃的节点v。观察完美的匹配G和G是一一对应的。

图4。删除2级节点v并确定它的两个邻居u和w一种保持完美匹配和循环的操作。

还要注意的是，任何循环G出现在G’去掉2阶节点，也就是说，循环变得更短G”。

为了进一步使用这种方法，我们首先将所有2级节点塌陷进去G(逐个删除)，删除所有1级节点。让G₀得到结果图。因为有一个恒定分数的节点在2次G中的节点数G₀以一个常数分数递减。还要注意的是，所有的节点

G₀有学位3。由引理3.3，图形G₀同样有4 log的小周期n。现在，我们可以重复消去所有长度为4log的循环n与G₀。

在每一轮中，图中的节点数量会减少一个常数分数。因此,在0(日志n)轮，我们消除所有的循环，得到空图。我们可以很容易地在原始图中获得唯一的完美匹配G，通过逆转所有的1级删除和2级折叠。

3.3.方法3:消除边缘不相交环的最大尺寸集合

在这种方法中，我们不考虑周期的长度。相反，在每一轮中，我们选择尽可能多的边不相交的循环。回想一下，消除一个循环意味着它至少有一条边在下一轮不会出现在图中。因此，当我们消去一组不相交的环时，我们至少会消去同样多的边。一旦我们移走了足够多的边，我们就没有循环了。

让G成为一个具有n顶点,米边缘。每一轮选中的周期数被简单地限定为m。重要的是要找到一个下界。鄂尔多斯和Posa⁹显示,G至少有edge-disjoint周期。我们将讨论，如果我们在一个圆中消除一个最大尺寸的边不相交环集，那么数量米n每一轮都有显著的下降。

引理3.4。设G是一个连通图，有n个顶点和m条边。设C为G中不相交边环的最大大小集合。设H为C中每个环删除至少一条边而得到的G的任意子图₁H和n₁顶点和m₁边缘，

证明。让|C| =k。让H的任何子图G这样H的子图是H和每一个循环C,完全少了一条边H”。请注意,H的联系，因为周期在Cedge-disjoint。的边数和顶点数之间的差H”是米nk。

自H是通过删除更多的边得到的吗H的任何连接组件H，边数与顶点数之差不能大于米nk。现在，引理由上面Erdös和Pósa的下界推导出来⁹关于边不相交环的数量。

让我们重复消去最大尺寸的不相交环集的过程。它由后面的引理推导而来0(日志²n)轮，得到的图的每个分量的边数和顶点数之间有一个常数差。在这个阶段，每个组件将只有不断的许多周期。因此，在最后一轮中，我们将消除所有的循环。

对第三种方法的不同看法是考虑维完美匹配的多面体。对于连通二部图，它的每条边都属于某个完美匹配，完美匹配多边形具有维数米n+ 1 [Lovász和普卢默，^20.定理土壤质素。因此，这种方法的论证也可以看成是每一轮都将完美匹配多面体的维数减少一个分数，最终达到维0，即只有一个完美匹配点。

回到顶部

4.进一步发展

经过多年的沉寂，我们的结果启发了一系列关于完美匹配和隔离引理的并行算法的后续工作。在一个方向上，我们的隔离方法分别推广到具有完全幺模面的拟阵交点和多面体的更广泛的情形。^15，16对于这些一般设置，循环的正确替代品是与相关多面体的一个面平行的整数向量。按照第一种方法，如果我们去除了长度为2的向量^我，那么只有多项式的多个向量的长度为2^我＋1，在各自的设置(见^15，16详情)。然而，尚不清楚我们的第二和第三种方法在这些情况下是否有效。

在另一个方向，斯文森和塔纳斯基²⁴将分离结果推广到完全匹配通用图形。他们使用我们第一种方法的基本框架作为起点，但他们需要结合消除循环的技术与第二个参数(收缩性)，以控制其后各轮的进度。

我们以及Svensson和Tarnawski开发的技术被Anari和Vazirani使用^3.来计算一个完美的匹配平面图形在NC中(参见²²)，这也是一个长期悬而未决的问题。它们表明，要收缩的集合，即在lp约束中形成一个紧切点的奇顶点集，可以在NC中计算。在后续的工作中，NC算法进一步推广到单交叉次要无图。⁸

孤立引理在许多不同的场合都有应用，特别是在随机算法的设计中。仍然存在的主要问题是，还有什么其他的设置可以使隔离引理无序化。我们推测，我们的隔离方法适用于任何集族，其对应的多边形由0/1约束描述。

致谢

我们要感谢Manindra Agrawal和Nitin Saxena的不断鼓励和非常有帮助的讨论。我们感谢Arpita Korwar对本研究中使用的其他一些技术的讨论，Jacobo Torán对最短周期数的讨论，以及Nisheeth Vishnoi的有益评论。

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2019 ACM股份有限公司

---

没有发现记录