1
$\begingroup$

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

$\endgroup$
7
  • 2
    $\begingroup$ There are non-complete graphs where each pair of vertices is connected with a length 2 path. $\endgroup$ Nov 30, 2018 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, 2018 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, 2018 at 0:11
  • $\begingroup$ Ilya said that $S^{(2)}$ might tell you nothing about $G$. $\endgroup$ Dec 1, 2018 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, 2018 at 20:38

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.