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.

  • $\begingroup$ 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? $\endgroup$ – galah92 Mar 22 '18 at 11:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.