Инкрементальный максимальный поток в динамических графиках

Я ищу быстрый алгоритм для расчета максимального потока в динамических графиках. то есть, учитывая граф и s , t ∈ V, мы имеем максимальный поток F в G от s к t . Затем новый / старый узел u добавляется / удаляется с соответствующими ему ребрами для формирования графа G 1 . Каков максимальный поток во вновь созданном графике? Есть ли способ предотвратить пересчет максимального расхода?$G=(V,E)$$s,t\in V$$F$$G$$s$$t$$u$$G^1$

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

Простейшая идея - пересчитать поток.

Другая простая идея заключается в том, чтобы сохранить все пути расширения, которые использовались в предыдущем вычислении максимального потока, для добавления вершины мы можем найти простые пути (в обновленном графе пропускной способности на предыдущем шаге), которые начинаются с источника, идут к v, затем идут до места назначения, но проблема в том, что этот путь должен быть простым, я не мог найти лучше, чем O ( n ⋅ m ) для этого случая, для m = | E | , (Также обратите внимание, что если бы это был только один путь, это можно было бы сделать за O ( n + m ), но это не так.)$v$$v$$O(n\cdot m)$$m=|E|$$O(n+m)$

Также для удаления узла выше идея не работает.

Кроме того, я уже видел такие документы, как инкрементальный подход для ребер , но, кажется, они недостаточно хороши в этом случае, они превышают для каждого ребра и, кажется, не подходят для этого расширения (мы просто пересчитываем поток). Также в настоящее время я использую алгоритм максимального потока Форда-Фулкерсона. Если есть лучший вариант для онлайн-алгоритмов, это хорошо знать.$O(m)$

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

Предположим, что у нас есть неориентированная сеть . Предположим, что он хранится в структуре данных, которая позволяет легко вставлять / удалять вершины / дуги. Иногда мы будем использовать остаточную сеть G f (т.е. с обновленными мощностями c f = c - f ).$G=(V,E,c)$$G_f$$c_f = c - f$

Первая часть - как обработать вставку / удаление вершин. Это более или менее просто для вставки:

1. Добавьте новую вершину с соответствующими ребрами в остаточную сеть.
2. Найдите максимальный поток в обновленной остаточной сети, используя алгоритм по вашему выбору.

$v$$v_{in}$$v_{out}$$v_{in}$$v_{out}$$v$$v_{in}$$v_{out}$$f^v$$v$$v_{in}$$f^v$$v_{out}$$f^v$$\tilde{f^v}$$v_{in}$$v_{out}$$v_{in}$$v_{out}$$f^v$$f^v$$v$$\Delta = f^v - \tilde{f^v}$$s$$t$$v_{in}$$v_{out}$$\Delta$$\Delta$

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

$O(|V|^2|E|)$$O(|E|^2 \log C_{max})$

Хорошо, принимая во внимание новую информацию и избегая некоторых хитрых предварительных фальстартов / рефери красной сельди (mea culpa), вот несколько новых ссылок на это.

Быстрое решение онлайн-последовательности задач с максимальным расходом с расширением до вычисления надежных минимальных сокращений Дуг Алтнер и Озлем Эргун

В этой ссылке рассматриваются онлайновые последовательности МФУ и «теплые запуски», т. е. построение дополнительных запросов к предыдущему МФУ. «Мы демонстрируем, что наши алгоритмы сокращают время выполнения на порядок при сравнении аналогичных кодов, которые используют решатель МФП черного ящика. В частности, мы показываем, что наш алгоритм для надежных минимальных сокращений может разрешать случаи за секунды, для которых потребуется более четырех часов с использованием решателя максимального потока черного ящика ".

достижения в решении проблем, связанных с максимальными потоками Altner, Douglas S., Georgia Georgia

в этой докторской диссертации 2008 года (загружаемый файл в формате pdf) автор рассматривает проблему постепенного добавления дуг, которая кажется «достаточно близкой» к проблеме добавления новых вершин (с несколькими новыми дугами).

большая часть этой ссылки касается удаления частей сети (сокращения / «запрет»), как указано в 1-й части реферата

см. esp "IV РЕШЕНИЕ ОНЛАЙН-ПОСЛЕДОВАТЕЛЬНОСТЕЙ МАКСИМАЛЬНЫХ ПОТОКОВ ... ... стр. 63".

стр. 63 «Однако цель этой главы - убедить читателя в том, что итеративное использование решателя максимального потока черного ящика для решения большой последовательности МФУ может привести к огромному количеству ненужных вычислений».

p66 "В вышеупомянутых приложениях МФУ обычно топологически похожи. То есть следующее МФП в последовательности отличается от предыдущего тем, что добавляет или удаляет небольшое количество дуг или предсказуемо изменяет пропускную способность локализованного набора дуг. Более того, При решении этих случаев время и пространство, необходимые для хранения чего-либо, выходящего за рамки решения предыдущей проблемы, обычно неоправданны ».

Автор p67 также использует подход «теплого старта». «Эффективной стратегией быстрого решения целой последовательности задач оптимизации является разработка эффективной эвристики повторной оптимизации. С этой целью мы разрабатываем модифицированный алгоритм максимального потока, который предназначен для эффективного теплого запуска». »

см. esp p71, в котором есть специфическая добавочная проблема новой дуги:

Новая проблема повторной оптимизации максимального потока (NAMFRP)

автор рассматривает более общие проблемы

Задача повторной оптимизации
максимального потока (MFROP) Задача повторной оптимизации максимального потока одной дуги (MFSAROP)

из некоторого быстрого поиска похоже, что онлайн-версия - область активных исследований. Вы не упоминаете область применения, которая может помочь сузить поиск литературы. Одним из вариантов является поиск области приложения, где есть большинство или последние инновации. следовательно, есть некоторое применение инкрементного максимального потока в системах зрения и некоторые алгоритмы для него; Попробуйте максимальные потоки с помощью инкрементного поиска в ширину в исследовательских лабораториях Microsoft. Перефразируя вступление к этой статье, очевидно, что для случаев со зрением алгоритм Бойкова и Колмогорова преуспевает, и нет известных экспоненциальных контрпримеров времени, хотя за пределами приложений для зрения он может работать плохо. так что, возможно, стоит попробовать алгоритм B & K для ваших данных и посмотреть, как он работает и

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

Вот интересная статья, в которой утверждается, что, хотя неинкрементный алгоритм для максимального потока находится в P, инкрементная версия является NP-полной. «Насколько нам известно, наши результаты являются первыми, кто обнаружил проблему времени P, инкрементная версия которой завершена с помощью NP».

Инкрементальный поток по Hartline, Sharp

другая возможность / направление - это алгоритм максимального потока с принудительной привязкой , который является «одним из наиболее эффективных алгоритмов для максимального потока» и может иметь более сложные профили сложности в зависимости от ваших данных. например, как говорится на странице википедии

$O(V^3)$$O(V^2 \sqrt E$$O(V \cdot E \cdot log(V^2 / E))$