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|)?

Single

The first three lines of (a) are iterating over all edges... – Zoology

Since you optimized (a) a bit, the innermost loop runs only if ij is an edge. Thus a more careful analysis gives cost O(V^2) for when ij is a nonedge and O(EV) for when ij is an edge, for a total of O(EV) assuming that E >= V. – Zoology

@ARJUN can you update your link? that seems to be a phishing site now. – Have

Check this C program to find number of triangles inside a graph – Whiny

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!

Radiolucent

could you please tell me whether my solution is also correct? – Single

@JacksonTale: It is not, I added a counter example that shows why. – Radiolucent

This is an exercise from the algorithm design manual right? couldn't we, based on the example of page 173, modify process_edge and have if (discovered[y] && parent[parent[x]] == y) ? – Bottali

@antonis_wrx I've done much same as you and I think your answer is correct. – Apogee

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))!

Tacho

Cool answer;but..! I am working on it but I cannot get how you manage to find the all 3rd nodes in O(V). is O(V) for each non-zero entry? then it's O(V^3) for the whole matrix tho.. as you need to spend O(V) for possibly each entry of the matrix. If not, then how do you manage that? can you please add some explanation to the answer? thanks – Zinck

@Zinck You know A-B and A-?-B. Intersecting the neighbors of A and B to find that common element takes at most O(V) time. – Tacho

so it's O(V) for only A-?-B. and then for every triangle you need to do so... so overall it's not O(V) and is something above O(V^2). am I right? – Zinck

@Zinck You only have to do one triangle. That was the purpose of looking for entries where the adjacency matrix and its square both had a 1. – Tacho

why "one" triangle? for any coinciding non-zero element you need to find the 3rd node, don't you? – Zinck

Oh pardon, we are looking for a single triangle... but I actually want to find all the triangles... any thoughts on that problem? – Zinck

Answer 3

Here is what I think :

The origianl BFS solution is incorrect as pointed above. But we can modify the DFS. Assign numbers to the nodes visited as we visit each vertex in the DFS. Now, if we reach a vertex( in the question I saw cross edges, there are none in an undirected graph), we check its adjacency list and suppose one vertex is discovered(but not processed, cannot happen), then we check its number. If the difference is 2 then there is a cycle of length 3.

Dallapiccola

Answer 4

I really like the matrix multiplication solution discussed in this blog post.

Let a = the adjacency matrix

• The adjacencies in a*a (a2) matrix multiplied are the numbers of 2-length paths
• The adjacencies in a2*a matrix multiplied are the numbers of 3-length paths

The problem is, matrix multiplication is slow... However, you can use GPGPU to perform matrix multiplication and can have a performant solution on modern architectures that include a GPU.

Woodchuck

You linked to the wrong thing. The link points at this question instead of a blog post. – Tacho

Answer 5

Solving this using DFS: (Although the solution is discussed above I thought to give a clear explaination using DFS)

Cycle detection

• During DFS, we can detect cycles if we encounter an edge(u, v) where v was previously discovered but not processed (i.e it's an ancestor of u).

Verifying cycle is triangular

• Whenever a cycle is found during processing an edge(u, v), it is considered a triangular cycle if and only if there exists a vertex that has edges to both u and v. This criterion indicates the presence of a cycle of length 3 in the graph.

Time Complexity O(|V|·|E|):

Nerta