«Родственники» проблемы кратчайшего пути

10

Рассмотрим связный неориентированный граф с неотрицательными весами ребер и двумя выделенными вершинами s,t . Ниже приведены некоторые задачи на пути, которые имеют следующую форму: найдите путь st , чтобы некоторая функция весов ребер на пути была минимальной. В этом смысле все они являются «родственниками» проблемы кратчайшего пути; в последнем случае функция - это просто сумма.

Примечание. Мы ищем простые пути, то есть без повторяющихся вершин. Поскольку в литературе я не нашел стандартных названий этих проблем, я назвал их сам.

Траектория с минимальным разрывом в весе: найдите st траекторию, чтобы разница между наибольшим и наименьшим весом ребер на трассе была минимальной.

Самый плавный путь: найдите путь st , чтобы наибольший размер шага на пути был минимальным, где размер шага - это абсолютное значение разницы в весе между двумя последовательными ребрами.

Траектория с минимальной высотой. Давайте определим высоту трассы суммой размеров шагов вдоль пути (см. Определение размера шага выше). Найти st путь с минимальной высотой.

Путь с минимальным простым весом: предполагая, что все веса ребер являются натуральными числами, найдите путь st , чтобы его вес был простым числом. Если есть такой путь, найдите тот с наименьшим возможным основным весом.

Вопрос: что известно об этих проблемах пути? (И другие, которые можно было бы представить в том же духе, применяя другую функцию весов.) В целом, есть ли какое-либо указание, что какие функции весов ребер могут быть минимизированы за полиномиальное время, а какие являются NP-сложными?

stst

Андрас Фараго
источник

Ответы:

8

Вот ответ на первую проблему:

Траектория с минимальным разрывом в весе: найдите s - tst

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

S. Martello, WR Pulleyblank, P. Toth, D. de Werra
Сбалансированные задачи оптимизации
Письма об исследовании операций 3, 1984, стр. 275-278

Это подразумевает алгоритм полиномиального времени на ваш вопрос.

Гамов
источник
1
Это также может быть сделано путем поиска методом грубой силы по всем парам ребер, которые могут составлять максимум и минимум, и их порядку / ориентации.
Йонатан N
3

O~(|E|2)|E||E|

O~(|E|)|E|2kk1


SΘ(n/logn)PSдаже для двоичных весов: достаточно отслеживать полиномиально много (в зависимости от ) самых низких весов пути в каждой точке. Однако при использовании простых весов нам, возможно, придется диверсифицировать делители весовых различий (вместо того, чтобы просто отслеживать самые низкие веса), и неясно, достаточно ли этого.S

Плавный путь: НП завершен. Если бы мы разрешали самопересечения, это было бы разрешимо во времени , но для версии без самопересечений здесь приведено сокращение от 3-SAT с переменными. Иметь вершины , плюс вершины для каждого предложения. Для каждой переменной ( ) добавьте плавный путь (при необходимости используя дополнительные вершины) из в который проходит через все предложения с положительным вхождением , и аналогичный путь для предложений сO~(|E|)ns=v0,v1,...,t=vnxii<nvivi+1xi¬xi, Установите вес первого и последнего ребра каждого пути равным 1 (или другой константе), но в противном случае выбирайте веса так, чтобы другие пути не были гладкими. Наконец, продублируйте все вершины клаузулы и прилегающие ребра; таким образом, каждое предложение может быть просмотрено не более двух раз, что достаточно для 3-SAT.

Дмитрий Тарановский
источник
Я думаю, Smoothest путь находится в P, из-за следующего преобразования. Пусть - вершина степени . Замените кликой размером , так что каждое ребро которое изначально было смежно с теперь заканчивается в другой вершине клики. Если два таких исходных ребра, то присваиваем веск краю в клике. Сделайте это преобразование для каждой вершины и присвойте 0 весов исходным ребрам графа. Тогда минимальный весvdvdevvee,f|w(e)w(f)|(ve,vf)vs,tstПуть в новом графе дает наиболее плавный путь в оригинале после отмены преобразования.
Андрас Фараго,
@AndrasFarago Проблема с вашим аргументом в том, что некоторые простые пути в расширенном графе имеют повторяющиеся вершины в исходном графе. Мне нравится, что проблема гладкого пути выглядит обманчиво простой.
Дмитрий Тарановский
@ Дмитрий Тарановский Кажется, вы правы, может случиться так, что после возврата к исходному графу мы можем получить повторяющиеся вершины на пути (но без повторяющихся ребер). Однако, если каждая степень в исходном графе не превышает 3, повторение не может произойти. Это означает, что задача Smoothest Path находится в P по крайней мере для графов с максимальной степенью . 3
Андрас Фараго
Извините, в преобразованном графе нам нужно найти путь с наименьшим максимальным весом (который также находится в P), а не с наименьшим общим весом. Общий вес приведет к траектории с минимальной высотой (на графиках с максимальной степенью , так что повторяющиеся вершины исключаются). 3
Андрас Фараго