Given two vertices s,t in a directed graph, is there a vertex x such that xs and xt are paths?

Question

I am curious of knowing of an efficient algorithm for the problem:

Given two vertices s,t in a directed graph, is there a vertex x such that xs and xtare paths?

I can of course do a BFS from each node of the graph resulting in a quadratic time algorithm.

Or I can reverse all the edges of the graph, do a BFS from s store all reachable vertices in a hashtable, do a BFS from t and check for each reachable vertex if it is in the table, ifso, I found x. While the running time is linear, the extra space requirement is ugly.

Is there any elegant O(E + V) time algorithm for this problem?

Answer 1

tl;dr I wrote some solution but realized it is not perfect. Since I didn't want all this typing to go waste I figured I might post my observations here rather than splitting them in the comments.

I think that the problem can be solved for any arbitrary $s,t$ and $x$ in $\mathcal{O}(V+ E)$. In fact we can extend the problem to answer $Q$ queries of the form $(s,t,x)$ with $\mathcal{O}(V+E)$ pre processing and $\mathcal{O}(1)$ per query. I am having trouble completing step 6, but I am pretty sure that it can be done. Someone in the comments may know.

1. Find all strongly connected components (scc) of the graph using Kosarjau's or Tarjans algorithm. This step will take $\mathcal{O}(V+E)$ time.
2. Using a hash table, you can check if two nodes belong to the same stongly connected component in $\mathcal{O}(1)$ time.
3. If two nodes $u$ and $v$ belong to the same strongly connected component, then there exists paths both from $u$ to $v$ and $v$ to $u$.
4. Now what remains to be checked is if two nodes $u$ and $v$ do not belong to the same strongly connected component, does there still exist a path from $u$ to $v$.
5. We will modify the given graph $G$ to a new graph $G'$ which we shall call the strongly connected component graph or scc graph for short. In the scc graph, each node corresponds to one strongly connected component in the original graph i.e. we compress all nodes belonging to the same scc to a single node. It can be proven that the scc graph is a Directed Acyclic Graph (DAG for short).
6. Now our task reduces to check if there exists a directed path between $u$ and $v$ in the DAG. Topological sort can give an ordering such that for any path from $u$ to $v$, $u$ will appear before $v$ in the ordering. Thus we can check if index of $u$ in the topologically sorted sequence of vertices is less than that of $v$ in $\mathcal{O}(1)$ but this method also gives false positives and this is where I am stuck.
7. I feel that we can augment step 6 with some additional data to complete the algo. One method I was thinking of was to maintain some constant $K$ number of random topological sorts and if the inequality $index(u) < index(v)$ is true for all $K$ sequences then we can conclude with high probability that there is a path from $u$ to $v$.