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

  • 2
    $\begingroup$ There are non-complete 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 non-trivial 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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.