Algorithm to decide whether two vertices are ancestors/descendants of each other
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).