Cub11k's BIU Notes

Algorithms-1 09

6 min read

Reporting triangles in a graph

The goal is to return all triangles in a graph, that is, all triplets such that

The first algorithm to achieve this is a simple triple nested loop, with runtime of

The second algorithm will prove that this simple iteration is not the most efficient. The idea behind it is that first algorithm completely ignores number of edges and will always iterate through all vertices

Note that order of loops doesn’t matter, we can first iterate over vertices or over edges Runtime of this algorithm is which is in the worst case

The third algorithm relies on the fact that triangles with edge can only be formed with a third vertex being a neighbor of both

Note that if the graph is represented via adjacency lists and vertices in all lists are sorted by some global order, it is possible to compute in time This gives us a runtime of

Lower bound

Note that in the worst case, the graph contains all triangles, and in this case runtime of all three algorithms is That is, this lower bound is present if we consider the number of triangles as a function of only. What if we consider it as a function of two parameters,

One of the cases when all triangles are present is a clique, and the following is true: This gives us a lower bound of or In cases where it is possible to obtain a runtime that is much better than , in particular

Let us partition vertices of the graph into two categories:

Each triangle can than be classified as

  • Light, if it contains no heavy vertices
  • Heavy, if it contains at least one heavy vertex

And the following algorithm is defined:

Hamming distance

As seen in previous practice sessions, computing Hamming distance on small alphabets is most efficient using FFT polynomial multiplication.

However, if the alphabet is large, it is better to use another approach. First option is to consider texts where each character appears at most times, we can count the number of matches using the following algorithm:

Note that it is possible to apply light-heavy classification to the characters in

Graph View