确定图形是否包含三角形？

Question

如果我们的目标时间复杂度是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.

这就是我开始意识到的地方，也许我们被骗去解决一个未解决的问题！那个臭教授！

不过，我还是有点怀疑。论文说 "finding and counting"。这是否等同于我要解决的问题？

TL;DR：我是被愚弄了，还是我忽略了如此微不足道的事情？

Answer 1

这是 O(|E|*|V|) 版本的代码。

当你限制|V|位掩码 intersect-any 操作实际上是 O(1) 这让你 O(|E|)，但那是作弊。

实际上，复杂度为 O(|E| * (|V| / C))，其中 C 是某个特定于体系结构的常量（即：32、64、128）。

function hasTriangle(v, e) {
  if(v.length > 32) throw Error("|V| too big, we can't pretend bit mask intersection is O(1) if |V| is too big!");
  // setup search Array
  var search = new Uint32Array(v.length);
  // loop through edges O(|E|)
  var lastEdge = [-1, -1];
  for(var i=0, l=e.length; i < l; i++) {
    var edge = e[i];
    if(edge[0] == lastEdge[0]) {
      search[lastEdge[1]] = search[lastEdge[1]] | (1 << edge[0]);
      search[edge[1]] = search[edge[1]] | (1 << edge[0]);
    } else {
      lastEdge = edge;
    }
    // bit mask intersection-any O(1), but unfortunately considered O(|V|)
    if( (search[edge[0]] & search[edge[1]]) > 0 ) {
      return true;
    }
  }
  return false;
}

var V = [0, 1, 2, 3, 4, 5];
var E_no_triangle = [[0, 4], [0, 5], [1, 2], [1, 3], [2, 5]];
var E_triangle = [[0, 1], [0, 2], [0, 3], [1, 4], [2, 1], [2, 3], [4, 5]]; // Triange(0, 2, 3)
console.log(hasTriangle(V, E_no_triangle)); // false
console.log(hasTriangle(V, E_triangle)); // true

Answer 2

嗯，事实证明，这在 O(|V| + |E|) 中确实不可行。或者至少，我们不知道。我读了 4 篇论文才得出这个结果。我中途停了下来，因为我意识到它更侧重于分布式计算而不是图论。其中之一甚至给出了概率算法来确定 "almost linear" 时间内的三角形自由度。三篇相关论文是：

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 来自 Latapy

我为作业写了大约 2 页的 LaTeX，引用了论文并附有适当的引文。论文中的相关说法加框：

最后，我和我的教授谈过，事实证明，这实际上是一个无意的严重错误。然后他将所需的复杂度更改为 O(|V| * |E|)。我不怪他，他让我学了更多图论！

确定图形是否包含三角形？

Determine if a graph contains a triangle?

algorithm

graph-theory