A directed rooted graph is defined as graph for which there exists a vertex r such that to every vertex x there is a unique path (Equivalently dfs tree with source r has only back edges and has all vertices). I need an algorithm to find the longest path in such a graph.

I know that in general longest path problem is NP-hard. I want to know whether for this special case there exists a polynomial time algorithm.

  • $\begingroup$ If I have understood correctly, then this graph basically consists of the 'dfs tree' along with edges only directed towards r. Am I right? $\endgroup$ Nov 9, 2014 at 11:26
  • $\begingroup$ No the edges except those of dfs tree are backwards but not necessarily towards r. In general they must be to one of their ancestors of dfs tree. $\endgroup$ Nov 9, 2014 at 12:24
  • $\begingroup$ Your definition of rooted tree is not correct. In a rooted tree, there exists a root and there is no obligation on the uniqueness of path from root to the others. $\endgroup$
    – orezvani
    Nov 9, 2014 at 13:28
  • $\begingroup$ "there exists a vertex r such that to every vertex x there is a unique path " does it mean that there is only one path or at least one path? $\endgroup$
    – orezvani
    Nov 9, 2014 at 13:33
  • $\begingroup$ There is only one path from r to x for every x. $\endgroup$ Nov 9, 2014 at 13:36

1 Answer 1


The problem falls into one of the following cases:

case (a): There is a unique path from the root to all other nodes (it means that there is only one single path from root to others; this implies that there is only one single path between any other pair of nodes too). If there is only a unique path from source to each node, then there is $O(n^2)$ number of different paths in the graph, you can just find them pick the longest one as the optimal solution using a polynomial time algorithm. You just need a DFS traversal from root and find the length of path to each leaf and choose the longest one.

case (b): But if it's a general rooted graph, i.e. there can be multiple paths from root to other nodes but there is no path from them to the root, then the following theorem holds. This problem is NP-complete as the actual longest path problem reduces to it. The reduction is as follows. Given an instance of longest path problem $I=(G(V,E), k)$, we build an instance of your problem $I'=(G'(V \cup \{s\},E \cup \{(s,v_1),(s,v_2),...(s,v_n)\}),k+1)$ (The reduction is very strightforward, I keep it short).

In the later case, if you are just looking for a feasible solution. I suggest removing the source node from your directed graph and using the available heuristics for the longest path problem in the resulting graph. Then adding the source to that path.

  • $\begingroup$ This does not satisfy the unique path condition. If you originally had an edge uv now you have two paths to v : (s,v) and (s,u,v). $\endgroup$ Nov 9, 2014 at 13:20
  • $\begingroup$ I edited the answer. Initially I assumed that it's a general rooted tree. $\endgroup$
    – orezvani
    Nov 9, 2014 at 13:21
  • $\begingroup$ Your algorithm works if there were no back edges but as back edges are allowed it will not give the longest path. $\endgroup$ Nov 9, 2014 at 13:23
  • $\begingroup$ @nikhil_vyas If there is a unique path from root to other nodes, then there cannot be any back-edge. $\endgroup$
    – orezvani
    Nov 9, 2014 at 13:26
  • $\begingroup$ there can be as there are no repeated vertex in a path. $\endgroup$ Nov 9, 2014 at 13:30

Your Answer

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

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