<p>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.</p>

<p>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.</p>

<p>To see this, we need the known facts that</p>

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

<p>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.</p>

CC BY-SA 3.0
2016-10-22T07:08:06.487Z
2016-10-22T07:08:06.487Z
David Eppstein
<p>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.</p>

CC BY-SA 3.0
2016-10-21T21:31:38.293Z
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.
Sasho Nikolov
<graph-theory><graph-algorithms>
Longest path from every vertex in a tournament
Theodor Thrusht
# Longest path from every vertex in a tournament

(Asked by: username_0 on 2016-10-21)

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.

**Tags:** graph-theory, graph-algorithms

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2016-10-22. Score: 5 | Accepted answer

This is really just an elaboration of username_1'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.


---

