# What time complexity is a reachability algorithm?

I've read there are ways you can determine all reachable pairs using Strongly Connected Components. But, I want to calculate all reachable nodes on the fly - so I don't have to store a massive reachability matrix in RAM. What sort of time complexity would be possible for an algorithm to calculate all reachable nodes in a directed graph, from a single node?

Here's a naive algorithm I came up with, I'm not sure of the time complexity of this. $$O(V!)$$?

It seems to have an $$O(V)$$ spacial complexity though.

I've read about the Bellman-Ford algorithm with a time complexity of $$O(EV)$$ which is essentially $$O(V^3)$$ and the Floyd-Warshall algorithm which is $$O(V^3)$$. They require $$O(V)$$ and $$O(V^2)$$ space complexity, respectively.

The problem is only inputs can be determined in constant time. So, one would have to find (in $$O(V)$$ time) all outputs for a particular node. What I actually did in my solution is invert the graph using a similar technique, before running DFS. But I don't know if this is optimal... Also, due to a copy of the graph being stored in memory, my solution has a spacial complexity worse than the bellman-ford algorithm. If this time complexity is also worse, I may as well use bellman fords algorithm

• I don't understand what you mean by "inputs" or "neuron".
– D.W.
Apr 30, 2020 at 7:42
• The representation of the directed graph in memory is recursive, each node has a set of inputs.
– Tobi
Apr 30, 2020 at 7:44
• Rather than responding in the comments, please edit the question to clarify. Please either avoid using $n$, or define what it represents in the question. I see the question still uses $n$. I don't know what it means to say that the representation is recursive, and I still don't know what it means for a node to have inputs. Do you mean incoming edges?
– D.W.
Apr 30, 2020 at 7:47

You can calculate all reachable nodes in $$O(V+E)$$ time and $$O(V)$$ space, using DFS on the fly.

If you want to use less than $$O(V)$$ space, then the problem becomes much more challenging. I recommend looking at how the SPIN model checker works. See https://en.wikipedia.org/wiki/Bitstate_hashing. Even then, the space required is probably still $$O(V)$$, just with a lower constant factor.

• DFS works if you can traverse a nodes outputs, in constant time. As explained, only the inputs can be traversed (In constant time)
– Tobi
Apr 30, 2020 at 7:36
• Do you think this is optimal?
– Tobi
Apr 30, 2020 at 7:39
• Inversion of a graph (to prepare for DFS) works in $O(E)$ time, and DFS obviously works in $O(V+E)$. The spacial complexity however is now $O(V^2)$ as an inverted graph is (briefly) stored in memory.
– Tobi
Apr 30, 2020 at 7:47