一个CM通信

评论文章

用于更快算法的代数指纹

作者:Ioannis Koutis, Ryan Williams
ACM通信，2016年1月，第59卷第1期，第98-105页
10.1145 / 2742544
评论

2010年，Andreas Björklund发现了许多人之前认为不可能的事情:一种针对名人的显著改进算法哈密顿路径问题，也被称为汉密尔顿性。⁴哈密性要求一个给定的图是否包含一条路径，该路径只经过每个顶点一次，如图1．

回到顶部

关键的见解

哈密性是卡普最先提出的np完全问题之一。^20.已知的np完全问题的唯一算法需要时间缩放指数级的输入的大小。尽管不排除这种可能性，但总的来说，这些问题不可能更快地得到解决。¹⁷给定一个无向图n顶点，Björklund的算法可以找到一个哈密顿路径或报告不存在这样的路径O* (1.657ⁿ)时间。^一个该算法仍然在指数时间内运行，但比O* (2ⁿ)之前最快算法的运行时间，自20世纪60年代以来就为人所知。^3.，19

哈密性是一个突出的算法问题。在Björklund之前，许多研究人员已经在这方面进行了尝试，但都没有成功。但是Björklund使用的一些工具直到2009年才得以使用k-path问题，是上下文中的相关问题参数化算法。

一个参数化的种族和一个猜想。的k-路径问题是哈密顿性的自然参数化模拟。现在的目标是在给定的图中找到一条长度的路径k的某一特定值k，而不是一条长度的路径n。从实际的角度来看，可以说k-路径问题相对于哈密顿性有更好的动机。算法专门为k-path问题已经被用于检测大型蛋白质相互作用网络中的信号通路。²⁹

大多数np完全问题都有类似的参数化，其中参数k测量解决方案的大小到给定的实例。这是很自然的，因为在实践中，np困难问题的解决方案长度通常比整个实例的长度短。唐尼和同伴¹²观察到，一些参数化问题似乎比其他问题“更容易”。为了捕捉这一点，他们定义了类固定参数易处理的(把)问题。FPT的定义相当简单。参数化算法的运行时间显然应该取决于输入的大小n，参数k。但这种依赖性应该有些特殊:如果一个问题可以用一种算法来解决，那么这个问题就被定义为FPTO* (f（k)时间。

FPT概念已经被证明是非常有洞察力的，并导致了对问题硬度的更详细的理解。并不是所有np困难的问题都是FPT问题;一个突出的例子是k-派系问题，其目标是检测一个k-成对连接的网络节点的子集(参见图2)．最著名的算法k-clique并不比穷尽式搜索好多少，穷尽式搜索需要时间O（n^k)．然而，经验表明，当一个问题被显示为FPT时，算法的进展才刚刚开始，因为它通常是函数的情况f（k)的运行时间可以得到提高。

的k-path问题就是一个典型的例子。莫尼安认为问题出在FPT上²⁵谁描述了运行的算法O* (k)时间。这后来被改进为O* ((2e）^k)阿隆等人。²和O* (4^k)作者:Chen等。¹⁰这些步骤中的每一个都代表着一个重要的新思想的引入。同样，对于许多FPT问题，现在也存在这样的问题比赛对于更快的参数化算法，²⁷用新的技术丰富了算法设计领域。

然而，随着每一次改进，人们都面临着一个问题:是否有可能取得进一步的进步?已知的“父”np完全问题的算法对于回答这个问题是有价值的指南。这是因为它们的运行时间为参数化算法设定了明确的目标。在哈密性的例子中，我们知道一个运行的算法O* (2ⁿ)时间。因此，有理由推测有一种算法k运行的路径O* (2^k)时间，“匹配”哈密顿路径算法为参数的极值。

路线图。我们将要讨论的算法技术的发展很大程度上是由k路径推测。但为了简单起见，我们将在另一个重要的np完全问题的背景下说明它们，即3d匹配问题，该问题也发挥了核心作用。事实上，哈密顿性算法之前是另一个破纪录的算法3d匹配问题，也是由于Björklund。⁵

在本文中，我们迈向更快算法的第一步是所谓的代数化组合问题的，也就是说，把这个问题看成一个关于多项式中某些单项是否存在的问题。我们稍后讨论三维匹配问题的一种代数化方法。给定了多项式，原来的组合问题变成了代数检测单项;也就是说，通过给多项式的变量赋值，从多项式中提取信息。寻找符合我们目的的作业将引导我们进行模2的计算，在一个代数中，对的和抵消了。这反过来又会给我们带来一个问题不需要的取消单项。我们将用的方法来解决它指纹增加3d匹配多项式，以确保没有不必要的取消发生。的k-路径猜想通过指纹代数检测的推广得到了正解，这也产生了许多其他更快的参数化算法。这些想法将在后面进行回顾，Björklund的关键扭转有助于解锁更快的哈密顿性算法。尽管仍然以一种轻松的方式使用指纹的方法，Björklund不仅把计算模2看作是一种麻烦，而且是一种资源，通过在许多地方提出代数不需要的单体消掉了，因为它们是成对出现的。为了推导出更清晰的代数利用取消， Björklund利用了代数组合学的力量，通过线性代数研究图。接下来是其他几个参数化问题的更快算法。

回到顶部

代数化

考虑下面这个虚构的航班调度问题:在任何给定的一天都有一个集合X指定的船长，一组Y指定的二把手，还有一组Z的目的地。每个船长和二副都要宣布一些首选目的地。航空公司希望能满足尽可能多的偏好;但与此同时，他们希望在同一航班上匹配一名曾一起飞行的飞行员和副驾驶。这就创建了一些三元组:if captainx以前和副驾一起坐过飞机吗y他们都想飞到目的地z，它们定义了一个三重{x, y, z}。当然，任何给定的船长、副驾驶或目的地都可能出现在许多三重组合中。但为了最大化效用，航空公司希望选择一个大匹配，即成对不相交的三元组的子集;在此基础上，他们可以安排人员。np完全问题要求匹配最大大小，而参数化问题要求匹配最大大小k-匹配至少k三重组，我们也叫它ak三维匹配。该问题的一个例子显示在图3．

三维匹配的多项式。在库蒂斯明确阐述之前，这一点可能已经被许多人理解了²¹我们可以看到k通过代数透镜的- 3d匹配问题。让我们通过文中的例子来解释图3．

首先，我们把集合中的每个元素看作一个变量X, Y, Z。我们有变量X= {x₁，x₂，x_3.}，Y= {y₁，y₂，y_3.},Z= {z₁，z₂，z_3.，z₄}。然后对每一个三元组，通过取相应变量的乘积，构造一个单项。在我们的例子中图3，我们有单项式。

我们还定义了实例多项式P₁是这些单项的和。最后，我们设置&cacm5901_a;;我们将调用P_k的kth编码多项式。例如，对于第二个编码多项式，我们有

要了解这些定义背后的动机，请考虑的扩展P₂变成和积形式。

和积展开式中的单项可分为两类。在展开的解部分，对应于问题解的一元是线性的;该乘积不包含平方或其他高幂变量。举个例子，单项x₂x_3.y₁y_3.z₁z₄式(2.1)中为线性，对应于选择第二个和第四个三元组。在互补的非解部分，每个非线性单项对应一个“非解”，即非不相交三元组的选择。

这种构造可以推广到问题的任何实例;唯一的区别是如果我们想要检查ak-匹配，我们就必须看多项式的和积展开P_k．总结:

观察。3d匹配问题的一个实例包含一个大小为k的匹配，当且仅当第k个编码多项式P的和积展开_k包含一个线性单项。

因此，要解决三维匹配问题，只需对多项式展开即可P_k代入乘积的和，并检查这个和是否包含一个线性单项。然而,一个O* (2^N）动态规划算法已知，为N= |X| + |Y| + |Z|。另一方面，可能的单体数N变量比O* (2^N)．因此，扩展的想法很简单P_k化成积并不能给出一个好的算法。

动态规划代数。动态规划经常涉及归纳定义，陈述起来很繁琐;在我们的代数设置中的类比可能更直观。它可以很自然地看作是多项式的“截断”展开P_k变成和积形式。更具体地说，想象一下扩张P_k慢慢地，一次做一个乘法。我们观察到，包含平方变量的单项一旦形成就可以被丢弃，因为它们不影响线性单项在的完全和积展开中的存在P_k．有两个^N线性单项N变量。这意味着“截断”展开可以在O* (2^N)时间。的最终截断和积形式中，如果至少还有一个单项P_k，我们可以得出结论，给定的实例包含一个3D匹配的大小k。否则，它不会。

更正式地说，我们是在计算和积展开P_k在一个扩展的多项式的动态规划代数它包含了多项式的乘法和加法的所有常用规则，还有一个额外的规则所有平方变量的值都为零。注意，这意味着所有的非线性单项也等于零。因此，我们可以用代数术语重新表述我们对线性单体的观察P_k：

3d匹配问题的一个实例包含一个大小为k的匹配，当且仅当第k个编码多项式P_k在动态规划代数中不等于零。

一般来说，我们可以N= 3k，因为所有的元素XYZ可以参加3D配对。然而，如果我们只是在寻找一个3D匹配只包含k三倍，那么我们可以把目标设为anO* (2^3.k)时间参数化算法。

通过作业参数化。这里的目标是描述3d匹配问题的第一个参数化算法，它将演示如何使用多项式变量的赋值，以便从中提取信息。

“参数化”的问题O* (2^N)的算法显然在于变量的数量N。阿隆，尤斯特和兹威克正在努力解决这个问题²想出了一种叫做颜色编码的方法。它们的解可以理解为如下的赋值。回到前面的例子，假设我们对查找大小为2的匹配感兴趣。然后，如所讨论的，和积展开中的所有线性单项P₂有六个程度;它们是六个不同变量的乘积。Alon等人提出了一种新的集合W正好包含6个变量(更一般地说3 k变量的k当日)。所以,让

然后对变量进行随机分配W的变量X, Y, Z。我们也可以把这个任务想象成随机着色N变量与k颜色。让我们考虑一个这样的任务:

将式(2.1)代入，P₂（X, Y, Z)变成了变量的多项式W：

可以看出，一元在P_k（X, Y, Z)映射到单项式P_k（W)．如果一个单体在P_k（X, Y, Z)不是线性的，对应的单项也是如此P_k（W)．的线性单项P_k（X, Y, Z)可能作为线性单项存在，也可能不存在P_k（W)．在我们的例子中，除了一个线性单项外，所有的线性单项都映射为中的线性单项P₂（W)．检测线性单项P_k（W)可以让我们推断出它在P_k（X, Y, Z)，因此存在一个k-匹配我们原来的问题。相反的情况可能不成立，因为可能没有线性单项在赋值后存活。

我们可以评估P_k（W)在动态规划代数中P_k（X, Y, Z)．因为现在W只包含3k变量，求值的变量O* (2^3.k)时间。然而，任何给定的线性单项通过随机颜色编码分配存活的概率是非常小的;它可以被计算出来e^3.k在哪里e2.72.这意味着你必须去尝试O（e^3.k)的随机分配，以使单项以可接受的恒定概率存活下来，独立于k。总的运行时间是O* ((2e）^3.k)．这仍然是一个因子e^3.k远离我们的O* (2^3.k)目标。

回到顶部

代数检测

前面提到的检测线性单项的方法本质上是组合，但我们用代数的形式来表示。如果我们使用真正的代数方法，我们能找到更快的算法吗?

一个矩阵赋值。前面，我们考虑了对编码多项式的变量进行赋值的想法P及其在动态规划代数中的后续评价。动态规划代数和颜色编码分配只是一种可能。有很多可能的代数和赋值。特别是矩阵似乎提供了丰富的可能性。矩阵代数的一个吸引人的特性是，矩阵的平方可以为0，这提供了一种真正的代数方法来“实现”动态规划代数，特别是它的规则，变量的平方应该为零。举个简单的例子:

这导致我们对一组用于检测线性次单项的随机矩阵提出了以下要求k，即产品k不同的变量。

1. 为了简化关于单项式的推理，矩阵必须是成对交换的，也就是说，我们相乘的顺序不应该影响乘积的值。
2. 每个矩阵的平方必须等于零。随着交换性，这意味着非线性单体也将计算为零。
3. 度的线性单项式k必须在赋值中“存活”，也就是说，求值为一个非零矩阵，具有恒定的概率，比如至少1/4。如果这个非零矩阵的对角线上只包含1，那就方便多了。
4. 因为我们在寻找速度，矩阵必须尽可能小，以支持快速评估。理想情况下，矩阵运算应该需要时间O* (2^k)或更少。

在Koutis²²给出了这类矩阵的一个有效的随机化构造，表明如果我们愿意放宽零的概念，就有可能满足所有这些要求:

这里的“0”指的是0对2的模

我们称之为Mod-2矩阵事实。

我们不会讨论如何证明Mod-2矩阵事实的技术细节，因为我们在这里需要了解的是它的算法能力和结果。

与颜色编码方法相比，我们看到多项式的求值需要相同的时间，O* (2^k)用于检测线性单项k变量。增益在于线性单项在分配中存活的概率;从指数小概率e^k，概率就变成了1/4。这似乎表明我们已经摆脱了不需要的东西e^k并达到了我们的目标检测程度-k线性单项O* (2^k)时间，因此大小k3 d匹配O* (2^3.k)时间。

不需要的取消。然而，更仔细的观察会发现，由于我们对零的概念过于宽松，我们还没有做完。多项式很明显P（X)如果它不包含线性单项，则求值为零。然而，Mod-2矩阵事实不能保证P（X)求值为非零，即使它的一些线性单项求值为非零。这个问题最重要的来源不是在计算中，而是在多项式中P本身:通过看一下式(2.1)中的和积展开，我们可以看到的解部分P它由线性单项组成已经等于0了国防部2，因为单项乘以2。

指纹法。我们通过使用一组“指纹”变量，确保每个单项都是唯一的，从而解决线性单项的多个副本的问题一个= {一个₁，一个₂,……}。我们在k3 d-matching多项式P₂我们现在将其定义如下:

我们在这里所做的就是乘以每一个三倍的inP₂使用来自集合的“fresh”变量一个。然后考虑一下单项式的两个副本会发生什么x₂x_3.y₁y_3.z₁z₄；它们现在被两个独立的线性单项所取代:一个₂一个₈x₂x_3.y₁y_3.z₁z₄而且一个₆一个₄x₂x_3.y₁y_3.z₁z₄．

似乎辅助变量的引入是以获得更高次的线性单项为代价的，这将需要更大的矩阵才能通过评估，从而导致算法更慢。

但是，另一种想法是使用不同的赋值一个变量。例如，我们可以在的变量中分配随机的{0,1}值一个。本质上，我们希望为线性多项式创建奇数个副本，这样编码多项式的解部分就不是模2的零。在Koutis²²结果表明，这种方法足以进行线性单项检测在3d匹配的情况下。也就是说，通过给变量随机分配矩阵X, Y, Z，和{0,1}值对指纹变量，如果多项式的和积展开包含一个线性单项，则多项式将以恒定的概率求非零值，否则总是为零。

目标达成。我们设计了一个O* (2^3.k的时间算法k3 d-matching问题。

一个一般的代数框架。我们已经非常接近一个快速参数化算法来解决一个比k- 3d匹配问题:即检测度-k任意多项式的和积展开中的线性单项P（X)，以某种简洁、“未扩展”的形式呈现给我们。这个问题的重要性在库蒂斯得到了证实^22，24其中观察到，它的快速算法意味着一些参数化问题的更快算法，包括k路径问题。为了推广这个方法，我们需要做什么?

这里描述的所有步骤都延伸到任意多项式，包括使用适当的多项式预处理和在其中放置指纹变量生成唯一的线性多项式。然而，我们仍然被多重副本问题所困扰，因为对指纹变量的随机{0,1}赋值并不保证对任何多项式都有效。因此，我们将需要推广到一些其他类型的赋值，在任意情况下工作，同时仍然是紧凑的，易于计算处理。

以下是威廉姆斯提出的解决方案。³²想象一下评估P（X,)分为两个阶段。首先，我们分配随机矩阵&cacm5901_c;从Mod-2矩阵事实到X变量和计算P(&cacm5901_c;一个),将一个变量未鉴定的。结果是一个对角线是多项式的矩阵问（一个)．Mod-2矩阵事实说明了这一点问（一个)取模2为零，如果P（X)不包含线性单项。如果P（X)确实包含一个线性单项问（一个)为非零，概率至少为1/4。这种考虑使问题具体化:我们希望能够测试是否问（一个)等于0对2取模，我们想通过求值来实现问（一个)对其变量进行“紧凑”赋值。然而，这个问题早就被研究和解决了。它被称为身份测试。

一个被称为SchwartzZippel引理的身份测试解决方案，²⁶简单直观。我们在赋值中为3d匹配多项式选择值{0,1}的原因是，我们可以使用它们执行模2运算的乘法和加法。但是还有其他的代数“域”允许我们进行同样的操作，额外的事实是它们更大，在某种意义上它们包含更多的值。如果我们选择的字段不是{0,1}，而是由O（k)值对指纹变量可能赋值的数量远远超过可能的根的数量问（一个)，即使其求值为零的赋值数。因此，从这个更大的领域随机分配将产生高概率问（一个)求值到字段中的非零值。这使得我们可以得到以下结果。

快速线性单项检测。检测度的问题-k任意多项式中的无平方单项P（X)可以在中求解O* (2^k)时间。

回到顶部

打破贸易壁垒

一个更快的线性单项检测参数化算法将会产生巨大的影响，因为它意味着更快的算法不仅适用于许多参数化问题，而且适用于相应的非参数化NP-hard问题。因此，一个有趣而自然的问题是，是否可以通过在支持更快运算的更奇特的代数上计算输入多项式来更快地解决问题。不幸的是，这个问题的答案是否定的;不可能找到更好的代数了。²⁴

这个代数势垒表明，如果有可能的话，在线性检测问题上进一步取得进展需要新的技术。然而，人们可以对具体问题持乐观态度。线性单项检测是非常普遍的，完全不知道潜在问题的组合性质，因此利用特定的问题性质有时可能绕过代数障碍。另一方面，试图在研究完善的np完全问题上取得进展，如哈密顿路径问题或3d匹配问题，可能会面临一个更重要的心理障碍:近50年来缺乏进展。

在精彩的作品中，Andreas Björklund用一种O* (2^{N/ 3})时间算法的“精确”x3d匹配问题⁵和惊人的O* (1.657ⁿ)哈密性的时间算法。⁴这些运行时间后来被参数化算法几乎匹配。⁶读者可以在Fomin等人的书中找到。¹⁴这是二分图哈密顿路径问题算法的一个极好的阐述。

Björklund的核心工作是从大量的代数组合学(例如，Royle)中提取的更清晰的代数工具²⁸)生成低次多项式。更重要的是，Björklund提出了放宽指纹法的想法，以便利用非解单体对的消去。在这里，我们将看到这些思想是如何应用于x3d匹配问题的。

计算加权匹配Mod 2。考虑将我们的3d匹配问题限制为2d匹配问题，在2d匹配问题中，我们得到的是由船长和副驾驶组成的对，而不是三人组。我们假设这两个集合X而且Y大小相等n。

该问题有一个如图所示的图形表示图4．一个解决方案的n覆盖图中所有顶点的边/对称为a完美的匹配。

完美匹配问题可以在多项式时间内得到解决。但计数完美匹配的数量众所周知是一个难题;这就像计算np完全问题的解决方案的数量一样困难。^30.事实上，对任何质数取模也很难计算出完美匹配的数量p,除非p= 2。如果p= 2模2的完美匹配的个数等于二部图的关联矩阵的行列式。²⁸这个关键事实将发挥重要作用，因为矩阵行列式可以用多项式次的算术运算来计算。

定义关联矩阵一个，我们任意编号节点X数字从1到n，并对中的节点执行相同的操作Y，如图4．条目一个（我,我)如果节点为1我X连接到节点jY，否则为0。

给定这个定义，如果N₂表示完美匹配的次数，我们称之为匹配的引理：

我们现在考虑对上述引理的一个扩展，它将特别有用。完美匹配计数问题对边标记多图有一个自然的泛化，其中(i)我们允许任意两个给定节点之间有多条“平行”边，(ii)每个边e被标记为唯一的单项l_e．

匹配的签名定义为通过取匹配的边的标签的乘积而形成的单项．例如，匹配中的签名图4是l_1、4l_2、1l_3、2l_4、3．更普遍的是,

给定边缘的标记，我们可以展开N₂解的多项式N₂（l)，它只是所有完全匹配的签名的和，比如if米那么完美匹配的集合在图中吗

最后，我们可以扩展关联矩阵一个一个矩阵一个_l在l用一种自然的方式:if节点我而且j都由一条或多条边连接，我们让一个_l（我,我)是总和他们的标签。我们有以下广义匹配引理:

x3d匹配的单项检测。我们现在返回到x3d匹配问题，这是一个3d匹配问题，加上约束|X| = |Y| = |Z| =n。在这种情况下，我们想要确定是否有一个解由n＝N的所有元素的解X, Y, Z。

该算法涉及到将X3D匹配问题转换为标记匹配实例。的集X而且Y定义二部图的两部分。为了确定标签，我们使用了两组变量，Z而且U。中的一个不同的变量Z每个三元组对应一个不同的变量U。

为了了解如何形成标记二部图，我们给出了一个例子，说明了图的两个给定顶点之间的边，以及它们的标记。假设x3d匹配实例包含三元组

没有其他带有{的三元组W, K担任船长和二副。再假设我们已经将这些三元组中的变量关联起来u₁，u₂，u_3.,分别。然后,节点W而且K会用三条边连接，分别用单线标记吗u₁z_SJU，u₂z_旧金山,u_3.z_坑．

现在考虑多项式N₂（Z,你）国防部2.因为二部图的每条边都对应于一个三重的，任意的一项N₂（Z,你）国防部2对应于的选择n因为它是匹配的签名。根据定义的N₂（Z,你）国防部2这些n三元组完全覆盖集合，没有重叠X而且Y。在目标重叠的情况下，单项包含一个平方变量，对应于该目标。另一方面，如果一组三元组形成一个三维匹配，单项式是线性的，相对于变量Z因为没有目的地出现两次。因此，从Mod-2矩阵事实分配随机矩阵到变量Z我们将非线性单项归零。此外，我们还观察了中各单项的系数N₂（l）国防部2等于1，因为U变量指定每一组n三元组。因此,U变量是我们的指纹变量，我们将从一个适当的代数域中分配值给它们O（n)．有了这些分配，评估的结果将是非零的一个很好的概率当且仅当N₂（l)包含与实例的解对应的单项。因此，如果存在精确的三维匹配，我们可以检测到。算法的运行时间为O* (2ⁿ)因为的程度N₂（Z,你)就…而言Z变量是n。

决定因素和周期。当行列式按模2计算时，如式(4.2)所消去的单项对应于循环覆盖。一个循环是一条路径加上一条闭合循环的边。循环盖是图中的一组循环，每个顶点恰好参与一个循环。特别地，一个哈密顿循环，即包含所有顶点的循环，是一个循环盖。完美匹配也是一个循环盖，尽管它只包含“简并”循环，也就是边。包含至少一个非简并循环的循环盖成对出现，因为每个这样的循环可以以两种可能的方式遍历:顺时针和逆时针。Björklund的哈密顿性算法实际上针对的是哈密顿循环而不是路径，它通过向图中的一些边引入方向打破了这种对称性。他的算法仍然主要依赖于剩余的对称和消去。哈密性是否有一个更快的O* (2ⁿ)一般有向图时间算法。

回到顶部

最近的进展

自代数指纹模计算的一般框架出现以来，已被用于设计一些参数化问题的更快的算法。例子包括:寻找比路径更复杂的子图，^16，31在生物网络中寻找功能基序，^8，18，23寻找通过给定图中指定节点的最短周期，⁷以及字符串的无重复最长公共子序列问题，在计算生物学中的应用。⁹在众多的例子中，我们强调了在图上np完全问题的算法的显著进展，用所谓的参数化treewidth输入图的。

如果图是一棵树，也就是说，如果它不包含循环，那么图上的几个np完全问题是可以处理的。图问题的np完备性通常是通过构造非常复杂的图来证明的，这些图与实际情况中出现的图相比，可以说是人为的。特别是，真实世界的图通常具有更类似树的结构。

树宽的概念提供了一种量化给定图“偏离”存在树的程度的方法。文中给出了一个例子图5．图的顶点以树形结构排列。每个树节点列出一些图顶点的副本。图的每条边都连接在某个树节点上列出的两个顶点。此外，任何给定的图顶点只能出现在相邻的树节点中。的treewidth太瓦的最大值定义为树节点中承载的图顶点的最大值;在我们的例子中太瓦= 3。作为一个更普遍的例子，自然类平面图，即可以在没有交叉的平面上绘制的图，具有树宽度&cacm5901_d;，其中n是顶点的个数。

西冈等。¹¹给出了许多用树宽参数化的图问题更快的算法。以前的算法有这种形式的运行时间O* (太瓦^太瓦)，而新的算法大大提高了表单的运行时间O* (c^太瓦)为小常数c;例如，哈密顿路径周期可以在O* (4^太瓦)时间。

回到顶部

开放的问题

本文中的算法都是随机化的;在任何给定的运行中，他们都有很小的概率报告一个实例没有解决方案，而实际情况恰恰相反。但运行O(日志(1 /p)的次数将使总体失败的概率小于p,对于任何p> 0。最快的知道确定的算法的k路径问题需要O* (2.85^k)时间。¹⁵找到一个确定的算法来解决问题O* (2^k时间仍然是一个悬而未决的问题。按照目前的情况，似乎需要一个确定性版本的SchwartzZippel引理:一个确定性的多项式时间算法，用于测试一个给定的多项式作为算术电路是否等于零。

代数指纹法可用于求解加权问题k路径问题;这里的目标是找到一个k-path的最小总代价，假设一个代价附加到图的每条边。运行时间为O* (2^kW),W是与图中某条边相关的最大代价。另一方面，动态规划可以解决这一问题O* (2n日志W),当k＝n。推测是合理的k路径有一个O* (2^k日志W)算法。但需要注意的是，与代数指纹方法不同的是，它可以在内存中实现多项式的大小n，颜色编码为加权k路径需要O* (2^k)记忆，这在实践中可能是一个非常有限的因素。

动态规划也可以用于数哈密顿路径的个数。数数k-paths exactly可能不是FPT，¹³但是颜色编码可以用来计数k路径约,在O* ((2e）^k)时间。¹这是目前已知的解决这个问题最快的算法，但我们有理由推测O* (2^k)算法进行近似计数。

解决这些开放的问题可能需要新的想法，从而开启新的发现周期。

回到顶部

致谢

一、库蒂斯获得NSF CAREER奖CCF-1149048的支持。R. Williams获得了David Morgenthaler II学院奖学金、NSF CCF-1212372、斯隆奖学金和微软研究奖学金的支持。这项工作的最后阶段发生在西蒙斯计算理论研究所。

回到顶部

回到顶部

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2016 ACM, Inc.

---

没有发现记录