How to construct a Hamilton path from a complete directed graph

1
votes

Given a directed graph.

Any 2 vertices are adjacent. The edge connecting a pair of vertices may be uni-directional or bi-directional.

How do I find a Hamilton path?

Side notes:

  • Wikipedia says "A strongly connected simple directed graph with n vertices is Hamiltonian if every vertex has a full degree greater than or equal to n." Therefore, a solution must exist in my problem.
  • I understand that the general Hamilton path problem is NP-Complete. But it feels like this specific version should have a polynomial solution.
1
algorithmgraph

1 Answers

2
votes

Use a variant of insertion sort to construct a path in quadratic time. Given a path

v1 v2 ... vn-1

on a subset of vertices, consider how to insert vn. If vn has an arc to v1, then prepend vn. If vn-1 has an arc to vn, then append vn. Otherwise, there exists by Sperner's lemma an index i such that vn has an arc from vi and an arc to vi+1. Insert it there.