0
$\begingroup$

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.

$\endgroup$
  • $\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$ – Abhishek Bansal Nov 9 '14 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$ – nikhil_vyas Nov 9 '14 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 '14 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 '14 at 13:33
  • $\begingroup$ There is only one path from r to x for every x. $\endgroup$ – nikhil_vyas Nov 9 '14 at 13:36
1
$\begingroup$

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.

$\endgroup$
  • $\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$ – nikhil_vyas Nov 9 '14 at 13:20
  • $\begingroup$ I edited the answer. Initially I assumed that it's a general rooted tree. $\endgroup$ – orezvani Nov 9 '14 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$ – nikhil_vyas Nov 9 '14 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 '14 at 13:26
  • $\begingroup$ there can be as there are no repeated vertex in a path. $\endgroup$ – nikhil_vyas Nov 9 '14 at 13:30

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.