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

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

Данный

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

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

Примечания:

• Мне не нужно перечислять пути.
• Я ищу эффективный алгоритм (и время, и память), так как мне нужно выполнить его на очень больших графах (10 ^ 8 вершин, 10 ^ 9 ребер).

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

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

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

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

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

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

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

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

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

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

Анализ:

• $x_e$$y_e$x e ⇝ t → y $x_e\leadsto s\to y_e$$x_e\leadsto t\to y_e$
• Пути не пересекаются, поскольку для каждой вершины в дуге есть только 1 емкость .( т - , т +$t$$(t^-,t^+)$
• Возвращенные пути - это два пути, сумма расстояний которых минимальна, и это также стоимость найденного потока. Это позволяет нам добавить в выходной граф или удалить в противном случае.$e$

$s$$t$$s$$t$$\le \ell$

$O(|V|+|E|)$$\ell$

$s$$\ell$$V_s$$s$$\ell$$dist(s,v)$$v \in V_s$$t$$V_t$$t$$V_{solution}=\{ v : v \in V_s \cap V_t, dist(s,v)+dist(t,v) \le \ell \}$$E[V_{solution}]$$=(v,u) \in E : u,v \in V_{solution}$

$O(|V|+|E|)$$O(|V_s| + |V_t| + |E[V_s]|+|E[V_t]|)$$\ell$$s$$t$ маленькие.

$s$$t$$\ell/2$$\ell$$\ell$

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

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

$O(n^{4/3})$$O(n^{4/3})$$O(n^{4/3})$

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