1
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Oct 21 '16 at 21:31
5
$\begingroup$

This is really just an elaboration of Sasho Nikolov's comment, but the subsequent comment makes clear that it needs elaboration and this doesn't fit within a comment itself.

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.

To see this, we need the known facts that

  • Each strongly connected component contains a Hamiltonian cycle.
  • Condensing the strongly connected components to a single vertex per component produces a directed acyclic graph, which must itself be a tournament.
  • Any acyclic tournament is totally ordered by the orientations of its edges, so the topological ordering of components is uniquely defined.

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.

| cite | improve this answer | |
$\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.