Is there an algorithm that performs the following:
Input: A directed graph and two vertices within that graph
Output: Whether one of the two vertices is the ancestor of the other
For example, in this graph:
A is an ancestor of D. B is neither the ancestor nor the descendant of C.
The best I can think of doing is performing a DFS/BFS from each of the two input vertices and seeing if either search includes the other vertex. This takes O(|V| + |E|) time. Is there a well-known, faster algorithm?