Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
There isn't going to be a nice classification scheme. Just asking whether the graph has a path of length $V-1$ is already difficult. –  EuYu Nov 7 '12 at 15:22
    
so the longest path within a connected, undirected graph differs with every existing graph? –  blacksmth Nov 7 '12 at 15:26
    
Yes. I doubt your question asks you to find the longest path of a graph in general. If you have a bunch of vertices of degree $1$ connected to a central vertex (like in your example) then the longest path is of length $2$. If you have a graph with a Hamiltonian path, then you have a path of $|V|-1$. In general anything in between is possible. –  EuYu Nov 7 '12 at 15:30
    
thanks for clearing this up for me. I need it to solve another proof but I think I have a wrong approach. –  blacksmth Nov 7 '12 at 15:36

1 Answer 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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