Докажите, что сокращение HAM-CYCLE до TSP является полиномиальным временем?

Question

Это вопрос, который наш профессор загрузил вчера, чтобы подготовиться к нашему экзамену завтра.Моя проблема с вопросом - часть b (жирным шрифтом ниже);Я не уверен, что именно мне следует делать.

Задача коммивояжера состоит из продавца и ряда городов.Продавец должен посетить каждый из городов, начиная с определенного (например, родного города) и возвращаясь в тот же город.Проблема в том, что коммивояжер хочет минимизировать общую продолжительность поездки.

TSP = {(G, f, t): G = (V, E) полный граф, f функция V × V → Z, t ∈ Z, G граф, содержащий бегущиетур продавца со стоимостью, не превышающей t}.

Пусть задача HAM-CYCLE определена следующим образом: если существует неориентированный граф G = (V, E), существует ли простой цикл H, содержащий каждый узел в V.

Пусть aполный граф - это граф, в котором есть ребро «между» каждым возможным набором вершин.

a-Определите сертификат для TSP.Покажите, что мы можем проверить сертификат за детерминированное полиномиальное время.

b-Докажите, что сокращение HAM-CYCLE до TSP происходит за полиномиальное время.

c-Используя тот факт, что HAM-CYCLE является NP-полным, чтомы можем заключить?

Answer 1

Существует только три различия между TSP и HAM-CYCLE, как вы их представили:

• TSP предполагает полный граф, тогда как HAM-CYCLE позволяет некоторым парам вершин не делить ребро.
• TSP назначает стоимость каждому ребру, тогда как HAM-CYCLE рассматривает все ребра как эквивалентные.
• TSP ищет тур стоимостью менее t , тогда как HAM-CYCLE принимает любой тур.

Учитывая график G и алгоритм решения TSP, мы можем решить HAM-CYCLE следующим образом:

• Построить полный граф G ′ с тем же набором вершин, что и G .
• Пусть f (наша функция стоимости для TSP) вернет 0, если две вершины смежны в G , и 1, если они не являются.
• Примените наш алгоритм решения TSP к ( G ′, f , t = 0) и верните результат. Это позволит определить, существует ли обход по G ′, в котором используются только ребра, аналоги которых существуют в G .

Выше приведено сокращение полиномиального времени от HAM-CYCLE до TSP. (Понимаете почему?)