Может ли минимальное сокращение быть проще, чем сетевой поток?

Благодаря теореме min-cut о максимальном потоке мы знаем, что мы можем использовать любой алгоритм для вычисления максимального потока в сетевом графе для вычисления -min-cut. Следовательно, сложность вычисления минимального -среза не больше, чем сложность вычисления максимального -потока. $(s,t)$ $(s,t)$ $(s,t)$

Может ли быть меньше? Может ли быть алгоритм для вычисления минимального -среза, который быстрее любого алгоритма максимального потока? $(s,t)$

Я пытался найти сокращение, чтобы свести проблему ) -max-flow к проблеме -min-cut, но я не смог ее найти. Моей первой мыслью было использование алгоритма «разделяй и властвуй»: сначала найдите минимальный разрез, который разделяет график на две части; Теперь рекурсивно найдите максимальный поток для левой части и максимальный поток для правой части и объедините их вместе со всеми ребрами, пересекающими разрез. Это действительно будет работать для создания максимального потока, но его время выполнения в худшем случае может быть в раз больше времени выполнения алгоритма min-cut. Есть ли лучшее сокращение? $(s,t$ $(s,t)$ $O(|V|)$

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

Это очень тесно связано с вычислением максимального потока из минимального сокращения , за исключением: (1) я хочу разрешить сокращения Кука (сокращения Тьюринга), а не только сокращения Карпа (многократные сокращения) и (2) возможно, учитывая мы можем найти некоторый граф такой, что минимальный срез облегчает вычисление максимального потока , что является чем-то, что выходит за рамки этого другого вопроса. $G$ $G'$ $G'$ $G$

@AshkanKzme, я не слежу за тобой; можешь уточнить? Как я утверждаю в 4-м абзаце вопроса, теорема о минимальном сечении максимального расхода показывает, что значение максимального потока равно пропускной способности минимального среза. Я подозреваю, что это то, что вы думаете. Однако знание значения максимального потока не говорит вам о самом максимальном потоке (например, сколько нужно отправить на каждом конкретном ребре). Этот вопрос задает вопрос о сложности вычисления самого максимального потока по сравнению с вычислением самого минимального сокращения. Мой вопрос точно такой, как указано во втором абзаце вопроса.

@AshkanKzme, нет, я не ошибся. Вы неявно предполагаете, что Ford-Fulkerson - это самый быстрый из возможных алгоритмов поиска минимального разреза ... но, насколько я знаю, никто никогда не доказывал этого, и мы не знаем, правильно это или нет. Мне кажется, что вы делаете стандартную ошибку новичка с нижними доказательствами: «Я не вижу способа быстрее решить эту проблему, поэтому это должно быть невозможно». (PS Вы рассказываете мне стандартные учебники о минимальном срезе с максимальным потоком. Я ценю вашу попытку помочь, но я уже знаком с этим ...)

Что касается вашего утверждения «Я думаю, что можно доказать, что если у вас есть только минимальное сокращение, вы можете получить максимальный поток», то я призываю вас написать ответ с доказательством этого - потому что это в основном то, что мой вопрос задаю Я никогда не видел доказательства этого, но если у вас есть, я надеюсь, что вы напишите это!

@DW Я думаю, теперь мне стало легче. Я думаю, что меня обескуражил тот факт, что вы даете полиномиальное сокращение Тьюринга. Разве вам не нужно постоянное уменьшение Тьюринга, чтобы доказать

, в то время как даже доказательство того, что такое сокращение невозможно, не опровергает его?

f (n) = Θ (g (n))

$f(n) = \Theta(g(n))$

Томас Босман

@ThomasBosman, да, это правильно. [Извините, что сбил вас с толку. Приведенная мною редукция доказывает, что

, что является очень слабой нижней границей. Я надеюсь, что может быть сокращение, которое доказывает, что

, но я не знаю, как построить такую вещь.]

f (n) = Ω (g (n) / n)

$f(n) = \Omega(g(n)/n)$

f (n) = Ω (g (n))

$f(n) = \Omega(g(n))$

Вот возможный подход:

Предположим, что вы знаете срез S, а затем нахождение потока от до является проблемой сетевого потока с минимальными затратами при нулевой стоимости, поскольку вы точно знаете отток в каждой вершине в и приток в . Предположим, что обозначает поток а - матрицу узловой дуги (т. Е. Строка , col имеет 1, если является хвостом , -1, если ее голова, в противном случае ноль), и пусть будет таким, что если $S$ $t$ $V\setminus S$ $t$ $f$ $S-t$ $A$ $i$ $j$ $i$ $j$ $b$ $Af = b$ $f$ удовлетворяет спрос / предложение и сохранение потока. Тогда с помощью исключения Гаусса мы можем найти допустимое решение в операции. $|V|^3$

Чтобы найти срез из потока, нам нужно построить остаточный граф, который принимает максимум время, а затем потенциально пройти Вершины. $|E|$ $|V|$

Таким образом, для полных графиков и минимального среза, являющегося только источником или только стоком, сокращение занимает одинаковое время в обоих направлениях в худшем случае. Тем не менее, я думаю, что нахождение возможного решения может быть сделано быстрее, чем учетом специальной структуры. Я не уверен, как доказать это, хотя. $Af =b$ $|V|^3$

Томас Босман
источник

Я не понимаю, как найти

с использованием исключения Гаусса. У нас есть

линейные уравнения в

Неизвестные. Обычно

, поэтому у нас не будет достаточно уравнений, чтобы однозначно определить неизвестных. Есть ли уловка, которую я пропускаю?

f

$f$

| V |

$|V|$

| E |

$|E|$

| E | > | V |

$|E|>|V|$

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

независимые столбцы. Тогда уникальное решение этой подматрицы и

сочетании с нулевым потоком для всех остальных столбцов даст неуникальное решение, которое само по себе не является проблемой. Проблема , которую я могу предвидеть, что

нарушает ограничения пропускной способности, но интуитивно я бы сказал , что есть способ , чтобы обойти это прямо

| V |

$|V|$

b

$b$

f

$f$

Томас Bosman

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

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

A f = b

$Af=b$

Дерьмо это правильно. Вы можете добавить ограничения (верхние и нижние), которые, как вы знаете, имеют решение, но тогда у вас есть | V | +2 | E | строк, так что это будет медленнее, чем просто вычисление максимального потока напрямую.

Томас Босман

Другая проблема заключается в том, что ограничения емкости - это неравенства (не равенства), поэтому вы не можете использовать исключение Гаусса: вам нужно использовать линейное программирование, которое, как вы говорите, вряд ли будет быстрее, чем просто вычисление максимальный поток напрямую.

Может ли минимальное сокращение быть проще, чем сетевой поток?

Ответы: