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?

Improve this question
$\endgroup$
7
  • 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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 0:16

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$

Your Answer

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

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