1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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$. Note that $R_{aa}$ counts the number of cycles of the form $abcba$.

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.

$\endgroup$
3
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.