<p>If you have an adjacency matrix, you can find triangles by squaring the matrix and seeing if the original matrix and square matrix have a non-zero entry in the same place.</p>

<p>A naive matrix multiplication takes time <code>O(n^3)</code>, but there are fast matrix multiplication algorithms that do better. One of the best known is the <a href="http://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm" rel="nofollow noreferrer">Coppersmith-Winograd</a> algorithm, which runs in <code>O(n^2.4)</code> time. That means the algorithm goes something like:</p>

<ul>
<li>Use <code>O(V^2)</code> time to convert to an adjacency matrix.</li>
<li>Use <code>O(V^2.4)</code> time to compute the square of the adjacency matrix.</li>
<li>Use <code>O(V^2)</code> time to check over the matrices for coinciding non-zero entries.</li>
<li>The index of the row and column where you find coinciding non-zero entries in (if any) tell you two of the involved nodes.</li>
<li>Use <code>O(V)</code> time to narrow down the third node common to both the known nodes.</li>
</ul>

<p>So overall this takes <code>O(V^2.4)</code> time; more precisely it takes however long matrix multiplication takes. You can dynamically switch between this algorithm and the if-any-edge-end-points-have-a-common-neighbor algorithm <a href="https://stackoverflow.com/a/10193372/52239">that amit explains in their answer</a> to improve that to <code>O(V min(V^1.4, E))</code>.</p>

<p>Here's a <a href="http://i11www.iti.uni-karlsruhe.de/extra/publications/sw-fclt-05_wea.pdf" rel="nofollow noreferrer">paper that goes more in-depth into the problem</a>.</p>

<p>It's kind of neat how dependent-on-theoretical-discoveries this problem is.
If conjectures about matrix multiplication actually being quadratic turn out to be true, then you would get a really nice time bound of <code>O(V^2)</code> or <code>O(V^2 log(V))</code> or something like that. But if quantum computers work out, we'll be able to do <a href="http://arxiv.org/abs/quant-ph/0310134" rel="nofollow noreferrer">even better than that</a> (something like <code>O(V^1.3)</code>)!</p>
How to find a triangle inside a graph?
<p>Here is an exercise in the <a href="http://www.algorist.com/">Algorithm Design Manual</a>.</p>

<blockquote>
  <p>Consider the problem of determining whether a given undirected graph G
  = (V, E) contains a triangle or cycle of length 3.</p>
  
  <p>(a) Give an O(|V |^3) to find a triangle if one exists. </p>
  
  <p>(b) Improve
  your algorithm to run in time O(|V |·|E|). You may assume |V | ≤ |E|.</p>
  
  <p>Observe that these bounds gives you time to convert between the
  adjacency matrix and adjacency list representations of G.</p>
</blockquote>

<p>Here is my thoughts:</p>

<p>(a) If the graph is given as an adjacency list, I can convert the list to matrix by O(|V|^2). then I do:</p>

<pre><code>for (int i = 0;i &lt; n;i++) 
   for (int j = i+1;j &lt; n;j++) 
   if (matrix[i][j] == 1) 
      for (int k = j+1;k &lt; n;k++) 
         if (matrix[i][k] == 1 &amp;&amp; matrix[j][k] == 1)
             return true;
</code></pre>

<p>This should give a O(|V|^3) to test the triangle.</p>

<p>(b) My first intuitive is that if the graph is given as an adjacency list, then I will do a bfs. Whenever a cross edge is found, for example, <code>if y-x is a cross edge</code>, then i will <code>check whether parent[y] == parent[x], if true, then a triangle is found</code>.</p>

<p>Could anyone tell me whether my thinking is correct or not?</p>

<p>Also for this (b), I am not sure its complexity. Should it be O(|V| + |E|), right?</p>

<p>How can I do it in O(|V|*|E|)?</p>