<p>It is known that squares of bipartite graphs can be recognized in polynomial time ( See <a href="http://www.cse.cuhk.edu.hk/~chi/papers/bipartite-roots.pdf" rel="nofollow">this</a>). In general, there is a <a href="http://www.cse.cuhk.edu.hk/~chi/papers/girth.pdf" rel="nofollow">characterization</a> of the complexity of this problem based on the girth of the underlying graph. </p>

<p>Recently there was a optimization <a href="http://arxiv.org/pdf/1310.5469v1.pdf" rel="nofollow">variant</a> 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$.</p>

CC BY-SA 3.0
2015-04-04T18:56:13.487Z
Thanks for the response, but the results you mention are not relevant to this problem - they assume, as in the paper of Motwani and Sudan, that the given matrix is an adjacency matrix and the goal is to find another graph whose adjacency matrix _squared under Boolean matrix multiplication_ is the given matrix.  Whereas in this problem it is not Boolean, but integer matrix multiplication.  In other words, this problem is not about the square root of a graph as they use the term.
Ben Fish
CC BY-SA 3.0
2015-04-05T05:56:38.287Z
@BenFish Oops. Misunderstood your question. For Integer matrices, I don't see any better way than just approximating the square root of the matrix, though I presume you are interested in computing this as the square root of a weighted graph (and I have no idea how to do that)
Nikhil
CC BY-SA 3.0
2015-04-05T20:22:19.660Z
@Nikhil the square root of a matrix is not unique, so doing this doesn't solve the question
Lev Reyzin
CC BY-SA 3.0
2015-04-06T06:37:18.243Z
@LevReyzin You are correct. In general, I think the uniqueness can be characterized from the spectrum of the matrix (maybe they don't provide a necessary and sufficient condition). There are some interesting results known for stochastic matrices -- See http://eprints.ma.man.ac.uk/1241/01/covered/MIMS_ep2009_21.pdf
Nikhil
CC BY-SA 3.0
2015-04-04T10:04:03.853Z
2015-04-04T10:04:03.853Z
Nikhil
<p>If the underlying graph is a sparse, random graph, one can solve the "graph square root" problem in polynomial time; this is also true for weighted graphs. Examples of papers that use this idea are <a href="http://arxiv.org/abs/1112.1831" rel="nofollow">Finding Overlapping Communities in Social Networks</a> and <a href="http://arxiv.org/abs/1310.6343" rel="nofollow">Provable Bounds for Learning Some Deep Representations</a>. Any idea about similar algorithms for graph cube roots, fourth roots etc.? </p>

CC BY-SA 3.0
2015-04-06T17:49:10.620Z
2015-04-06T22:19:06.133Z
2015-04-06T22:19:06.133Z
Pratik
<p>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?</p>

<p>Is the computational complexity of this problem known?</p>

<p>Remarks:</p>

<ul>
<li><p>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$.</p></li>
<li><p>Motwani and Sudan (<a href="http://www.sciencedirect.com/science/article/pii/0166218X94000239">Computing roots of graphs is hard</a>, 1994) and 
Kutz (<a href="http://www.sciencedirect.com/science/article/pii/S0304397504004165">The complexity of Boolean matrix root computation</a>, 2004) show similar but distinct problems from this one are NP-hard - they consider only the square of adjacency matrices under Boolean matrix multiplication.</p></li>
</ul>

CC BY-SA 3.0
2015-04-06T17:02:10.843Z
The problem is equivalent to deciding the existence of $n$ vectors with given pairwise inner products.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-04-06T19:24:43.410Z
Very recently there was a paper addressing this question for _stochastic_ matrices rather than adjacency matrices (http://arxiv.org/abs/1411.7380). The property of being a square in this context is known as _divisibility_ and is shown to be NP-complete in the paper I mentioned.
Māris Ozols
CC BY-SA 3.0
2015-04-06T22:02:04.370Z
@MohammadAl-Turkistany how are they equivalent? The solution to OP's problem requires additional structure than generic vectors (integer valued, certain indices must be zero, etc).
Jeremy Kun
CC BY-SA 3.0
2015-04-28T20:52:59.427Z
This ought to be related to checking if a degree sequence is graphic. Notice that in $A^2$ the diagonal represents the degree sequence and $(A^2)_{ij}$ the number of common neighbours of vertices $i,j$. Thus it is a restriction to the graphic degree sequence problem. No idea how to solve it though.
SamiD
<cc.complexity-theory><graph-theory>
Complexity of the recovery of an adjacency matrix from its square
Ben Fish
# Complexity of the recovery of an adjacency matrix from its square

(Asked by: username_0 on 2015-04-03)

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](http://www.sciencedirect.com/science/article/pii/0166218X94000239), 1994) and
  Kutz ([The complexity of Boolean matrix root computation](http://www.sciencedirect.com/science/article/pii/S0304397504004165), 2004) show similar but distinct problems from this one are NP-hard - they consider only the square of adjacency matrices under Boolean matrix multiplication.

**Tags:** cc.complexity-theory, graph-theory
> **Comments:**
> **username_1**: The problem is equivalent to deciding the existence of $n$ vectors with given pairwise inner products.  
> **username_2**: Very recently there was a paper addressing this question for _stochastic_ matrices rather than adjacency matrices (http://arxiv.org/abs/1411.7380). The property of being a square in this context is known as _divisibility_ and is shown to be NP-complete in the paper I mentioned.  
> **username_3**: @MohammadAl-Turkistany how are they equivalent? The solution to OP's problem requires additional structure than generic vectors (integer valued, certain indices must be zero, etc).  
> **username_4**: This ought to be related to checking if a degree sequence is graphic. Notice that in $A^2$ the diagonal represents the degree sequence and $(A^2)_{ij}$ the number of common neighbours of vertices $i,j$. Thus it is a restriction to the graphic degree sequence problem. No idea how to solve it though.  

---

## 2 answers

### Answer by username_5 on 2015-04-04. Score: 3

It is known that squares of bipartite graphs can be recognized in polynomial time ( See [this](http://www.cse.cuhk.edu.hk/~chi/papers/bipartite-roots.pdf)). In general, there is a [characterization](http://www.cse.cuhk.edu.hk/~chi/papers/girth.pdf) of the complexity of this problem based on the girth of the underlying graph.

Recently there was a optimization [variant](http://arxiv.org/pdf/1310.5469v1.pdf) 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$.

> **Comments:**
> **username_0**: Thanks for the response, but the results you mention are not relevant to this problem - they assume, as in the paper of Motwani and Sudan, that the given matrix is an adjacency matrix and the goal is to find another graph whose adjacency matrix _squared under Boolean matrix multiplication_ is the given matrix.  Whereas in this problem it is not Boolean, but integer matrix multiplication.  In other words, this problem is not about the square root of a graph as they use the term.  
> **username_5**: @BenFish Oops. Misunderstood your question. For Integer matrices, I don't see any better way than just approximating the square root of the matrix, though I presume you are interested in computing this as the square root of a weighted graph (and I have no idea how to do that)  
> **username_6**: @Nikhil the square root of a matrix is not unique, so doing this doesn't solve the question  
> **username_5**: @LevReyzin You are correct. In general, I think the uniqueness can be characterized from the spectrum of the matrix (maybe they don't provide a necessary and sufficient condition). There are some interesting results known for stochastic matrices -- See http://eprints.ma.man.ac.uk/1241/01/covered/MIMS_ep2009_21.pdf  

---

### Answer by username_7 on 2015-04-06. Score: 1

If the underlying graph is a sparse, random graph, one can solve the "graph square root" problem in polynomial time; this is also true for weighted graphs. Examples of papers that use this idea are [Finding Overlapping Communities in Social Networks](http://arxiv.org/abs/1112.1831) and [Provable Bounds for Learning Some Deep Representations](http://arxiv.org/abs/1310.6343). Any idea about similar algorithms for graph cube roots, fourth roots etc.?


---

