Determine if a graph contains a triangle?

Question

This problem has an easy solution if our target time complexity is O(|V| * |E|) or O(V^3) and the like. However, my professor recently gave us an assignment with the problem statement being:

Let G = (V, E) be a connected undirected graph. Write an algorithm that determines if G contains a triangle in O(|V| + |E|).

At this point, I'm stumped. Wikipedia says:

It is possible to test whether a graph with m edges is triangle-free in time O(m^1.41).

There was no mention of the possibility for a faster algorithm besides one that runs on a Quantum computer. I started resorting to better sources afterwards. A question on Math.SE linked me to this paper that says:

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.

And that's where I started to realize that maybe, we're being tricked into working on an unsolved problem! That dastardly professor!

However, I'm still a bit skeptical. The paper says "finding and counting". Is that equivalent to the problem I'm trying to solve?

TL;DR: Am I being fooled, or am I overlooking something so trivial?

Answer 1

Well, it turns out, this really isn't doable in O(|V| + |E|). Or at least, we don't know. I read 4 papers to reach this result. I stopped half-way into one of them, because I realized it was more focused on distributed computing than graph theory. One of them even gave probabilistic algorithms to determine triangle-freeness in "almost linear" time. The three relevant papers are:

• Finding and counting given length cycles by Alon, Yuster & Zwick.
• Testing Triangle-Freeness in General Graphs by Alon, Kaufman, Krivelevich & Ron.
• Main-memory Triangle Computations for Very Large (Sparse (Power-Law)) Graphs by Latapy

I wrote about 2 pages of LaTeX for the assignment, quoting the papers with proper citations. The relevant statements in the papers are boxed:

---

---

In the end, I spoke to my professor and it turns out, it was in fact an unintended dire mistake. He then changed the required complexity to O(|V| * |E|). I don't blame him, he got me to learn more graph theory!

Answer 2

Here's the code for the O(|E|*|V|) version.

When you constrain |V| the bit mask intersect-any operation is effectively O(1) which gets you O(|E|), but that's cheating.

Realistically the complexity is O(|E| * (|V| / C)) where C is some architecture specific constant (i.e: 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