Complexity of the recovery of an adjacency matrix from its square
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$.