Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
