Является ли самый длинный, возможно, непростой путь в NP?

Question

Я знаю, что в NP-HARD существует следующая проблема: для простого графа G = (V, E), двух вершин v, v 'в V, целого числа B и неотрицательной функции длины len: E -> Z +, существует ли простой путь от v до v 'с длиной меньше B?

Мой вопрос таков: при тех же условиях, что и раньше, если мы заинтересованы в нахождении самого длинного не обязательно простого пути в G от вершины v до v ', остается ли проблема в NP-HARD?

Примечание. Я пытался сократить путь к Гамильтону, но до сих пор не могу доказать, есть проблема в NP, сводимая к этой, которую я упоминаю. Я также посмотрел в Garey & Johnson, но ничего не нашел.

Я бы хотел немного подсказки, чтобы доказать, является ли эта проблема NP-HARD. Заранее спасибо!

Answer 1

Кратчайший простой путь в графе без отрицательных циклов не является NP-трудным.См. Кормен «Введение в алгоритмы».Это можно решить с помощью алгоритма Беллмана-Форда.Если у нас нет весов отрицательных ребер, можно также использовать алгоритм Дейкстры.Оба вычисляют весь кратчайший путь от одного источника ко всем остальным узлам графа.Итак, ваша первая проблема, как я вас правильно понимаю, не является NP-трудной.

Задача с самым длинным простым путем, учитывая отсутствие положительных циклов, является двойственной задачей о самом коротком простом пути без отрицательных циклов.Также не NP-hard.

Кратчайший (не простой) путь, допускающий отрицательные циклы, является NP-сложным, потому что вам нужно запомнить все возможные пути к узлу, которые могут быть экспоненциальными.То же самое должно быть верно для задачи с самым длинным (непростым) путем, где допускаются положительные циклы.

Я надеюсь, что это ответит на ваш вопрос.пожалуйста, не стесняйтесь поправлять меня.

Answer 2

Нет, это не NP-жесткий;Вы можете использовать алгоритм кратчайшего пути (например, Беллмана-Форда), чтобы решить его за полиномиальное время, отрицая длину ребер.Обратите внимание, что, вероятно, самый длинный путь будет бесконечным, особенно когда все веса ребер неотрицательны.