2
$\begingroup$

I have to identify the longest path of a connected, undirected graph $G=(V,E)$, but I'm currently stuck.

Out of intuition I would say that the longest path in G is $G=|V-1|$ but that doesn't seem to work with every graph.

Happy for any pointers into the right direction.

Sorry for the confusion. I was talking about a connected graph. Wrong translation from my mothertongue.

  • 0
    thanks for clearing this up for me. I need it to solve another proof but I think I have a wrong approach.2012-11-07

1 Answers 1

1

The Hamilton path problem is NP-complete. Thus, we cannot even reasonably expect to find an efficient algorithm for answering "does the longest path in $G$ have length $|V|-1$?"

There are even results in the literature that give theoretical limitations to the efficiency of an algorithm that approximates the longest path:

Andreas Björklund, Thore Husfeldt, Sanjeev Khanna, Approximating Longest Directed Paths and Cycles, Automata, Languages and Programming, Lecture Notes in Computer Science Volume 3142, 2004, pp 222-233.