实现Babai的准多项式图同构算法？

Question

实现Babai的准多项式图同构算法？

algorithmgraphgraph-theorygraph-algorithmisomorphism

6

有人实现了拉兹洛·巴拜的准多项式图同构算法吗？

http://people.cs.uchicago.edu/~laci/

我不是这个领域的专家。我想知道，为什么不直接实现他的算法并运行它来验证其时间复杂度呢？

- JackWM

1

我认为它还没有被实现（或者说：已经实现了），但请记住，这篇论文还没有通过通常的同行评审流程。但是，如果运行它，你如何“验证它的时间复杂度”？（无论如何，“仅仅实现”他的算法听起来似乎很容易，但我怀疑这不是一件简单的事情） - Anthony Labarre

3

人们经常会忘记一个问题，那就是如果你有一个运行时间为10000000*(n^10000000)的算法，那么它是一个多项式算法，在实践中完全没用。你会愿意投资（浪费）你的时间来实现这样的算法吗？相比之下，一个运行时间为1/100000000*(1.1^n)的算法在实践中可能相当高效。 - Matsmath

2个回答

0

实际图同构问题属于P类问题。请参考Brendan McKay的C语言实现的nauty。

nauty和Traces是用于计算图和有向图的自同构群的程序。它们还可以生成规范标签。nauty和Traces使用C语言的可移植子集编写，并且可以在许多不同的系统上运行。

Babai的结果仅具有理论兴趣。

- Matsmath

我听说 VF2 也很高效，但我没有看到 nauty 和 VF2 之间的比较。我有遗漏什么吗？ - JackWM

你能定义一下“实用”并指向一个给出McKay规范标号算法具体多项式时间复杂度的参考文献吗？ - Anthony Labarre

1

有一些巧妙的手工构造的图形序列，nauty 的运行时间是指数级的。但这些图形很少见。请参见McKay1 McKay2和complexity，以及来自CS.SE的一些解释，以及来自SO的一些（模糊的）答案/解释。 - Matsmath

如果你想尝试不同的算法，并且你有Mathematica软件，可以看看IGraph/M package。它提供了VF2、Bliss和LAD算法。此外，Mathematica还内置了一个使用nauty（或者至少在信用中承认了nauty）的算法。对于大而复杂的问题，Bliss在实践中是最有效的。 - Szabolcs

2

-1：对于图同构问题的保证准多项式时间解决方案绝对不仅仅是“理论上的兴趣”。 - Hans Brende

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

假设您已经实现了算法，那么您能使用它来实证该算法的时间复杂度吗？很遗憾，答案是否定的。如果我们说一个算法的时间复杂度是 O(f(n))，那么我们就是在说：

- 对于足够大的输入， - 在所有可能的这个大小的输入中， - 运行时间最多是 n 的常数倍。

因此，想象一下我们已经编写好了代码。要验证所宣称的上限是否适用，我们可以尝试在几个输入上运行并绘制运行时间，但这并不能告诉我们任何东西。我们的输入可能不足够“大”，以使渐近上界适用。即使我们得到了大输入并在许多不同的输入上看到了运行时间，我们仍然不知道是否具有最坏情况的运行时间，除非我们尝试所有可能的输入，但是图同构算法的可能输入数量随着输入大小呈指数增长。这意味着我们无法在大输入大小时尝试所有可能的输入，因此我们永远无法确定是否找到了实际的最坏情况输入。还有许多实际问题会出现。算法的理论分析通常没有考虑缓存行为、分页、抖动等等，所以我们可能会看到某些大输入的时间比预期的要长得多，仅仅因为它们与缓存不兼容。在这种情况下，我们可能会发现事情比预期的慢得多，尽管原始操作的数量分析是正确的。总之，无论我们在实际输入上运行多少次算法，都不能肯定地确认或否认运行时间分析是否正确。如果它似乎符合趋势，那太好了...但是你没有查看的无数输入呢？如果它似乎不符合预测的趋势，那么您如何知道您没有尝试足够大的输入？或者说，您是否从其他因素中看到了分析中的噪声？这就是为什么难以分析这些算法的原因。我们可能已经拥有一种图同构的多项式时间算法，但没有人能够证明它具有正确的运行时间。任何实证数据都不能作为证明，尽管它可能激励人们尝试证明某种方法快速运行，从而在理论上证明观察到的运行时间的正确性。