I have a finite automaton with these properties: Contains cycles It\'s a directe

Question

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.

Explanation / Answer

This seems to be a difficult problem. For undirected graphs, this is known as "dynamic connectivity". You can see slides describing an O(log2n) 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.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.