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$?
1

2$\begingroup$ There are noncomplete graphs where each pair of vertices is connected with a length 2 path. $\endgroup$ – Ilya Bogdanov Nov 30 '18 at 15:46

$\begingroup$ Also, if in a graph of 3 vertices $S^{(2)}_{12}=S^{(2)}_{13}=1$, then necessarily $S^{(2)}_{23}=1$, so there are nontrivial restrictions. Should we understand the question as "Assuming that $S^{(k)}$ is feasible, how to find an underlying graph efficiently?" instead? $\endgroup$ – fedja Nov 30 '18 at 20:55

$\begingroup$ 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. $\endgroup$ – Eric J Dec 1 '18 at 0:11

$\begingroup$ Ilya said that $S^{(2)}$ might tell you nothing about $G$. $\endgroup$ – Dima Pasechnik Dec 1 '18 at 20:13

$\begingroup$ @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? $\endgroup$ – Eric J Dec 1 '18 at 20:38