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?
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: $$ \frac{1}{8} \left( \operatorname{Tr} (A^4) - 2\sum_i d_i^2 + \sum_i d_i \right), $$ 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.
To prove the formula, let us expand $\operatorname{Tr} (A^4)$: $$ \operatorname{Tr}(A^4) = \sum_{i,j,k,\ell} A_{ij} A_{jk} A_{k\ell} A_{\ell i} = \sum_{\substack{i,j,k,\ell \\ \text{all different}}} A_{ij} A_{jk} A_{k\ell} A_{\ell i} + R, $$ where $R$ consists of bad terms that we would like to get rid of.
Let's see what these terms look like. Since the diagonal of $A$ consists of zeroes, we have $i \neq j \neq k \neq \ell \neq i$. Hence what could go wrong is $i = k$ or $j = \ell$, or both. Therefore $$ R = \underbrace{\sum_{\substack{i,j,\ell \\ i \neq j \neq \ell \neq i}} A_{ij} A_{ji} A_{i\ell} A_{\ell i}}_{R_1} + \underbrace{\sum_{\substack{i,j,k \\ i \neq j \neq k \neq i}} A_{ij} A_{jk} A_{kj} A_{ji}}_{R_2} + \underbrace{\sum_{\substack{i,j \\ i \neq j}} A_{ij} A_{ji} A_{ij} A_{ji}}_{R_3}. $$ It is not hard to check that $$ \begin{align*} R_1 &= \sum_i d_i (d_i - 1), \\ R_2 &= \sum_j d_j (d_j - 1), \\ R_3 &= \sum_i d_i \end{align*} $$ It follows that $$ \sum_{\substack{i,j,k,\ell \\ \text{all different}}} A_{ij} A_{jk} A_{k\ell} A_{\ell i} = \operatorname{Tr}(A^4) - 2 \sum_i d_i^2 + \sum_i d_i $$ The sum on the left counts each square precisely eight times, leading to the formula stated above.
As an example, consider the square graph on four vertices $1,2,3,4$, which satisfy $d_1 = d_2 = d_3 = d_4 = 2$. Then $$\operatorname{Tr}(A^4) - 2 \sum_i d_i^2 + \sum_i d_i = 32 - 2 \cdot 4 \cdot 2^2 + 4 \cdot 2 = 8, $$ and indeed there is a single square.
Another example is the complete graph on $n$ vertices. The eigenvalues are $n-1,-1,\ldots,-1$, and so $$ \operatorname{Tr}(A^4) - 2 \sum_i d_i^2 + \sum_i d_i = (n-1)^4 + (n-1) - 2n(n-1)^2 + n(n-1) = n(n-1)(n-2)(n-3) = n^{\underline{4}}, $$ and indeed the number of squares is $n^{\underline{4}}/8$.
I'm not sure where Yuval got his formula from but when trying to replicate it I got a bit lost so I will share with you what I found. You can naively calculate the number of 4 cycles using $$\text{Tr}(A^4)=\sum_{ijkl}A_{ij}A_{jk}A_{kl}A_{li}$$ which you can read as "test if vertex $i$ is connected to vertex $j$, vertex $j$ is connected to vertex $k$ etc." But there is an issue, consider the following graph:
1--2
| |
4--3
In addition to counting the square (1-2-3-4) the naive algorithm will also count 2 cycles (1-2-1-2). If you don't want this you can add a term with a Kronecker Delta to ensure that vertex $i$ is distinct from vertex $k$ and node $j$ is distinct from vertex $l$. $$\sum_{ijkl}A_{ij}A_{jk}A_{kl}A_{li}(1-\delta_{ik})(1-\delta_{jl})$$ You can expand this and use that $A_{ij}^2=A_{ij}$, $ A_{ij}=A_{ji}$ and $d_i=\sum_jA_{ij}$. After simplifying this gives $$\text{Tr}(A^4)-2\sum_id_i^2+\sum_i d_i$$ I'm relatively sure this is correct. As a bonus you can also consider "pure squares", i.e. exclude squares with cross links:
1--2
|\ |
| \|
4--3
You can exclude this by adding two terms that don't count cross links. $$\sum_{ijkl}A_{ij}A_{jk}A_{kl}A_{li}(1-\delta_{ik})(1-\delta_{jl})(1-A_{ik})(1-A_{jl})$$ But I don't know if it's possible to simplify this and as it is written right now this is really slow to compute. If you divide this final expression by $8$ you get exactly the number of squares in the graph. Each vertex that's in a square accounts for two squares (one clockwise, one anti-clockwise) and for four vertices this gives $2*4=8$.
