3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ You don't need a hash table, a simple binary array will do. Your extra space is just |V| bits. Do you really want to go lower than that? :) I'm personally skeptical it's possible. $\endgroup$ – Mihai Calancea Mar 16 '16 at 21:03
  • $\begingroup$ @Mihai Calancea I think it is possible but I have not a clear idea: You alter BFS so that in each path you initially are allowed to follow forward arcs only and then backward arcs only. $\endgroup$ – user695652 Mar 16 '16 at 21:36
  • $\begingroup$ Can you even do a BFS without using extra memory to remember which nodes you've been to (which would amount to those |V| bits?). Also, I was actually wrong, you also need O(|V|) extra integers to store the BFS queue. $\endgroup$ – Mihai Calancea Mar 16 '16 at 22:30
  • $\begingroup$ @Mihai Calancea I totally get your point, I was just hoping for a one-pass algorithm or just to hear some other approach... $\endgroup$ – user695652 Mar 17 '16 at 0:47
  • $\begingroup$ What about this: reverse the edges, construct a disjoint-set data structure for all the vertices, run a BFS from $s$ and call $Union(s, v)$ on all reachable vertices $v$, do the same with $t$, then call $Find(s, t)$ to get your answer? $\endgroup$ – DylanSp Mar 17 '16 at 14:38
1
$\begingroup$

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$.
$\endgroup$
  • $\begingroup$ Would it help to use a disjoint-set structure to store data about the vertices and what strongly connected component they belong to? I don't think it helps with the runtime of step 1, although it helps with the runtime of step 2. $\endgroup$ – DylanSp Mar 17 '16 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.