Перечисление всех пар непересекающихся путей

10

Учитывая , ориентированный граф , и две вершины . Пара простых путей от до является ребром, если они не разделяют ребро.гзнак равно(В,Е)s,TВп1,п2sT

Используя максимальный поток, легко определить, существует ли пара непересекающихся ребер от до . Теперь, есть ли алгоритм полиномиальной временной задержки для перечисления всех пар ребер непересекающихся путей от до ?sTsT

любительский
источник
1
Нет, поскольку таких путей может быть экспоненциально много.
Каве
6
@Kaveh: Я думаю, что «алгоритм полиномиальной задержки» может занимать экспоненциальное время, пока задержка между выходами полиномиально велика. Например, существует алгоритм полиномиальной задержки, который перечисляет все максимальные клики в возрастающем порядке, даже если число максимальных кликов является экспоненциальным.
Робин Котари
3
Можно ли включить в вопрос объяснение задержки полинома? Я не был знаком с ним, пока не прочитал комментарий Робина.
Артем Казнатчеев
@ Робин, ты прав, я не обратил внимания на слово «задержка».
Каве

Ответы:

6

Я считаю, что ответ Артема Казнатчеева правильный, но он не дает полиномиального пространства. Так что вот другой подход, который должен работать немного лучше в этом отношении.

Используя максимальный поток, можно решить чуть более общую проблему: найти пару непересекающихся путей ребер из некоторых двух вершин {s1, s2} к другой паре вершин {t1, t2}, но не контролируя, какая вершина источника соединена к какой вершине назначения.

Предположим, у нас есть граф G и вершины s1, s2, t1, t2, для которых мы хотим перечислить все пары путей. Найдите одну пару путей P1, P2, и пусть e = (s1, v) будет первым ребром на одном из этих путей. Затем мы можем разбить проблемное пространство на две подзадачи: пары путей, которые используют e, совпадают с путями из {v, s2} в {t1, t2} в G-s1, и пары путей, которые не используют e такие же, как пути из {s1, s2} в {t1, t2} в Ge. Выполните повторение в этих двух подзадачах и (чтобы избежать дублирования) сообщайте путь только тогда, когда вы находитесь в нижней части рекурсии.

Дэвид Эппштейн
источник
1
Очевидно ли, что алгоритм имеет полиномиальную задержку, если мы подождем до конца рекурсии?
Артем Казнатчеев
Рекурсия принимает многоуровневое многоуровневое значение для нижнего уровня (так как каждый уровень удаляет что-то из графика), и каждая ветвь либо сразу возвращается (потому что не может найти пару путей), либо выполняет нижнее значение и возвращает что-то, так что да, это действительно принимает только полиномиальную задержку.
Дэвид Эппштейн
5

Это первый раз, когда я читал об алгоритмах полиномиальной задержки, поэтому я не уверен на 100% в своем ответе, но я думаю, что что-то вроде следующего должно работать.

Выберите какое-то соглашение для представления путей с естественным общим упорядочением определенным на нем. (Одним из примеров будет просто перечислить вершины пути и порядок лексикографически). Выберите свою любимую на месте структуру данных D, которая поддерживает логарифмический поиск и вставку (скажем, красно-черное дерево). Пусть G будет вашим графом<Dг

Определим алгоритм :F


:F(s,T,г,*D)

(здесь D означает ссылку на внутреннюю структуру данных D )*DD

  1. запустите ваш многовременный алгоритм для возврата пары непересекающихся с ребром путей с P < Q от s до t .(п,Q)п<QsT
  2. Если не в D .(п,Q)D

    2.1. Вставьте в D (и выведите, если вы предполагаете вывести при выполнении алгоритма).(п,Q)D

    UvЕ(пQ)F(s,T,г-{Uv},*D)


Ds,TВ(г)s<TsTF(s,T,г,*D)

пSпAСЕпSпAСЕ

Артем Казнатчеев
источник