Какие из следующих задач могут быть сведены к задаче о гамильтоновом пути?

Question

Я беру класс " Алгоритмы: дизайн и анализ II ", один из вопросов:

Предположим, что P ≠ NP. Рассмотрим неориентированные графы с неотрицательными длинами ребер. Какие из следующих проблем могут быть решены за полиномиальное время?

Подсказка: задача о гамильтоновом пути: учитывая неориентированный граф с n вершинами, решите, существует ли путь (без цикла) с n - 1 ребрами, который посещает каждую вершину ровно один раз. Вы можете использовать тот факт, что задача о гамильтоновом пути является NP-полной. Существуют относительно простые сведения о задаче о гамильтоновом пути к 3 из 4 нижеприведенных задач.

• Для заданного источника s и пункта назначения t вычислите длину кратчайшего st-пути, который имеет ровно n - 1 ребер (или +∞, если такого пути не существует). Путь может содержать циклы.
• Среди всех охватывающих деревьев графа вычислите одно с наименьшим возможным числом листьев.
• Среди всех остовных деревьев графа вычислите одно с минимально возможной максимальной степенью. (Напомним, что степень вершины - это число падающих ребер.)
• Для заданного источника s и пункта назначения t вычислите длину кратчайшего st-пути, который имеет ровно n - 1 ребер (или +∞, если такого пути не существует). Путь не может содержать циклы.

Обратите внимание, что гамильтоновый путь является остовным деревом графа и имеет только два листовых узла, и что любое остовное дерево графа с ровно двумя листовыми узлами должно быть гамильтоновым путем. Это означает, что NP-полная задача определения того, существует ли в графе гамильтонова траектория, может быть решена путем нахождения минимального листового остовного дерева графа: путь существует тогда и только тогда, когда минимальное листовое остовное дерево имеет ровно два листа, Таким образом, задача 2 является NP-полной.

Задача 3 NP-сложная; вот документ, который доказывает это.

Это означает, что между 1 и 4 один является NP-завершенным, другой - P. Кажется, что проблема 4 тривиально сводится к задаче о гамильтоновом пути, но я не могу понять, как цикл делает его разрешимым? Или это другой путь?

Answer 1

Для первого вы можете использовать Dijkstra, чтобы получить кратчайшие четные и нечетные возможные расстояния. Для этого для каждой вершины нужно хранить не одно минимальное число, а два из них. Один - минимальный вес нечетного пути, другой - минимальный вес четного пути. Получив эти две длины, вы можете легко увеличить длину пути на четное число ребер, если допустимы циклы. Итак, первая проблема из P. Пошаговый алгоритм будет:

1. Найти кратчайшие четные и нечетные пути длины.
2. Увеличьте длину одного из этих путей, который имеет такое же соотношение n-1 в n-1 путем добавления цикла длины 2 требуется количество раз.