Search code examples
algorithmgraphruntimebig-onotation

Find a triangle in a graph using an algorithm with a specific run time

I need to find an algorithm that finds triangular cycles in an undirected graph. The runtime of the algorithm should be n^2,81

I really do not know how I can achieve this. Would be great if anyone could help!

Thanks!

Solution

  • The algorithm you search is matrix multiplication. Multiply adjacency matrix with itself three times and search for non zero entrees in the main diagonal. matrix multiplication is O(N^2.81): https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm

    EDIT:

    Recall that in the ith row of the adjacency matrix there will be '1' for each vertex connected to i, the same goes for the column.

    When you multiply the matrix with itself, (M^2)ij = sum (Mik*Mkj). in other words (M^2)ij is the number of 2-edge paths from i to j.

    Now if you multiply again to get M^3, in every cell (M^3)ij there will be the number of 3-edge paths from i to j. so in the main diagonal (M^3)ii there will be the number of 3-edge paths from i to i, a triangle.