Является ли логический Min-Cut NP-Complete?

Определение логической задачи Min Cut (LMC)

Предположим, что $G = (V, E)$ - невзвешенный орграф, $s$ и $t$ - две вершины $V$ , и $t$ достижимо из $s$ . Задача LMC изучает, как мы можем сделать $t$ недостижимым из $s$ путем удаления некоторых ребер $G$ следуя следующим ограничениям:

1. Количество удаленных ребер должно быть минимальным.
2. Мы не можем удалить каждое выходное ребро любой вершины из $G$ (т. Е. Ни одна вершина с исходящими ребрами не может удалить все свои исходящие ребра).

Это второе ограничение называется логическим удалением. Таким образом, мы ищем логическое, минимальное удаление некоторых ребер $G$ , чтобы $t$ было недоступно из $s$ .

Попытки решения

Если мы проигнорируем логическое ограничение удаления задачи LMC, это будет проблема минимального разреза в невзвешенном орграфе $G$ , поэтому она будет разрешима полиномиально (теорема о максимальном потоке минимального разреза).

Если мы проигнорируем ограничение минимального удаления задачи LMC, она снова будет полиномиально разрешима в DAG: найдите вершину $k$ такую, что $k$ достижима из $s$ а $t$ не достижима из $k$ . Затем рассмотрим путь $p$ который является произвольным путем от $s$ до $k$ . Теперь рассмотрим путь $p$ как подграф графа $G$ : ответом будет каждое выходное ребро подграфа $p$ . Очевидно, что вершина $k$ может быть найдена DFS в $G$ за полиномиальное время. К сожалению, этот алгоритм не работает в целом для произвольного ориентированного графа.

Я пытался решить проблему LMC с помощью техники динамического программирования, но число необходимых состояний для решения проблемы стало экспоненциальным. Более того, я попытался уменьшить некоторые проблемы NP-Complete, такие как 3-SAT, max2Sat, max-cut и clique, до проблемы LMC, которую мне не удалось найти.

Лично я считаю, что проблема LMC является NP-Complete, даже если является двоичной группой обеспечения доступности баз данных (т. Е. Группой обеспечения доступности баз данных, где ни один узел не имеет выходной степени больше 2).$G$

Вопросов

1. Является ли задача ЛКМ NP-полной в произвольном орграфе ? (основной вопрос)$G$
2. Является ли задача LMC NP-полной в произвольном DAG ?$G$
3. Является ли задача LMC NP-полной в произвольном двоичном DAG ?$G$

Пусть G = (V, E) - взвешенная группа DAG, s и t - две вершины G, а LSTMC = (G, s, t) - пример логической задачи о сокращении в мин. Очевидно, что проблема LSTMC - это NP. Теперь мы должны показать, что LSTMC - это NP-Hard. Мы сводим проблему со множеством ударов к задаче LSTMC. Пусть S = {s1, s2, ..., sn} - заданные множества, а {a1, a2, ..., am} - объединение всех множеств. При заданном числе k1 в задаче решения задачи о множестве ударов указывается, существует ли множество A с k1 элементами, такое, что каждый элемент S (каждый набор si st i = 1..n) содержит хотя бы один элемент из A. обозначим задачу о множестве ударов через HS (S). Построим взвешенный DAG G ′ из множества S по алгоритму HS2LSTMC. Этот алгоритм рассматривает s как исходную вершину DAG G ′. Для каждого множества si HS st i = 1..n алгоритм рассматривает соответствующую вершину, si и добавляет ребро с бесконечным весом от s к каждому si. Затем для каждого элемента aj объединения входных множеств st j = 1..m алгоритм рассматривает соответствующую вершину aj и добавляет ребро с нулевым весом из каждого si к любому aj st aj ∈si в HS. Наконец, алгоритм рассматривает две конечные вершины, называемые t и k, и добавляет два ребра из каждого aj st j = 1..m в обе конечные вершины. Понятно, что G ′ можно сделать за полиномиальное время.

Теперь мы должны продемонстрировать, что HS (S) имеет ответ с k1 элементами тогда и только тогда, когда LSTMC = (G, s, t) имеет ответ с некоторыми логически удаленными ребрами, так что сумма весов удаленных ребер равна k1.

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

На следующем рисунке предположим, что S = {s1, s2, s3} такое, что s1 = {1, 2, 3}, s2 = {1, 4} и s3 = {2, 5}. На рис. 2 показан взвешенный DAG G 'задачи LSTMC, соответствующий задаче HS (S) со множеством ударов. В этом примере множество A, а именно объединение всех элементов S, имеет вид A = {1, 2, 3, 4, 5}. У нас есть | S | = 3 и | A | = 5. В этом примере показано, как можно решить произвольный случай задачи с множеством ударов с помощью конкретного экземпляра задачи с минимальным вырезанием в взвешенной группе обеспечения доступности баз данных. Если мы вычислим ответ на LSTMC = (G ′, s, t) и рассмотрим те удаленные ребра ответа, которые имеют вид (aj, t), называемый E1 (1 ≤ j ≤ m), то набор хвостов E1 является ответом на HS (S). Ответом на проблему LSTMC является множество ребер E1 = {(s1, 2), (s1, 3), (s2, 4), (s3, 5), (1, t), (2, t)}. Итак, множество хвостов подмножества E2 = {(1, t), (2,

Вот (попытка) алгоритм полиномиальное время для БМО на произвольное бинарное DAGs .$G$

Это отвечает на вопрос № 3. (Извините за грязную переписку заранее. :))

Для начала отбросим "навсегда" любую вершину, недоступную из . Мы не заботимся о них, так как они не являются частью любого s - т пути.$s$$s$$t$

Затем определите вложенные группы DAG и B , изначально пустые. Тогда для всех вершин v ∈ G - { s , t } ,$A$$B$$v \in G-\{s, t\}$

Проверьте, существует ли путь от до t . Если это так, добавьте V к A . Если нет, добавьте V к B .$v$$t$$v$$A$$v$$B$

Пусть ребра и B будут те , индуцированных вершинами в пределах каждого набора (на данный момент, игнорировать любые ребра из S к А , от А до т , и от A до B , также отметить , нет ребра от B к т пути строительство).$A$$B$$s$$A$$A$$t$$A$$B$$B$$t$

Затем вычислить транзитивное замыкание . А именно, мы заинтересованы в поиске некоторого множества вершин { * } , которые являются «листья» из суб-DAG А .$A$$\{a^*\}$$A$

Исправьте все такое . Обратите внимание , что должно быть направлено ребро от с * до т . Это связано с тем, что по построению (i) существует путь s - t через a ∗ , (ii) нет путей от a ∗ до B , и (iii) поскольку A само является DAG, а a ∗ является листом в A нет пути из a ∗ через другую вершину из A в t .$a^*$$a^*$$t$$s$$t$$a^*$$a^*$$B$$A$$a^*$$A$$a^*$$A$$t$

Теперь также должно быть направленное ребро от каждой вершины в до некоторой вершины в B , или у некоторых из { a ∗ } есть одно ребро к t . В любом случае мы можем удалить любое ребро a ∗ → t .$\{a^*\}$$B$$\{a^*\}$$t$$a^*\rightarrow t$

Если = 1, то либо мы должны удалить ребро из уникального a ∗ → t , либо в пути s - t ранее есть вершина, содержащая a ∗, которая имеет два пути к t - один через a ∗ и один непосредственно. В случае, если последнее может иметь место, мы записываем a ∗ → t и действуем «жадно назад» (подробности об этом ниже).$|\{a^*\}|$$a^*\rightarrow t$$s$$t$$a^*$$t$$a^*$$a^*\rightarrow t$

Если > 1, то мы должны либо удалить все ребра из { a ∗ } → t , либо существует некоторое количество ребер k < | { a ∗ } | ранее в транзитивном замыкании A, которое разъединяет все пути от s через { a ∗ } к t .$|\{a^*\}|$$\{a^*\}\rightarrow t$$k < |\{a^*\}|$$A$$s$$\{a^*\}$$t$

Здесь мы используем тот факт, что граф является двоичным DAG.$G$

Рассмотрим множество предшественников . Поскольку каждая из этих вершин имеет внешнюю степень не более двух, существует ровно три случая:$\{a^*\}$

Случай 1. Предшественник имеет затраченной край к некоторой вершине в и из-края до некоторой вершины в B .$\{a^*\}$$B$

В этом случае не имеет значения, удаляем ли мы ребро из предшественника в вершину в или ребро из вершины в { a ∗ } в t . Следовательно, мы можем «пропустить» эту вершину (и проверить, сливается ли обратный путь с путем другой вершины в { a ∗ } ).$\{a^*\}$$\{a^*\}$$t$$\{a^*\}$

Случай 2. Предшественник имеет выход к вершине в и другой предшественник { a ∗ } .$\{a^*\}$$\{a^*\}$

In this case, we must either delete both edges from the $\{a^*\}$ to $t$, or we can delete a single earlier edge in the path from $s$ to the predecessor that disconnects both paths.

Case 3. A predecessor has an out-edge to two vertices in $\{a^*\}$.

This is identical to case 2. It doesn't matter whether we delete one of this predecessor's edges and the corresponding other edges from $\{a^*\}$ to $t$, or both of the edges from the $\{a^*\}$ to $t$. We just want to know whether we can disconnect the path from $s$ through this predecessor to $t$ with a single edge earlier in the path from $s$ to the predecessor.

В целом, когда мы сканируем в обратном направлении через предшественников в транзитивном замыкании , мы можем жадно отслеживать «лучший на данный момент» выбор. То есть на каждом этапе у нас есть очевидный выбор, который включает в себя удаление некоторого количества ребер, но мы хотим подождать, чтобы увидеть, доступен ли лучший вариант. Как только найден лучший вариант, мы можем «забыть» о предыдущем варианте. Следовательно, достаточно жадного выбора на каждом уровне предшественников (пока мы ждем до конца, чтобы совершить любой выбор).$A$

Therefore, with some basic memoization, the time and space complexities of this process appear to be at most $O(|E|)$. This leaves out the fact that, while we can locally/greedily identify when we have found a "cheaper choice," it's a priori unclear which previously-recorded edges to remove. Therefore, we record the order in which we check edges as we go. Upon finding a better option, we repeat the search up to this point in order to find which previously-recorded edges to remove. The total time complexity of this step is $O(|E|^2)$ and space complexity $O(|E|)$.

Altogether, the time complexity is $O(|V|\cdot(|V|+|E|))$ for initialization, plus $O(|V|^3)$ for the transitive closure, plus $O(|E|^2)$ for the search. The total time is $O(|V|^2+|E||V|+|V|^3+|E|^2) = {\bf O(|V|^3+|E|^2)}$.

Upon completing the process, we obtain the minimum set of edges required to disconnect $s$ from $t$ while preserving at least one out-edge of every vertex in the graph (or we discover that a solution is impossible along the way, and abort).