0
$\begingroup$

Kind help with an algorithm or any refrence to enumerate all paths of length 3 in a given tree T in the shortest possible time.

$\endgroup$
  • $\begingroup$ Sounds like an interesting question. What did you try and where did you get stuck? $\endgroup$ – Juho Nov 26 '19 at 6:34
  • $\begingroup$ Does length=3 refer to the number of vertices or edges? $\endgroup$ – Albjenow Nov 26 '19 at 14:49
1
$\begingroup$

Let $T$ be a tree on $n$ vertices. Root $T$ in an arbitrary vertex $r$ and let $p(v)$ denote the parent of vertex $v \neq r$ in $T$. For $v \in V$, let $C(v)$ denote the children of $v$ in $T$.

A path $\langle v_1, v_2, v_3, v_4 \rangle$ of length $3$ in $T$ is of exactly one of the following two forms (when the path's traversal direction is ignored):

  • Type A: $p(v_1) = v_2$, $p(v_2) = v_3$, $p(v_3) = v_4$, or

  • Type B: $p(v_1)=p(v_3)=v_2$ and $p(v_4)=p(v_3)$.

To enumerate all paths of type $A$ it suffices to perform a DFS visit of $T$. When a vertex $v$ at depth at least $3$ is encountered, return the path $\langle v, p(v), p(p(v)), p(p(p(v))) \rangle$. This takes $O(n)$ time overall.

To enumerate all paths of type $B$, perform a DFS visit of $T$ and when a vertex $v$ at depth at least $2$ is encountered, return all the paths of the form $\langle v, p(v), p(p(v)), u \rangle$ where $u \in C(p(p(v))) \setminus \{ p(v) \}$. This requires time $O(n + P)$, where $P$ is the number of paths of type $B$ in $T$.

Overall you can enumerate all the paths of length $3$ in $T$ in time $O(n + P)$.

Notice that $\Omega(n)$ is a lower bound on the time needed by any algorithm since you need to read the input tree. A bad case in which $P=0$ but you still spend $\Theta(n)$ time is a star.

$\endgroup$
  • $\begingroup$ Thank you Could you help with with method or link on how to find the diametrical path of a Tree $\endgroup$ – sriram Nov 27 '19 at 15:08
  • $\begingroup$ Right now I can only give the gist. But I'm sure you can find a description of how to solve that problem if you google. Anyway: Root the tree in an arbitrary vertex. Notice that there is a unique vertex of minimum depth in a diametral path $P$. Let this vertex be $v$. Then $P$ is the concatenation of two paths from $v$ to the deepest leaves in two distinct subtrees rooted in the children of $v$ (one or both of these paths might possibly be empty). Use a DFS visit to compute the length of such paths for all the nodes of $T$. This allows you to find $v$ and $P$. $\endgroup$ – Steven Nov 27 '19 at 22:34
0
$\begingroup$

I'm trying to solve it by white-gray-black DFS, but I failed to write the exact answer. But, this idea works: You can solve it easily by Adjacency Matrix Check this link:

https://www.google.com/amp/s/www.geeksforgeeks.org/find-the-number-of-paths-of-length-k-in-a-directed-graph/amp/

Note: if we had repeated vertices, we shouldn't add it. Because in this case we had a cycle or repeated edges.

You can construct all paths of length 3 by this method.

$\endgroup$
  • 1
    $\begingroup$ Can you give a few more details why this solves the question? Just providing a link to a rather practical solution does not make a really good answer. $\endgroup$ – ttnick Nov 26 '19 at 8:03
  • $\begingroup$ Yeah, you're right. I edited it and change the algorithm. $\endgroup$ – Sepehr omidvar Nov 26 '19 at 9:16
  • 1
    $\begingroup$ This will also find "paths" of the form a-b-a-b since "Paths don’t have to be simple i.e. vertices and edges can be visited any number of times in a single path." I suspect that is not what OP wants. $\endgroup$ – Albjenow Nov 26 '19 at 14:46
  • $\begingroup$ Yes, you're right but this is a simple check: if we had repeated vertices, it's not appropriate answer and we shouldn't add it. $\endgroup$ – Sepehr omidvar Nov 27 '19 at 15:18

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.