従って、一般のグラフにおけるハミルトン路の問題はnp困難であるが、一意なトポロジカルソート結果が存在するかどうか、あるいはハミルトン路が存在するかどうかは多項式時間で決定することができる。