1
$\begingroup$

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

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?

$\endgroup$
  • 2
    $\begingroup$ Try to see if you can reduce Hamiltonian Path to your problem. If you can, then your problem is NP-complete. $\endgroup$ – Yuval Filmus Apr 1 '15 at 21:39
  • $\begingroup$ @YuvalFilmus But in Hamiltonian Path we check whether we visit each vertex but here we are trying to see the longest path i.e. there could be some vertices which might be left out because there might be no connectivity. Also here we are talking about Directed edge only. $\endgroup$ – arqam Apr 1 '15 at 22:01
  • 2
    $\begingroup$ What do you mean by "we don't look in the cycle of the graph"? $\endgroup$ – Yuval Filmus Apr 1 '15 at 22:02
  • $\begingroup$ @YuvalFilmus I meant that being acyclic should not be a compulsory criterion like the previous case. Graph could be cyclic also. $\endgroup$ – arqam Apr 1 '15 at 22:04
  • 2
    $\begingroup$ Cross-posted on cstheory: cstheory.stackexchange.com/questions/30990/… – don't do that. CS.se is indeed the correct site for this question. $\endgroup$ – Yuval Filmus Apr 2 '15 at 0:16
1
$\begingroup$

If I understand your problem correctly, it is NP-hard (and so NP-complete) since you can reduce Hamiltonian Path to it. Given an undirected graph, make it into a directed graph by splitting each undirected edge into two directed edges going in both directions, and ask whether there is a path of length $n-1$.

$\endgroup$

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.