Find an O(n) algorithm that returns all interesting vertices of the graph

0
votes

Problem : A directed graph G with n vertices and a special vertex u is provided. We call a vertex v ‘interesting’ if there is a path from v to a vertex w such that there is a cycle containing the vertices w and u. Write an O(n) time algorithm which takes G (the whole graph) and the node u as input and returns all the interesting vertices.

Ineffiecient Algorithm : My idea initially was to consider the node u and compute all the cycles that contain u. (This itself seems like traversing through the nodes using DFS and then forward-tracking as well when you encounter a visited node) Now from each vertex on these cycles we can compute the number of nodes on the graph that do not belong to the cycle(s) but is connected with each particular vertex w not equal to u on a cycle. Add all these values to get the desired answer. This isn't an O(n) algorithm.

1
algorithmgraph
How is G represented? (If it's represented as an adjacency list, then this is clearly impossible, because there can be more than O(n) edges, so just reading the adjacency list can take more than O(n) time. I suspect that something similar would be true of any representation of G, but a concrete description would help confirm that.) - ruakh
@ruakh I'm not really sure of that. I have copied the question without any modification whatsoever. Let's not assume that it's listed as an adjacency list then. - Mathejunior
Could you please clarify the "there is a path from v to a vertex w such that there is a cycle containing the vertices w and u" part? So there is a path from v to w. What does it have to do with the cycle containing w and u? Should the cycle be part of the path? - Nico Schertler
@NicoSchertler so a vertex v is interesting when v and another vertex w are connected in such a way that w and u are two nodes of some existing cycle in the graph. - Mathejunior
@NicoSchertler: I agree that it's worded very confusingly, but I think it makes sense: v is "interesting" if there exists a vertex w such that there's a path from v to w, and a cycle containing both w and u. - ruakh

1 Answers

3
votes

There are two cases:

  • If there are no cycles containing u, then no vertex can be "interesting".
  • If there are any cycles containing u, then a vertex v is "interesting" if and only if there's a path from v to u. (We don't need to worry about the w in the problem description, because if a cycle contains two vertices u and w, then any path that ends at u can be extended to end at w and vice versa.)

So, the most efficient algorithm would be as follows:

  1. Using DFS, determine if u is in a cycle. (We don't need to find all cycles; we just need to determine whether there are any.)
  2. Using DFS in the "reverse" direction, find all vertices from which u is reachable.

DFS requires O(|V| + |E|) time, which is greater than O(n) = O(|V|) unless |E| is in O(n); but then, there's no way to even read in the entire graph definition in less than |E| time, so this is unavoidable. Whoever gave you this question must not have really thought this through.