Нахождение мин-макс вершинно-непересекающихся путей с общим источником на плоских графах

10

Для заданного невзвешенного плоского графа и набора пар вершин ( - константа) найдите непересекающихся вершин (кроме исходных) путей от до таких что длина самого длинного пути сведена к минимуму.(s,T1),...,(s,TК)К2КsTя

Вопрос: есть ли алгоритм задачи с полиномиальным временем?

Некоторые связанные результаты:

  • если не зафиксировано, проблема является NP-сложной, даже если ;КT1знак равнознак равноTК
  • если входной граф взвешен и источники путей не совпадают, то есть пути проблема NP-трудна даже для ;(s1,T1),...,(sК,TК)Кзнак равно2
  • проблема с другой целью, а именно минимизацией суммы длин пути, заключается в

    • разрешимый с алгоритмом минимальной стоимости потока для совпадающих источников;
    • NP-hard для несовпадающих источников и общего ;К
    • открыт для несовпадающих источников и константы .К
Сергей Пупырев
источник
4
Похоже, что есть много связанных результатов. Можете ли вы суммировать важные связанные результаты в вопросе?
Цуёси Ито
Взвешен ли входной граф G (то есть длина каждого ребра равна целому положительному целому числу)? Я предполагал, что G не взвешен, но я понял, что вы, вероятно, смешиваете две установки: (1) Если G взвешен, то случай k = 2 является NP-полным по существу по теореме 14 в статье: Кобаяши и Соммер, с которыми вы связались, что также по сути совпадает с последним абзацем в Разделе 2 [HP02], указанном в моем ответе. (2) Если G не взвешен, то я не могу понять, почему в работе Кобаяси и Соммера подразумевается NP-твердость в случае k = 2 и различных источников.
Цуёси Ито
В моих настройках график не взвешен, так что вы правы: мое утверждение о NP-твердости в случае K = 2 и различных источников (вероятно) неверно.
Сергей Пупырев
Я обновил формулировку проблемы с учетом комментария Цуёси Ито.
Сергей Пупырев

Ответы:

6

Это не совсем то, что вы просили, но проблема в 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

Цуёси Ито
источник
КК
@SergeyPupyrev: Вы написали, что k является константой. (Вы написали это, потому что знали, что это значит, не так ли?) Из того, что я узнал из беглого взгляда на соответствующие статьи, кажется, что k является константой или нет в связанных проблемах, имеет огромное значение в текущем состоянии сложность проблемы.
Цуёси Ито
КК
1
@SergeyPupyrev: Я не могу найти статью, в которой говорится о сложности в случае, когда k является константой, но это только означает, что она мне неизвестна .
Цуёси Ито