# Find a graph when given length-k paths?

I have an undirected connected graph $$G$$ and I have a matrix $$S^{(k)}$$ were $$S^{(k)}_{i,j}=1$$ if there is a length-$$k$$ path between $$i$$ and $$j$$ and 0 otherwise. Now, $$S^{(1)}$$ is then simply the adjacency matrix, which uniquely defines my graph. Is it possible to compute a graph (not necessarily unique) $$G$$ from $$S^{(2)}$$ or any other $$S^{(k)}$$, $$k>1$$?

• There are non-complete graphs where each pair of vertices is connected with a length 2 path. – Ilya Bogdanov Nov 30 '18 at 15:46
• Also, if in a graph of 3 vertices $S^{(2)}_{12}=S^{(2)}_{13}=1$, then necessarily $S^{(2)}_{23}=1$, so there are non-trivial restrictions. Should we understand the question as "Assuming that $S^{(k)}$ is feasible, how to find an underlying graph efficiently?" instead? – fedja Nov 30 '18 at 20:55
• Yes, "how to find efficiently", ideally in polynomial time, but I would of course be interested in approximate solutions and inefficient methods that might point the way to better avenues. – Eric J Dec 1 '18 at 0:11
• Ilya said that $S^{(2)}$ might tell you nothing about $G$. – Dima Pasechnik Dec 1 '18 at 20:13
• @DimaPasechnik It might also tell you something, correct? I can see "remove one edge from a complete graph" resulting in the same $S^{(2)}$ regardless of the edge removed, but this seems like a pathological case? – Eric J Dec 1 '18 at 20:38