# Space complexity for connectivity problem with given graph diameter

Given $(G,D,d)$, a graph, the graph diameter and the maximum outdegree of the graph. Verify that $G$ is strongly connected in $O(D\log d + \log n)$ space complexity.

I thought about using the $STCON$ problem for the whole nodes in the graph, but that will yield a space complexity of $O(n^2 \log^2n)$ (according to Savitch's theorem).

Then I thought about using a DFS traversal (it will be needed twice, actually), but I don't know how to prove it's space complexity.

The idea here is to use a reachability-based approach. Given $u, v \in V$ we ask ourselves whether $u$ reaches $v$ in $G$. By definition, there exists a path that connects $u$ and $v$ if and only if there exists a path of length at most $D$; there are at most $d^D$ such paths.
Loop over all pairs of nodes and all paths to answer the original question. The total space required by this procedure is $\left \lceil \log(n^2d^D) \right \rceil$ plus a constant amount.
• Pretty straightforward. In a way, you're saying one need to perform $n^2$ DFSs where each DFS has a space complexity of $\log{(d^D)}$, am I correct? Mar 22 '18 at 11:14