18

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.

Lev Reyzin
  • 11,968
  • 13
  • 63
  • 103
Ben Fish
  • 181
  • 4
  • The problem is equivalent to deciding the existence of $n$ vectors with given pairwise inner products. – Mohammad Al-Turkistany Apr 06 '15 at 17:02
  • 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. – Māris Ozols Apr 06 '15 at 19:24
  • 2
    @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 Apr 06 '15 at 22:02
  • 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 Apr 28 '15 at 20:52

2 Answers2

3

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$.

Nikhil
  • 1,354
  • 10
  • 23
  • 7
    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 Apr 04 '15 at 18:56
  • @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 Apr 05 '15 at 05:56
  • @Nikhil the square root of a matrix is not unique, so doing this doesn't solve the question – Lev Reyzin Apr 05 '15 at 20:22
  • @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 Apr 06 '15 at 06:37
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 and Provable Bounds for Learning Some Deep Representations. Any idea about similar algorithms for graph cube roots, fourth roots etc.?

Pratik
  • 11
  • 4