Using Strongly Connected Component Algo to Verify Peak Availability

Question

I would like to see if a given vertex, say, V0, is reachable by all other vertices in the graph G.
I know that I can just go through each vertex on the graph and make BFS / DFS to see if V0 is available.
However, this seems very inefficient.

I was wondering if I find the SCC algorithm on the graph, and if v0 is part of the whole scc, then I can safely conclude that v0 is reachable by all the vertices? That would be great, because the cost of SCC is only O (V + E) with Tarjan and checking that v0 is part of scc will also cost linear time.

I would think that makes sense, because SCC means that the vertices are reachable. Any confirmation of this logic?

or any effective approach to this?

Answer 1

V0 may not belong to SCC, but still be accessible to all other vertices. For example, the vertex d in the diagram is reachable by all other vertices, but the only nontrivial SCC contains the vertices a , b , c and does not contain the vertices d .

To check if V0 is accessible by all other vertices, you can change the direction of each edge (in linear time), then use BFS / DFS starting from V0 to check if any other vertex from V0 is available (also in linear time).

Answer 2

Let's name the vertex from which all other vertices are accessible, vista vertex. If the graph has a vista vertex, then it should have only one SCC source (since two SCC sources are inaccessible from each other), which should contain the perspective vertex (if it is in any other SCC, there is no way from the vista vertex to the original SCC). Moreover, in this case, each vertex in the original SCC will be the peak of the perspective. Then the algorithm is simply used for DFS, starting at any node and marking the top using the highest possible time finish. This should be in the original SCC. Now we run DFS again from this to check if we can reach all nodes. Because the algorithm simply uses decomposition in SCC and DFS, the runtime is linear. This algorithm is correct. Note that a vista vertex will exist if and only if there is only one SCC source. Any vertex in the source SCC is available only for other vertices in the same SCC, so no vertex can reach the vertices in two different SCC sources. In addition, if there is one SCC source, any vertex in this SCC is vista vertex, since all of them are available for each Other. Please note that DFS, which runs in any particular SCC, will not be completed until all SCCs that were accessible from it. This means that the last node ends in SCC which is inaccessible from any other SCC, that is, from the SCC source. Thus, in the first part of our algorithm, we find the node in the original SCC. Performing DFS, we will correctly determine whether it is a vertex vertex, and if it is not a vertex, we know that it does not have our graph.