Подграф, содержащий все узлы и ребра, являющиеся частью простых st-путей с ограниченной длиной в неориентированном графе

12

Очень похоже на мой ранее опубликованный вопрос . На этот раз, однако, график является ненаправленным.

Данный

  • Неориентированный граф G без каких - либо множественных ребер или петель,
  • Исходная вершина s ,
  • Целевая вершина t ,
  • Максимальная длина пути l ,

Я ищу G - подграф G который содержит любую вершину и любое ребро в G (и только те), которые являются частью хотя бы одного простого пути из s в t с длиной l .

Примечания:

  • Мне не нужно перечислять пути.
  • Я ищу эффективный алгоритм (и время, и память), так как мне нужно выполнить его на очень больших графах (10 ^ 8 вершин, 10 ^ 9 ребер).
Лиор Коган
источник
Проверь это. Нашел эту статью, которая, кажется, делает подобное сокращение минимальных затрат, но использует специальные характеристики сети, чтобы решить ее быстрее, чем общие алгоритмы MCF.
РБ

Ответы:

6

Ну, проблема в конце концов. Я оставлю предыдущий ответ, так как он также работает для направленного случая (который является NPC, как ответили на другой вопрос), и покажет, что это F P T по отношению к l .PFPTl

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

Следующая процедура определит, должно ли какое-либо ребро быть частью выходного графа. Чтобы ответить на исходную задачу, просто переберите все ребра.e=(u,v)E

Чтобы создать потоковую сеть, выполните следующие действия:

Шаг 1: Разверните чтобы получить вершину x e, и замените e ребрами ( u , x e ) , ( x e , u ) , ( v , x e ) , ( x e , v ) (они направлены как часть сети потоков), установите их стоимость на 0.exee(u,xe),(xe,u),(v,xe),(xe,v)

Шаг 2: замените каждую вершину , кроме x e , двумя вершинами t - и t + и добавьте ребро ( t - , t + ) . Установите стоимость этих ребер равной 1.txett+(t,t+)

Шаг 3: Заменить каждое ребро ребрами ( a + , b - ) , ( b + , a - ) . Установите стоимость этих ребер равной 0.{a,b}E(a+,b),(b+,a)

Шаг 4: Добавьте новую вершину и добавьте ребра ( s , y e ) , ( t , y e ) со стоимостью 0.ye(s,ye),(t,ye)

Шаг 5: установите все мощности на 1.

Теперь запустите алгоритм минимального потока затрат, ища поток значения 2 от до y e .xeye


Анализ:

  • xeyex et y exesyexetye
  • Пути не пересекаются, поскольку для каждой вершины в дуге есть только 1 емкость .( т - , т + )t(t,t+)
  • Возвращенные пути - это два пути, сумма расстояний которых минимальна, и это также стоимость найденного потока. Это позволяет нам добавить в выходной граф или удалить в противном случае.e
RB
источник
1
Проще понять аргумент в ответе выше, отбросив приведение к направленному потоку. Существует простой путь от до содержащий узел если существует путь от до и путь от до такой, что и не пересекаются, за исключением . Это принципиально использует ненаправленность. Это может быть проверено с помощью потока, а версия стоимости также может быть выполнена с помощью потока минимальной стоимости. Можно проверить, существует ли простой путь от до содержащийt v P v s Q v t P Q v s t e estvPvsQvtPQvsteвведя узел в середине . e
Чандра Чекури
@ChandraChekuri - это правильно, но имейте в виду, что если у проблемы нет ограничения по длине, существует гораздо более простой алгоритм ее решения - см. Здесь
RB
Конечно, я тоже знаю об этом решении - концептуально было бы хорошо понимать двусвязные компоненты через непересекающиеся пути, даже если можно найти вершины среза и двусвязные компоненты непосредственно через DFS.
Чандра Чекури
@RB: Спасибо. Предлагаемый алгоритм может быть эффективен, когда l относительно велико, но, вероятно, он неоптимален для относительно небольших значений l. Я думаю, что я могу сначала обрезать G, удалив любую вершину дальше пола (l / 2) от s и ceil (l / 2) от t.
Лиор Коган
1
Попробуйте адаптировать алгоритм последовательного кратчайшего пути (также называемый алгоритмом Сурбалла для случая 2 путей, который представляет интерес здесь). Вы хотите найти кратчайшие 2-пути от (лучше называть его вместо поскольку он одинаков для всех ребер) до каждого . Я думаю, что это эффективно выполнимо, сначала вычисляя дерево кратчайшего пути от а затем с некоторой осторожностью реализуя вычисление второго пути. у у е х е уyyyexey
Чандра Чекури
1

stst

O(|V|+|E|)

sVssdist(s,v)vVstVttVsolution={v:vVsVt,dist(s,v)+dist(t,v)}E[Vsolution]=(v,u)E:u,vVsolution

O(|V|+|E|)O(|Vs|+|Vt|+|E[Vs]|+|E[Vt]|)st маленькие.

st/2

пельмени мобиус
источник
3
tusvxl=4vv
Спасибо за исправление @RB. Я отредактировал свой ответ, чтобы отметить, что это неправильно.
клецки мобиуса
1

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

G=(V,E)H=(V,E)H=(V,E,w)

O(n4/3)O(n4/3)O(n4/3)

Если это звучит полезно, я могу попытаться выкопать соответствующие конструкции для вас.

GMB
источник