Вероятно, я бы начал разработку алгоритма, выбрав первый узел в P (назовем его P [0]), затем выполнив поиск в глубину из P [0], заметив, что P [0] снова достиг. Вам нужно будет сохранить путь, выбранный для повторного достижения P [0] (или, по крайней мере, были ли достигнуты другие узлы P), чтобы вы знали, что любой найденный цикл содержит все узлы в P. Время выполнения должно быть так же, как и для поиска в глубину, который, как я считаю, O (V + E).
Кто-то может предложить лучшее решение, и для помощи могут быть применены определенные эвристики, но это должно помочь вам начать. (Например, вы можете заключить, что вам следует начинать с узла P с наименьшим количеством ребер вместо того, чтобы начинать с P [0].)
Edit:
Еще одна вещь, о которой я подумал ... Когда вы достигаете другого узла в P посредством поиска в глубину, нет необходимости когда-либо DFS "начинать сначала" с самого начала или рассматривать пути, которые не включить этот недавно найденный узел. Это свойство может помочь вашему алгоритму быстрее завершиться в случае, если такого цикла не существует.
Дальнейшее редактирование:
Не берите в голову последнее редактирование - оно будет работать, только если будет установлено, что в P нет узла на другом пути между P [0] и узлом в P, который не может быть достигнут другим способом, и мы не знал бы этого наверняка, не выполнив всю DFS.
Что касается ответа о гамильтоновых циклах, я не знаю, как обнаружение циклов в рассматриваемой задаче является NP-полным. Да, нам нужно будет пройти весь граф (все вершины и ребра), достижимый из начальной точки, чтобы определить, существует ли цикл, отвечающий критериям рассматриваемой задачи. Кроме того, нам нужно знать при соприкосновении с ранее посещенной вершиной, каким будет «прямой путь» вершины, чтобы определить, существует ли цикл, отвечающий критериям. Поскольку нам не важен самый короткий такой цикл, я не уверен, как мы обязательно пытаемся найти гамильтонов цикл. Хочешь просветить?