1

I got stuck with this problem since the whole day.

When we are finding the longest path in a graph we first do topological sorting and then check the path of adjacent vertices and keep upgrading selecting the maximum of the edge weight or the alternate path from the other vertex.

So, we are able to solve this problem because of topological sorting which can be done only for acyclic graphs. Thus this type of question can be solved only for acyclic graph.

enter image description here

So, we are able to solve this problem because of topological sorting which can be done only for acyclic graphs. Thus this type of question can be solved only for acyclic graph.

Now, if I present another case. What if all the edge have the same weight and we don't look in the cycle of the graph. Is this solvable. Everytime I think about this I don't see any use of topological sorting if we can choose any source considering we have to choose the maximum number of nodes(longest path).

Is this also NP Hard or can we solve this?

PS : I went through this Longest acyclic path in a directed unweighted graph but there is just the algorithm to solve the longest path problem.

Community
  • 1
  • 1

1 Answers1

0

It's not clear what you mean by "not looking in the cycle", so I'll assume you mean that we don't consider taking edges between vertices in a cycle in our longest path. In this case, you can compress your cycles into single vertices and use the algorithm you describe above.

vrume21
  • 561
  • 5
  • 15
  • Yeah but in the modified version I don't think the above algorithm works. Like there can a vertex which does not have any incoming edge. We just have to pass through as many vertices as possible since all the path are of the same weight. I was thinking about reducing to Hamiltonian graph problem but there we have to select all the vertices but here we just have to check the longest path not compulorily passing through all the vertex. If you want then I can provide an example also in the link. –  Apr 02 '15 at 05:41
  • The dynamic programming solution to the LPP always handles nodes without incoming edges. The outline of the algorithm is as follows: for each node n_1, for each node n_2 less than n_1, consider paths including n_2 and excluding n_2. If some node n_n has no incoming edges, we will never include it in a potential longest path from the inner loop, but we will in the outer. This makes perfect sense because n_n will always be the root of any path including it. – vrume21 Apr 02 '15 at 12:17
  • Check this link. Here Aditya Deepak gave a solution, I have not tried it but it looks pretty feasible.What is your opinion on that? http://www.quora.com/Given-a-directed-unweighted-graph-how-can-we-traverse-though-maximum-number-of-nodes-given-we-can-choose-any-node-as-the-source –  Apr 02 '15 at 13:15
  • It's very hard to read and make sense of. Use this link: https://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf. They solve the problem you're having and give pseudocode. – vrume21 Apr 02 '15 at 13:36