Check whether an undirected graph contains a simple cycle of length four using the "Squares" method

The following problem is exercise 4.3 of the book "Algorithms" by S. Dasgupta, C. Papadimitriou, and U. Vazirani.

Squares. Design and analyze an algorithm that takes as input an undirected graph $G = (V,E)$ and determines whether $G$ contains a simple cycle (i.e., a cycle which does not intersect itself) of length four in $O(|V|^{3})$ time.

This can be solved by checking for each pair of vertices $u$ and $v$ whether they share at least two common neighbors; see the answer.

However, in the book, the authors gave a single-word hint: Squares.

Following the hint, I square the adjacency matrix $M$ of $G$ twice (i.e., $M \to M^2 \to M^4$) and check whether $M^4[i][i]$ is true for some $i$. But this attempt fails because it produces "false positives" by treating $a-b-a-b-a$ or $a-b-c-b-a$ as cycles of length four.

How to fix the "false positives" in the squaring method above?

Square $$M$$, to get $$M^2$$. Write $$M^2 = D + P$$, where $$D$$ is the diagonal part (all non-diagonal entries are zero) and $$P$$ is the non-diagonal part (all diagonal entries are zero).

Compute $$Q=P^2$$. Note that $$Q_{aa}$$ counts the number of ways to start at $$a$$ and end at $$a$$, excluding cycles of the form $$ababa$$ and $$abaca$$ etc., but not avoiding cycles of the form $$abcba$$.

Now compute $$R = MDM - D$$. Note that $$R_{aa}$$ counts the number of cycles of the form $$abcba$$ where $$c \ne a$$.

Let $$S = Q-R$$. We find that $$S_{aa}$$ counts the number of simple 4-cycles that start and end at $$a$$. Thus, the graph has a simple 4-cycle if and only if one or more of the diagonal entries of $$S$$ are non-zero.

• Note that $R_{aa}$ also counts cycles of the form $ababa$. Jun 20 '20 at 13:52
• Therefore you need to take $R = MDM - D$, or alternatively $S = Q - R + D$. Jun 20 '20 at 13:53
• @YuvalFilmus, thank you!
– D.W.
Jun 20 '20 at 19:34

Here is a slightly different (but equivalent) approach. The entry $(M^4)_{ii}$ computes the number of walks $i\to j\to k\to \ell\to i$. These are either squares (if all of $i,j,k,\ell$ are different), or of the form $i \to j \to i \to \ell \to i$ (possibly $j = \ell$), or of the form $i \to j \to k \to j \to i$. There are exactly $d(i)^2$ of the second type (here $d(i)$ is the degree of $i$, equal to $(M^2)_{ii}$) and exactly $\sum_{k \neq i} (M^2)_{ik}^2$ of the third type. So $(M^4)_{ii} > \sum_k (M^2)_{ik}^2$ iff there is a square through $i$.

Note that this actually gives an $O(|V|^\omega)$ algorithm for detecting squares, where $\omega$ is the matrix multiplication constant (the best known bound, $\omega < 2.373$, is due to Le Gall).