Второй самый маленький

Что-нибудь известно о втором наименьшем - -резе в сети потока? Или, в общем, об этой проблеме: $s$ $t$

Вход: сеть и число , все в двоичном виде. Выход: наименьшее - вырезать. $N$ $k$
$k$ $s$ $t$

- й наименьший - разреза любые - вырезать, например , что существует ровно - порезы , чьи мощности $k$ $s$ $t$ $(S,T)$ $s$ $t$ $k-1$ $s$ $t$

попарно разные и
действительно меньше, чем емкость . $(S,T)$

Я хотел бы знать, как это может быть вычислено и может ли это быть сделано эффективно как для случая . $k=1$

cc.complexity-theory optimization max-flow-min-cut flow-problems Оливер Витт
источник

Вы можете найти второй наименьший срез, добавив

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

закодировано в унарном порядке (и, конечно, для константы

)

ϵ

$\epsilon$

k

$k$

k

$k$

Юваль Фильмус

Я не понимаю, как это помогает. Представьте себе сеть путей, состоящую из трех узлов

только с двумя ребрами

. Далее, пусть емкости будут

. Понятно, что минимальные срезы

и вторые самые маленькие срезы

s

$s$

v

$v$

t

$t$

(s, v)

$(s,v)$

(v, t)

$(v,t)$

c (s, v) = 1

$c(s,v)=1$

c (v, t) = 2

$c(v,t)=2$

(s, v)

$(s,v)$

. Увеличение производительности, как вы описали, снова даст

минимальное сокращение с производительностью

. Как я могу вывести второй самый маленький вырез из этого?

(v, t)

$(v,t)$

(s, v)

$(s,v)$

1 + ϵ

$1+\epsilon$

Оливер Витт

Добавление нижней границы на колпачок среза является линейным неравенством, просто добавьте на один эпсилон больше, чем колпачок min, и запустите LP. Вы можете повторить это k раз, чтобы получить то, что вы хотите. Это, вероятно, может быть изменено как модификация в сети, но я не разработал это.

Каве

Я вижу, как это работает, если

в унарной кодировке. Что, если это двоичный файл? В этом случае модификация сети не может быть выполнена за

итераций.

k

$k$

k

$k$

Оливер Витт

Я сомневаюсь, что есть простое решение, если k является двоичным. Мы можем проверить, есть ли срез крышки c, как я описал. Мне кажется, что, по сути, подсчет количества возможных c может быть связан с подсчетом количества совпадений и, возможно, # P-complete. (Это только моя интуиция, а не аргумент.)

Каве

Второй наименьший срез, а в более общем случае наименьших срезов, может быть найден во временном полиноме от и размера сети. Видеть: $k$ $k$

HW Hamacher. алгоритм для нахождения лучшие сокращения сети. Опер. Местожительство Lett. 1 (5): 186–189, 1982, doi: 10.1016 / 0167-6377 (82) 90037-2 . $(K\cdot n^4)$ $k$

HW Hamacher, J.-C. Пикард и М. Кейранн. Нахождение лучших сокращений в сети. Опер. Местожительство Lett. 2 (6): 303-305, 1984, doi: 10.1016 / 0167-6377 (84) 90083-X . $K$

HW Hamacher и M. Queyranne. лучшим решениям комбинаторных задач оптимизации. Энн. Опер. Местожительство 4 (1–4): 123–143, 1985, doi: 10.1007 / BF02022039 . $K$

Дэвид Эппштейн
источник

Разве они не позволяют равные веса среди лучших

? Кажется, вопрос задается о

наименьшем весе , который, как предполагает Каве, пахнет больше как проблема # P-complete.

k

$k$

k

$k$

Андраш Саламон

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

Оливер Уитт

Вопрос плохо сформулирован, потому что он запрашивает одну вещь (

й наименьший разрез), а затем добавляет ограничение, которое превращает вопрос во что-то другое (

й наименьший различимый вес среза). Я согласен с тем, что версия этой проблемы с весомым весом, вероятно, будет $ P-полной.

k

$k$

k

$k$

Дэвид Эппштейн

Второй самый маленький

Ответы: