Для заданного невзвешенного плоского графа и набора пар вершин ( - константа) найдите непересекающихся вершин (кроме исходных) путей от до таких что длина самого длинного пути сведена к минимуму.
Вопрос: есть ли алгоритм задачи с полиномиальным временем?
Некоторые связанные результаты:
- если не зафиксировано, проблема является NP-сложной, даже если ;
- если входной граф взвешен и источники путей не совпадают, то есть пути проблема NP-трудна даже для ;
проблема с другой целью, а именно минимизацией суммы длин пути, заключается в
- разрешимый с алгоритмом минимальной стоимости потока для совпадающих источников;
- NP-hard для несовпадающих источников и общего ;
- открыт для несовпадающих источников и константы .
ds.algorithms
graph-algorithms
Сергей Пупырев
источник
источник
Ответы:
Это не совсем то, что вы просили, но проблема в NP-полноте, если k не является константой, а является частью входных данных.
Это следует из доказательства теоремы 1 в Ван-дер-Хольсте и де Пине [HP02], где говорится: для плоского графа G , различных вершин s и t в G и целых положительных чисел k и b NP-полна, чтобы решить существует ли k попарно внутренних вершинно-непересекающихся путей между s и t, каждая из которых имеет длину не более b .
Обратите внимание, что проблема в формулировке теоремы 1 отличается от вашей в двух отношениях. Одно из отличий состоит в том, что, как я уже говорил, k задается как часть ввода. Другая проблема заключается в том, что проблема в [HP02] касается путей с общими конечными точками, а не путей с общим источником и различными приемниками. Я не знаю, как исправить первое отличие; разница настолько велика, что, вероятно, нам понадобится совершенно другое доказательство, чтобы исправить k . Но я знаю, по крайней мере, как исправить второе отличие.
Доказательство теоремы 1 в [HP02] дает сокращение от 3SAT. Эта редукция имеет следующее свойство: в экземпляре ( G , s , t , k , b ), построенном по редукции, степень вершины t всегда равна k . Пусть t 1 ,…, t k - k соседей t . Тогда вместо того, чтобы спрашивать, существует ли k попарно внутренних вершинно-непересекающихся путей между s и t, каждая длиной не более b, мы можем в равной степени спросить, существуют ли попарные пути вершин, дизъюнктов, кроме источников P 1 ,…, P k, такие, что каждый P i является путем между s и t i длиной не более b −1.
[HP02] Х. ван дер Холст и Х.С. де Пина. Ограниченные по длине непересекающиеся пути в плоских графах. Дискретная прикладная математика , 120 (1–3): 251–261, август 2002 г. http://dx.doi.org/10.1016/S0166-218X%2801%2900294-3
источник