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

Я знаю, что в 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. Заранее спасибо!


shortest-path graph-theory longest-path np-hard np-complete
person Pafnuty    schedule 20.02.2011    source источник
comment
Это NP-трудно: см. cstheory.stackexchange.com/questions/20682/   -  person Peter de Rivaz    schedule 04.03.2015

Ответы (2)


arrow_upward
1
arrow_downward

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

person Jeremiah Willcock    schedule 20.02.2011

arrow_upward
1
arrow_downward

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

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

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

Я надеюсь, что это отвечает на ваш вопрос.

Если я что-то упустил или какое-то утверждение неверно, пожалуйста, поправьте меня.

person McMenace    schedule 08.11.2011