How to find a triangle inside a graph?

Question

Here is an exercise in the Algorithm Design Manual.

Consider the problem of determining whether a given undirected graph G = (V, E) contains a triangle or cycle of length 3.

(a) Give an O(|V |^3) to find a triangle if one exists.

(b) Improve your algorithm to run in time O(|V |·|E|). You may assume |V | ≤ |E|.

Observe that these bounds gives you time to convert between the adjacency matrix and adjacency list representations of G.

Here is my thoughts:

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

for (int i = 0;i < n;i++)     for (int j = i+1;j < n;j++)     if (matrix[i][j] == 1)        for (int k = j+1;k < n;k++)           if (matrix[i][k] == 1 && matrix[j][k] == 1)              return true; 

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

(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, if y-x is a cross edge, then i will check whether parent[y] == parent[x], if true, then a triangle is found.

Could anyone tell me whether my thinking is correct or not?

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

How can I do it in O(|V|*|E|)?

Answer 1

A possible O(|V||E|) solution, is the same idea of the brute-force in (a):

for each edge (u, v):   for each vertex w:      if (v, w) is an edge and (w, u) is an edge:           return true return false 

check all edges, and not all vertices pairs - with another vertex that forms a triangle - it is enough information to determine if the edge and vertex form a feasible solution.

Counter example to BFS solution:

       A      / | \     /  |  \    B   C   D    |   |   |    |   |   |    F---G---H    |       |    ---------     (F, H) is also an edge 

Note that father[F] != father[G] != father[H], thus the algorithm will return false - but nevertheless, (F, G, H) is a feasible solution!

Answer 2

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.

A naive matrix multiplication takes time O(n^3), but there are fast matrix multiplication algorithms that do better. One of the best known is the Coppersmith-Winograd algorithm, which runs in O(n^2.4) time. That means the algorithm goes something like:

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

So overall this takes O(V^2.4) 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 that amit explains in their answer to improve that to O(V min(V^1.4, E)).

Here's a paper that goes more in-depth into the problem.

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 O(V^2) or O(V^2 log(V)) or something like that. But if quantum computers work out, we'll be able to do even better than that (something like O(V^1.3))!