# Algorithm to decide whether two vertices are ancestors/descendants of each other

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?

DFS only requires $O(|V|+|E|)$ time, not $O(|V| \cdot |E|)$ time. (Same for BFS.) Therefore, DFS is an efficient solution for this problem. This is about as efficient as you hope for, as it takes that much time just to read the entire input -- you can't hope for something faster.
The problem becomes more interesting if we're provided the graph $G$ and allowed to do some precomputation, and then want to answer many queries efficiently. This is considerably more challenging, but in some cases, it is possible to do better than running a DFS from scratch every time you receive a new query.