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.