Минимальное сечение в взвешенных ориентированных ациклических графах с возможно отрицательными весами

Я столкнулся со следующей проблемой:

Для заданного ориентированного ациклического графа с вещественными весами ребер и двумя вершинами s и t вычислим минимальный срез st.

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

Какова ситуация с группами доступности баз данных? Может ли минимальное сокращение (или максимальное сокращение) быть решено за полиномиальное время? Это NP-сложный и, если да, есть ли известные алгоритмы аппроксимации?

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

algorithms complexity-theory graph-theory weighted-graphs Джордж
источник

Где здесь не работает формулировка min-cut для линейного программирования?

Питер Шор

(используя запись из en.wikipedia.org/wiki/… ): Для ребер с отрицательными весами d_ {ij} может быть сколь угодно большим. Даже если один ограничивает d_ {ij} сверху, он всегда будет принимать максимально возможное значение для ребер с отрицательными весами. Таким образом, решение для такой программы не всегда даст правильный срез. Я могу ошибаться, потому что я не очень опытен с такими проблемами, если так, пожалуйста, поправьте меня. В основном я хотел бы знать, может ли максимальное сокращение (с произвольными весами) быть эффективно решено для DAG или нет.

Джордж

Чтобы это сработало, вы должны изменить первое неравенство на равенство: . Я до сих пор не понимаю, почему это не получается, но, может быть, я что-то упустил. Я не думал об этом много.

d_{i j} = p_{j} - p_{i}

$d_{ij} = p_j - p_i$

Питер Шор

Это, наверное, я что-то здесь упускаю. Гарантирует ли это, что все принимают целые значения? Можно связать сверху с 1, но я не уверен, работает ли это или нет. Похоже, проблема заключается в том, что если это можно решить, можно уменьшить до максимума обрезку путем изменения веса ребер, что не должно быть возможным, поскольку максимальный обрез является NP-трудным. Однако я могу ошибаться здесь.

p_{i}

$p_i$

p_{i}

$p_i$

Джордж

Является ли st max-cut NP-hard для DAG? Если график не DAG, вы не можете изменить это неравенство на равенство, потому что вам нужно неравенство, если есть циклы. Так что в общем случае LP не работает с отрицательными весами.

Питер Шор

Ответы:

Вы уточнили свою проблему еще в комментариях. Чтобы быть более точным, у вас есть DAG со всеми ребрами, вытекающими из источника направлении приемника (то есть все ребра находятся на пути от до ). Вы хотите найти минимальный разрез между двумя частями DAG, где первая часть связана с , а вторая - с . Для этой задачи работает вариант стандартного алгоритма линейного программирования для MIN-CUT, даже с отрицательным весом ребра. $s$ $t$ $s$ $t$ $s$ $t$

Мы используем те же обозначения, что и в Википедии . Стоимость ребра составляет . Мы размещаем потенциальную функцию на каждом узле, и пусть . LP является $(i,j)$ $c_{ij}$ $p_i$ $d_{ij} = p_i - p_j$

\begin{aligned} m i n i m i z e & \sum_{(i, j) \in E} c_{i j} d_{i j} \\ s u b j e c t t o & d_{i j} = p_{i} - p_{j} \forall (i, j) \in E \\ d_{i j} \geq 0 \forall (i, j) \in E \\ p_{s} = 1 \\ p_{t} = 0 \end{aligned}

$\begin{align*} \mathrm{minimize\ } & \sum_{(i,j) \in E} c_{ij} d_{ij} \\ \mathrm{subject\ to\ } & \ \ \ d_{ij} = p_i - p_j \ \ \forall (i,j) \in E \\ &\ \ \ d_{ij} \geq 0 \ \ \ \ \ \ \ \ \ \ \ \, \forall (i,j) \in E \\ & \ \ \ p_s\, = 1 \\ & \ \ \ p_t \, = 0 \end{align*}$

Эти уравнения гарантируют, что , так как каждая вершина находится на некотором - пути. Точно так же, поскольку неотрицательна, потенциалы на любом пути от до уменьшаются. Нам все еще нужно показать, что существует оптимальное решение для LP со всеми либо либо . Это следует из того факта, что значение для решения LP выше является ожидаемым значением разреза , где выбирается случайным образом в , и где разрез получается путем помещения всех вершин $0 \leq p_i \leq 1$ $s$ $t$ $d_{ij} = p_i - p_j$ $s$ $t$ $p_i$ $0$ $1$ $C_w$ $w$ $[0,1]$ $C_w$ $i$ с в первом наборе вершин и всеми вершинами с во втором наборе. $p_i\geq w$ $p_i < w$

Питер Шор
источник

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

0 \leq p_{i} l e q 1

$0 \leq p_i leq 1$

Джордж

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

Питер Шор

Хорошо, я буду искать это. Еще раз большое спасибо за вашу помощь!

Джордж