On an algorithm for counting triangles

Question

This is regarding the complexity of an algorithm for counting triangles in an undirected graph which was suggested in a document I came across.

(Link - https://www.cs.cmu.edu/~15750/notes/lec1.pdf)

Suppose the graph has $m$ edges and $n$ vertices. The algorithm goes as follows: sort the vertices in increasing order of degree ($v_1 \cdots v_n$) and scan them beginning at the lowest degree vertex. When you are at vertex $v_i$, only scan pairs of edges (which could potentially be triangles) of the form $(\{v_i,v_j\},\{v_i, v_k\})$ where $j,k>i$. The document says that the time complexity of this algorithm is $O(m^{3/2})$. There’s no proof in the document and I’ve been trying to prove it but have not been able to. How do you show this?

Answer 1

Consider this simpler algorithm:

Pick an $\alpha \in \mathbb{R}_{>0}$ and partition the vertices of $G$ in two sets $A = \{u: d_u \leq a\}$ and $B=\{u: d_u > a\}$. Perform the following two subroutines:

• Iterate through all triplets $u, v, w \in B$ and check if they form a triangle
• For each $u\in A$ check for all pairs of neighbors $v, w$ if $\{u,v,w\}$ forms a triangle

The time complexity will be $$|B|^3 + \sum_{u\in A}\binom{d_u}{2} \leq |B|^3+\sum_{u\in A}d_u^2\leq |B|^3+\alpha\sum_{u\in V}d_u=|B|^3+2\alpha m$$

Furthermore, notice that $|B|\cdot \alpha \leq \sum_{u\in B}d_u\leq 2m$ and so $|B|\leq \frac{2m}{a}$. Choosing $\alpha = O(\sqrt{m})$ gives the desired complexity.

This logic is easily incorporated in the modified algorithm at hand. It is worth mentioning though that for this algorithm to work you require access both to the adjacency list of the graph as well as an oracle that tells you whether any edge $\{u,v\}$ exists in $O(1)$ time.