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$?
$\begingroup$
$\endgroup$
7
-
2$\begingroup$ There are non-complete graphs where each pair of vertices is connected with a length 2 path. $\endgroup$– Ilya BogdanovNov 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$– fedjaNov 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 JDec 1, 2018 at 0:11
-
$\begingroup$ Ilya said that $S^{(2)}$ might tell you nothing about $G$. $\endgroup$– Dima PasechnikDec 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 JDec 1, 2018 at 20:38
|
Show 2 more comments