¿Es lógico Min-Cut NP-Complete?

Definición del problema de corte lógico mínimo (LMC)

Supongamos que es un dígrafo no ponderado, y son dos vértices de , y es alcanzable desde . El problema de LMC estudia cómo podemos hacer que inalcanzable desde mediante la eliminación de algunos bordes de siguiendo las siguientes restricciones: $G = (V, E)$ $s$ $t$ $V$ $t$ $s$ $t$ $s$ $G$

El número de bordes eliminados debe ser mínimo.
No podemos eliminar todos los bordes de salida de ningún vértice de (es decir, ningún vértice con bordes salientes puede eliminar todos sus bordes salientes). $G$

Esta segunda restricción se llama eliminación lógica. Por lo tanto, buscamos una eliminación lógica y mínima de algunos bordes de manera que sea inalcanzable desde . $G$ $t$ $s$

Intentos de solución

Si ignoramos la restricción de eliminación lógica del problema LMC, será el problema de corte mínimo en el dígrafo no ponderado , por lo que será solucionable polinomialmente (teorema de corte mínimo de flujo máximo). $G$

Si ignoramos la restricción mínima eliminación del problema LMC, será polinómicamente nuevo solucionable en un DAG: encontrar un vértice que dicha es alcanzable desde y no es accesible desde . Luego considere una ruta que es una ruta arbitraria de a . Ahora considere la ruta como un subgrafo de : la respuesta será cada borde de salida del subgrafo . Es obvio que el vértice puede ser encontrado por DFS en en tiempo polinómico. Lamentablemente este algoritmo no funciona en general $k$ $k$ $s$ $t$ $k$ $p$ $s$ $k$ $p$ $G$ $p$ $k$ $G$ para un gráfico dirigido arbitrario.

Traté de resolver el problema de LMC mediante una técnica de programación dinámica, pero el número de estados requeridos para resolver el problema se volvió exponencial. Además, traté de reducir algunos problemas de NP-Complete como 3-SAT, max2Sat, max-cut y clique al problema de LMC. No logré encontrar una reducción.

Personalmente, creo que el problema de LMC es NP-Complete, incluso si $G$ es un DAG binario (es decir, un DAG donde ningún nodo tiene un grado de salida superior a 2).

Preguntas

¿Está el problema LMC NP-Completo en un dígrafo arbitrario $G$ ? (pregunta principal)
¿El problema de LMC es NP-Complete en un DAG arbitrario $G$ ?
¿El problema de LMC es NP-Complete en un DAG binario arbitrario $G$ ?

complexity-theory graph-theory np-complete amirv
fuente

Estoy bastante seguro de que el problema está en

si su gráfico no está dirigido . ¿Sería esa una respuesta suficiente a su pregunta?

P

$\mathrm{P}$

Alex ten Brink

@SaeedAmiri: encontrar un mínimo de corte de

. Si desconecta un vértice, entonces este vértice debe ser

. Si son ambas cosas, entonces no hay tal corte mínimo. Supongamos que

es el vértice desconectado y

el borde. Eliminar este borde y realizar una min-corte en

de forma recursiva.

s

$s$

t

$t$

s

$s$

t

$t$

t

$t$

(t, v)

$(t,v)$

s

$s$

v

$v$

Alex ten Brink

Por una simple observación, se puede concluir que si el siguiente problema es NP-Complete, entonces el problema de LMC también será NP-Complete (no estoy seguro de que el inverso sea verdadero). Suponga que es un dígrafo. Cómo podemos tener un corte mínimo en (partición a y st el número de bordes de a es mínimo) y no existe un vértice pertenece a st la cabeza de cada borde de salida de pertenece a (el borde de salida es de a $G=(V,E)$ $G$ $V$ $S$ $T$ $S$ $T$ $v$ $V$ $v$ $T$ $S$ ) $T$

amirv

Crosspost

Tsuyoshi Ito

Amirv, para el problema con solo la restricción (2), el algoritmo que sugiere, según tengo entendido, no es del todo correcto. Puede haber una solución aunque, para todos los nodos v, hay una ruta de s a v y una ruta de v a t. Considere la gráfica

con

G = (V, E)

$G=(V,E)$

V = {s, t, a}

$V=\{s,t,a\}$

E = {(s, t), (s, a), (a, s)}

$E=\{(s,t),(s,a),(a,s)\}$

Neal Young el

Respuestas:

Sea G = (V, E) un DAG ponderado, syt son dos vértices de G, y LSTMC = (G, s, t) sea una instancia del problema lógico de corte mínimo. Es obvio que el problema de LSTMC es NP. Ahora, debemos mostrar que el LSTMC es NP-Hard. Reducimos el problema del conjunto de golpes al problema LSTMC. Sea S = {s1, s2, ..., sn} los conjuntos dados y {a1, a2, ..., am} sea la unión de todos los conjuntos. Dado el número k1, el problema de decisión del problema del conjunto de golpes establece si existe un conjunto A con elementos k1 de manera que cada elemento de S (cada conjunto si st i = 1..n) contenga al menos un elemento de A. denota el problema del conjunto de golpes como HS (S). Construimos el DAG ponderado G 'del conjunto S por el algoritmo HS2LSTMC. Este algoritmo considera s como el vértice fuente del DAG G '. Para cada conjunto si de HS st i = 1..n, el algoritmo considera el vértice correspondiente, si, y agrega una ventaja con un peso infinito de s a cada si. Luego, para cada elemento aj de la unión de los conjuntos de entrada st j = 1..m, el algoritmo considera el vértice correspondiente, aj, y agrega una arista con peso cero de cada si a cualquier aj st aj ∈si en HS. Finalmente, el algoritmo considera dos vértices finales llamados t y k, y agrega dos aristas de cada aj st j = 1..m a ambos vértices finales. Está claro que G 'puede hacerse en tiempo polinomial.

Ahora, deberíamos demostrar que HS (S) tiene una respuesta con elementos k1 si y solo si LSTMC = (G ', s, t) tiene una respuesta con algunos bordes eliminados lógicamente, de modo que la suma de los pesos de los bordes eliminados es k1.

Para simplificar, realizamos esta parte de la prueba, proporcionando un ejemplo:

En la siguiente figura, suponga que S = {s1, s2, s3} tal que s1 = {1, 2, 3}, s2 = {1, 4} y s3 = {2, 5}. La figura 2 muestra el DAG ponderado G 'del problema LSTMC correspondiente al problema del conjunto de golpe HS (S). En este ejemplo, el conjunto A, es decir, la unión de todos los elementos de S, es A = {1, 2, 3, 4, 5}. Tenemos | S | = 3 y | A | = 5. Este ejemplo muestra cómo se puede resolver una instancia arbitraria del problema del conjunto de golpes con la ayuda de una instancia específica del problema lógico de corte mínimo en un DAG ponderado. Si calculamos una respuesta a LSTMC = (G ', s, t) y consideramos aquellos bordes eliminados de la respuesta que están en forma de (aj, t) llamados E1 (1 ≤ j ≤ m), entonces el conjunto de cola de E1 es una respuesta a HS (S). Una respuesta al problema LSTMC es el conjunto de bordes E1 = {(s1, 2), (s1, 3), (s2, 4), (s3, 5), (1, t), (2, t)}. Entonces, el conjunto de cola del subconjunto E2 = {(1, t), (2,

amirv
fuente

Aquí está (un intento de) un algoritmo de tiempo polinómico para LMC en arbitraria binario DAGs . $G$

Esto responde a la Pregunta # 3. (Perdón por la crítica desordenada por adelantado. :))

Para comenzar, deseche "para siempre" cualquier vértice no accesible desde . No nos importa acerca de estos, ya que no son parte de ningún - ruta. $s$ $s$ $t$

A continuación, defina los sub-DAG y , inicialmente vacíos. Entonces, para todos los vértices , $A$ $B$ $v \in G-\{s, t\}$

Pruebe si hay una ruta desde hasta . Si es así, añadir a . Si no es así, añadir a . $v$ $t$ $v$ $A$ $v$ $B$

Deje que los bordes de y sean los inducidos por los vértices dentro de cada conjunto (por ahora, ignore cualquier borde de a , de a y de a ; también tenga en cuenta que no hay bordes de a por construcción). $A$ $B$ $s$ $A$ $A$ $t$ $A$ $B$ $B$ $t$

A continuación, calcular el cierre transitivo de . Es decir, estamos interesados en encontrar un conjunto de vértices que son las "hojas" de la sub-DAG . $A$ $\{a^*\}$ $A$

Fijar dicha . Observe que debe haber un borde dirigido de a . Esto es porque, por construcción, (i) hay una - camino a través de , (ii) no hay caminos de a través de , y (iii) desde es en sí misma un DAG y es una hoja de , no hay camino desde través de otro vértice de hasta . $a^*$ $a^*$ $t$ $s$ $t$ $a^*$ $a^*$ $B$ $A$ $a^*$ $A$ $a^*$ $A$ $t$

Ahora, también debe haber un borde dirigido desde cada vértice en a algún vértice en , o algunos de los tienen un solo borde a . En cualquiera de los casos, se nos permite eliminar cualquier borde. $\{a^*\}$ $B$ $\{a^*\}$ $t$ $a^*\rightarrow t$

Si = 1, entonces debemos eliminar el borde de la única , o hay un vértice anterior en la ruta - que contiene que tiene dos rutas hacia - una a través de y otra directamente. En caso de que este último se mantenga, registramos procedemos "hacia atrás con avidez" (detalles sobre esto a continuación). $|\{a^*\}|$ $a^*\rightarrow t$ $s$ $t$ $a^*$ $t$ $a^*$ $a^*\rightarrow t$

Si > 1, entonces debemos eliminar todos los bordes de , o bien hay algún número de bordes anteriormente en el cierre transitivo de que desconecta todos los caminos de través de a . $|\{a^*\}|$ $\{a^*\}\rightarrow t$ $k < |\{a^*\}|$ $A$ $s$ $\{a^*\}$ $t$

Aquí es donde usamos el hecho de que el gráfico es un DAG binario. $G$

Considere el conjunto de predecesores de . Dado que cada uno de estos vértices tiene un grado externo como máximo en dos, existen exactamente tres casos: $\{a^*\}$

Caso 1. Un precursor tiene un fuera de punta a algún vértice en y un cabo de punta a algún vértice en . $\{a^*\}$ $B$

En este caso, no importa si eliminamos el borde del predecesor al vértice en o el borde del vértice en a . Por lo tanto, podemos "saltar" este vértice (y verificar si la ruta hacia atrás se fusiona con una ruta de otro vértice en ). $\{a^*\}$ $\{a^*\}$ $t$ $\{a^*\}$

Caso 2. Un predecesor tiene un borde externo a un vértice en y otro predecesor de . $\{a^*\}$ $\{a^*\}$

En este caso, debemos eliminar ambos bordes de a , o podemos eliminar un solo borde anterior en la ruta de al predecesor que desconecta ambas rutas. $\{a^*\}$ $t$ $s$

Caso 3. Un predecesor tiene un borde exterior a dos vértices en . $\{a^*\}$

Esto es idéntico al caso 2. No importa si eliminamos uno de los bordes de este predecesor y los otros bordes correspondientes de a , o ambos bordes de a . Solo queremos saber si podemos desconectar la ruta de través de este predecesor a con un solo borde anterior en la ruta de al predecesor. $\{a^*\}$ $t$ $\{a^*\}$ $t$ $s$ $t$ $s$

En total, a medida que exploramos hacia atrás a través de predecesores en el cierre transitivo de , podemos seguir con avidez las "mejores opciones hasta ahora". Es decir, en cada paso, tenemos una opción obvia que implica eliminar una cierta cantidad de bordes, pero queremos esperar para ver si hay una mejor opción disponible. Una vez que se encuentra una mejor opción, podemos "olvidarnos" de la opción anterior. Por lo tanto, una elección codiciosa en cada capa de predecesores es suficiente (siempre que esperemos hasta el final para comprometernos con cualquier opción). $A$

$O(|E|)$ $O(|E|^2)$ $O(|E|)$ .

$O(|V|\cdot(|V|+|E|))$ $O(|V|^3)$ $O(|E|^2)$ $O(|V|^2+|E||V|+|V|^3+|E|^2) = {\bf O(|V|^3+|E|^2)}$

$s$ $t$

Daniel Apon
fuente

{a^{*}}

$\{a^∗\}$

B

$B$

{a^{*}}

$\{a^∗\}$

t

$t$

(a^{*}, t)

$(a^∗,t)$

a^{*}

$a^*$

{a^{*}}

$\{a^*\}$

s

$s$

{a *}

$\{a*\}$

a

$a$

A

$A$

Finalmente logré demostrar que este problema es NP-Complete.

amirv

@amirv Oh, por favor haga cuota de un esquema de la prueba en la forma de una respuesta!

Raphael

El problema es NP-Complete, incluso si el dígrafo subyacente es un DAG binario no ponderado.

amirv