What is the optimal solution to prove the reachbility of a node from the root? I have a finite automaton with these properties:


Contains cycles
It's a directed graph
All the states/nodes are initialy reachable from the initial state
It has final states but I guess it isn't relevant for my issue
It's a random generated automaton, and the generation isn't meant to satisfy properties like strongly connected components or connected components 


Let's suppose I have to delete an edge. 

I need to know if there's a way to prove that the reached state by this edge is still reachable from the initial state without using a classical search (DFS or BFS); obviously, if there is any.
This seems to be a difficult problem. For undirected graphs, this is known as "dynamic connectivity". You can see slides describing an $O(\log^2 n)$ algorithm, or the paper itself. For directed graphs, there is an algorithm no better than DFS described in this paper (the algorithm is better than DFS if you are making several connectivity queries each time). A paper by Pătraşcu gives evidence that polylogarithmic update time isn't possible for directed graphs.