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

Question

Задача задается следующим образом: с учетом DAG и числа 0 < p ≤ 1вернуть минимальный набор вершин, который разъединяет по крайней мере p-разделение путей от источника (т. е. без входящих дуг) до приемника (т. е. без исходящих дуг). За p = 1проблема эквивалентна минимальному сокращению. Для других значений pОднако я не уверен, что ответ будет.

Алгоритм, о котором я думаю, состоит в том, чтобы сначала вычислить минимальный набор для DAG, а затем попытаться сократить его, чтобы удовлетворить критериям. Само по себе интересно посмотреть, является ли подмножество, которое мы находим, на самом деле минимальным набором сокращений для конкретного p это дано. Проблема этого алгоритма состоит в том, что он расточителен, потому что он вычисляет много узлов, которые нам не нужны в конечном ответе, и фактически решает "большую" проблему в первую очередь.

Какие-нибудь указатели на решение этой проблемы? Разве не возможно, что для некоторых алгоритмов минимального разреза мы добавим это дополнительное ограничение в качестве критерия ранней остановки?

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

Answer 1

Вот идея для получения примерно оптимальных решений.

Есть вариант покрытия наборов, который я хочу назвать частичным набором покрытий, где у нас есть наборы и элементы и мы хотим получить минимальное количество наборов, объединение которых содержит p-долю элементов. Чтобы применить к этой задаче, наборы соответствуют узлам, а элементы соответствуют максимальным путям. (Да, слишком много путей, чтобы сделать это наивно; см. Ниже.) Набор содержит элемент тогда и только тогда, когда узел содержится в пути.

Не так сложно написать частично заданную обложку в виде целочисленной программы.

minimize sum_{sets S} x_S
subject to
for all elements e, sum_{sets S containing e} x_S >= y_e
sum_{elements e} y_e >= p * number of elements
for all sets S, x_S in {0, 1}      # 1 if set S is chosen
for all elements e, y_e in [0, 1]  # 1 if element e is covered

Эта программа может быть решена с помощью целочисленного решателя программ. Решатели на удивление хороши, хотя они, конечно, не могут обещать оптимальных решений для этого обобщения покрытия NP-жесткого набора.

В интересном DAG, конечно, слишком много путей для перечисления. Выборка на помощь! Так как в DAG легко подсчитать максимальные пути, их можно легко выбрать случайным образом. Пример нескольких путей и использовать их в качестве элементов в целочисленной программе.

Компромисс состоит в том, что при большем количестве путей оценка цели лучше, но время для решения целочисленной программы хуже. Неравенство Хеффдинга дает некоторую подсказку о правильном выборе количества образцов. С n вершинами существует 2^n возможных решений. Мы хотим, чтобы расчетная доля для каждого из них была точной с точностью до эпсилона. Хеффдинг говорит, что нам нужно выбрать число отсчетов, которое должно быть тэта (н / эпсилон ^2), чтобы почти все время все оценки были приблизительно правильными. Я бы разработал точную константу, но я сомневаюсь, что это практически актуально.

Answer 2

EDIT1: после просмотра обновления OP, это решение применяется к случаю одного источника u и одного приемника v.

РЕДАКТИРОВАТЬ 2: это на самом деле эвристика, см. Контрпример в комментариях ниже.

Это решение O(V+E), основанное на методе подсчета путей, представленном в следующем потоке (на это указывает David Eisenstat, спасибо):

Количество путей между двумя узлами в группе обеспечения доступности баз данных

На первом этапе мы будем применять именно "обратный" метод, предложенный Сталкером. В конце этого этапа мы получим и сохраним следующую информацию:

• Для каждой вершины i число F(i, v) путей от i до v

• F(u, v) - количество путей от источника u к стоку v.

На втором этапе мы продвигаемся вперед тем же методом: мы моделируем алгоритм, как если бы вопрос заключался в том, чтобы найти "обратные пути" от v до u. В конце мы получаем:

• Для каждой вершины i число B(i, u) обратных путей от i до u. Очевидно, B(i, u) = F(u, i)

• B (v, u), который равен F(u, v).

На третьем этапе мы вычисляем для каждой вершины i число P(i) = F(u, i) * F(i, v). Легко доказать, что число (u, v) путей, которые пересекают i, равно P(i). Следовательно, удаление вершины i приводит к удалению путей P(i).

На четвертом и последнем этапе мы поступаем жадным образом: удаляем вершину с наибольшим P (i), пока общее количество удаленных путей не превысит p*F(u, v)

Общий алгоритм O(V+E), так как:

• Согласно справочному посту, первые две фазы O(V+E).

• Третья и четвертая фазы, очевидно, O(V), следовательно, O(V+E)