如果我们的目标时间复杂度是 O(|V| * |E|) 或 O(V^3) 等，这个问题就有一个简单的解决方案。然而，我的教授最近给了我们一个作业，问题陈述是:
Let G = (V, E) be a connected undirected graph. Write an algorithm that determines if G contains a triangle in O(|V| + |E|).
在这一点上，我被难住了。 Wikipedia说:
It is possible to test whether a graph with m edges is triangle-free in time O(m^1.41).
除了在 Quantum 计算机上运行的算法之外，没有提到可能有更快的算法。之后我开始求助于更好的资源。 Math.SE 上的一个问题将我链接到 this paper上面写着:
The fastest algorithm known for finding and counting triangles relies on fast matrix product and has an O(n^ω) time complexity, where ω < 2.376 is the fast matrix product exponent.
这就是我开始意识到的地方，也许我们被骗去解决一个 Unresolved 问题!那个可恶的教授!
不过，我还是有点怀疑。论文上写着“查找和计数”。这是否等同于我要解决的问题？
TL;DR:我是被愚弄了，还是忽略了如此微不足道的事情？
最佳答案
事实证明，这在 O(|V| + |E|) 中确实不可行。或者至少，我们不知道。我读了 4 篇论文才得出这个结果。我中途停了下来，因为我意识到它更侧重于分布式计算而不是图论。其中之一甚至给出了概率算法来确定“几乎线性”时间内的三角形自由度。三篇相关论文是:
- Finding and counting given length cycles作者:Alon、Yuster 和 Zwick。
- Testing Triangle-Freeness in General Graphs作者:Alon、Kaufman、Krivelevich 和 Ron。
- Main-memory Triangle Computations for Very Large (Sparse (Power-Law)) Graphs通过拉塔皮
我为作业写了大约 2 页的 LaTeX，并以适当的引文引用了论文。论文中的相关说法加框:
最后，我和我的教授谈过，事实证明，这实际上是一个无意的严重错误。然后他将所需的复杂度更改为 O(|V| * |E|)。我不怪他，他让我学习了更多图论!
关于algorithm - 确定图形是否包含三角形？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31521126/