Complexity of the recovery of an adjacency matrix from its square I am interested in the following problem:  Given an $n\times n$ matrix, is there an undirected graph on $n$ vertices whose adjacency matrix squared is that matrix?

Is the computational complexity of this problem known?

Remarks:


Of course this can also be phrased as a search problem, where you are given the matrix $A^2$ for $A$ an adjacency matrix of an undirected graph and the problem is to find any adjacency matrix (of an undirected graph) $B$ such that $B^2 = A^2$.
Motwani and Sudan (Computing roots of graphs is hard, 1994) and 
Kutz (The complexity of Boolean matrix root computation, 2004) show similar but distinct problems from this one are NP-hard - they consider only the square of adjacency matrices under Boolean matrix multiplication.
It is known that squares of bipartite graphs can be recognized in polynomial time ( See this). In general, there is a characterization of the complexity of this problem based on the girth of the underlying graph. 

Recently there was a optimization variant studied, which gives FPT algorithms for the problem when you want to test whether a graph has a square root with at most (respectively at least) $s$ edges for some given integer $s$.