3
$\begingroup$

Given an undirected graph, how would one go about calculating the number of squares in the graph? That is, a square is a cycle of length 4.

I know that it is possible to count the number of triangles (cycles with length 3) in polynomial time. Is it possible to calculate the number of squares in polynomial time as well, and how would one go about doing this?

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ What have you tried? Did you look at the algorithm for counting triangles? Maybe you can generalize it to squares. $\endgroup$ – adrianN Oct 18 '16 at 9:58
6
$\begingroup$

There is a simple $O(n^4)$-time algorithm which I will let you discover yourself. A better algorithm follows from the following formula for the number of squares: $$ \operatorname{Tr} (A^4) - \sum_i d_i^2, $$ where $A$ is the adjacency matrix and $d_i$ is the degree of the $i$th vertex. Using this formula you can compute the number of squares in $O(n^\omega)$, where $\omega < 2.373$ is the matrix multiplication constant.

|cite|improve this answer
$\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.