Вот образовалась у меня задача, а как решить -- не знаю. Задача полностью из головы, поэтому никаких ссылок нет.

Есть невзвешенный ориентированный граф (мне нужен случай разреженного графа, количество ребер меньше 3*{количество вершин}, но это мало влияет на суть задачи), в графе могут быть циклы. Надо найти самый длинный путь из заданной вершины, который не проходит через одну и ту же вершину больше одного раза.

Я не могу придумать алгоритм, который работал бы за полиномиальное от количества вершин время. И что-то у меня возникли сомнения в его существовании (задача чем-то похожа на задачу о коммивояжере).

Буду благодарен, если кто-то расскажет такой алгоритм, либо подтвердит мои сомнения. Заранее спасибо.

UPD. Действительно, достаточно очевидно, что решение этой задачи равносильно нахождению гамильтонова пути в графе, что, как известно, является NP-полной задачей. Спасибо MikeMirzayanov и Edvard.

Так же большое спасибо goo.gl_SsAhv за предложенное решение. Хотя оно, как видно, и неправильное, но очень интересное и поучительное для меня. Из неправильных решений иногда можно подчерпнуть не меньше, чем из правильных