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.
For instance, if the graph is a tree, there is an efficient solution: do a DFS once, and store the pre and post numbers at every node; then each ancestor query can be answered by testing for interval containment.
In a more general graph, this is known as a reachability query, and there are algorithms in the literature for this problem. See, e.g., https://cs.stackexchange.com/a/41432/755 and https://cstheory.stackexchange.com/q/25298/5038 and https://cstheory.stackexchange.com/q/21503/5038. Without loss of generality, you can assume the graph is a dag (if not, first compute all strongly connected components in linear time, and label each vertex with its scc; then you only need to consider the dag of scc's).
