# Longest path from every vertex in a tournament

I have a tournament (directed complete graph) with $V$ vertices. For every vertex I want to find the longest path starting in it (so the longest path starting in the first vertex, longest path starting in the second vertex etc.). In general, longest path problem is NP-complete, but this is a very special case so I guess there exist a polynomial (in terms of $V$) time algorithm.

• I may be missing something, but I think, if you order topologically the strongly connected components in a tournament as $C_1, \ldots, C_k$, and you are given a vertex $v \in C_i$, then the longest path starting at $v$ includes all vertices in $C_i, \ldots, C_j$. The reason is that the graph induced on each $C_j$ is a strongly connected tournament, so it contains a Hamiltonian cycle. Oct 21, 2016 at 21:31

If you topologically order the strongly connected components of your tournament, then the longest path from any vertex $v$ contains all vertices of the component containing $v$ and all vertices of later components.
So, start from $v$, and follow the Hamiltonian cycle within its own component. Then, when the cycle would return to $v$, instead follow any edge to the next component in the total ordering of the components (there's an edge to that component because there's an edge to every vertex and because the edges connecting the current component to the next component are all oriented in the direction you want to go). Then continue the same way in each successive component.