1
$\begingroup$

Why does the following procedure not work?

Let given vertices be $(u,v)$

  1. Run a dfs from any vertex.
    Compute : $low[u]$ for all vertices in the graph
    $low[u] = min(disc[u], disc[w]) $
    where w is an ancestor of u and there is a back edge from some descendant of u to w.
  2. In the tree formed by dfs, find the $lca(u,v)$ of given nodes.
  3. If $lca$ is $u$ or $v$:

    • (Say $lca = u $ wlog) if $low[v] <= disc[lca]$ then yes else no.
  4. If $lca$ is not any of the given nodes:
    • if $low[u]<disc[lca]$ and $low[v]<disc[lca]$ then yes else no.

Here one of the path is $u->lca->v$ and other is using the back edge.
Let $low[u]=low[p]$ where $p$ is a descendent of $u$
and $low[v]=low[q]$ where $q$ is a descendent of $v$.
$p$ to $low[p]$ is a back edge and so is $q$ to $low[q]$.

$u->p->low[p]->low[q]->q->v$ is the other path

Please provide with an example to show why does this not work?

$\endgroup$
2
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W.
    Oct 12, 2015 at 19:08
  • $\begingroup$ Anyway, why do you believe this doesn't work? What have you tried? Have you tried writing a program to generate a million random trees, and running your procedure on this and comparing its output to that of a known-good algorithm to see if you can find any counterexamples? P.S. In LaTeX you can use \le for $\le$ and \to for $\to$; that will look better than $<=$ and $->$. $\endgroup$
    – D.W.
    Oct 12, 2015 at 19:09

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.