Мне дан граф G и задача под названием LONGER-PATH, которая ищет путь в G между вершинами x и y и возвращает true, если существует путь с наименьшим k ребрами. Я должен доказать, что эта проблема NP-Complete. Используя метод Reductio, первый шаг - доказать, что это NP, который я уже сделал. Теперь Второй шаг - выбрать известный NP-полный для трансформации.
Вот мои варианты:
- цикл Гамильтона
- коммивояжер
- Vertex Cover
- Клик
Мой вопрос: какой из них выбрать, чтобы преобразование было простым?
Теперь я обычно сравниваю входы / выходы, чтобы выбрать подходящую задачу NP-Complete. Я знаю, что все эти четыре проблемы имеют в качестве входных данных график, аналогичный LONGER-PATH. Выводом для LONGER-PATH, отличным от true или false, является путь с как минимум k ребрами. Единственная проблема из 4-х, которую я могу выбрать, которая дает вам путь, - это цикл Гамильтона, даже если он посещает все вершины. Так что я бы честно выбрал один. Это был бы хороший выбор.