Aumentando la capacidad para maximizar el corte mínimo

Considere una gráfica con todas las aristas con capacidad unitaria. Uno puede encontrar el corte mínimo en tiempo polinómico.

Supongamos que se me permite aumentar la capacidad de cualquier bordes hasta el infinito (equivalente a fusionar los nodos a cada lado del borde). ¿Cuál es la forma óptima de seleccionar un conjunto óptimo de k bordes (cuya capacidad se incrementará hasta el infinito) para maximizar el corte mínimo?$k$$k$

Teorema. El problema en la publicación es NP-hard.

Por "el problema en la publicación", quiero decir, dado un gráfico y un entero k , elegir k bordes para aumentar las capacidades de manera de maximizar el corte mínimo en el gráfico modificado.$G=(V,E)$$k$$k$

La idea es reducir de Max Cut. Aproximadamente, un gráfico dado tiene un tamaño de corte máximo s si y solo si puede aumentar la capacidad de n - 2 bordes para que el gráfico resultante tenga un tamaño de corte mínimo s . La idea es que n - 2 aristas sean suficientes para forzar que el gráfico resultante tenga un solo corte de capacidad finita, y ese puede ser cualquier corte que elija.$G=(V,E)$$s$$n-2$$s$$n-2$

Esta idea no funciona del todo porque para obtener un corte dado , necesita que se conecten las subgrafías inducidas por C y V ∖ C cada una. Pero puede solucionar esto con un gadget apropiado.$(C, V\setminus C)$$C$$V\setminus C$

Prueba. Dado un gráfico conectado , defina un corte conectado como un corte ( C , V ∖ C ) de modo que las subgrafías inducidas por C y por V ∖ C estén conectadas. Defina Max Connected Cut como el problema de encontrar un corte conectado (en un gráfico conectado dado) maximizando el número de bordes que cruzan el corte.$G=(V,E)$$(C,V\setminus C)$$C$$V\setminus C$

Mostramos que Max Connected Cut reduce el problema en la publicación. Luego mostramos que Max Cut no ponderado se reduce a Max Connected Cut.

Lema 1. Max Connected Cut reduce en tiempo de polietileno al problema definido en la publicación.

Prueba. Dada una instancia de Max-Connected-Cut , sea k = | V | - 2 . Para probar el lema, demostramos lo siguiente:$G=(V,E)$$k=|V|-2$

Reclamación 1: Para cualquier , hay un corte conectado ( C , V ∖ C ) en G de capacidad al menos s , IFF es posible elevar las capacidades de borde k en G al infinito para que el gráfico resultante tenga un corte mínimo capacidad al menos s .$s>0$$(C,V\setminus C)$$G$$s$$k$$G$$s$

SÓLO SI: Supongamos que hay un corte conectado de capacidad al menos s . Deje que T 1 y T 2 sean subárboles que abarquen , respectivamente, C y V ∖ C , luego aumente las capacidades de los bordes en T 1 y T 2 . (Tenga en cuenta que | T 1 | + | T 2 | = | C | - 1 + | V ∖ $(C,V\setminus C)$$s$$T_1$$T_2$$C$$V\setminus C$$T_1$$T_2$ .) El único corte de capacidad finita que queda en el gráfico es entonces ( C , V ∖ C ) , de capacidad al menos s , por lo que el gráfico resultante tiene una capacidad de corte mínima al menos s .$|T_1|+|T_2|=|C|-1 + |V\setminus C|-1 = |V|-2 = k$$(C, V\setminus C)$$s$$s$

IF: suponga que es posible aumentar las capacidades de borde en G de modo que el gráfico resultante tenga una capacidad de corte mínima de al menos s . Considere el subgrafo formado por los k bordes elevados. Sin pérdida de generalidad, suponga que este subgrafo es acíclico. (De lo contrario, "levante" un borde de un ciclo de bordes levantados y, en su lugar, levante un borde no levantado que une dos componentes conectados del subgrafo. Esto solo aumenta el corte mínimo en el gráfico resultante). Mediante la elección de k = n - 2 , el subgrafo de bordes elevados tiene dos componentes conectados, digamos C y V ∖ $k$$G$$s$$k$$k=n-2$$C$$V\setminus C$, por lo que el único corte de capacidad finita en el gráfico resultante es . Y este corte tiene capacidad al menos s , como lo hizo en el gráfico original.$(C,V\setminus C)$$s$

Esto prueba el reclamo (y el lema). (QED)

Para completar, mostramos que Max Connected Cut es NP-complete, por reducción de Max Cut no ponderado.

Lema 2. El corte máximo no ponderado se reduce en tiempo polivinílico al corte máximo conectado .

Prueba. Para cualquier número entero , definen gráfico P ( N ) que consiste en dos trayectorias A y B , cada uno de longitud N , con los bordes de cada vértice en A a cada vértice en B . Lo dejamos como un ejercicio para el lector para verificar que el corte máximo en P ( N ) ( A en un lado, B en el otro) tenga un tamaño N 2 , y ningún otro corte tenga un tamaño mayor que, digamos, N 2 - N / 100 .$N\ge 1$$P(N)$$A$$B$$N$$A$$B$$P(N)$$A$$B$$N^2$$N^2-N/100$

Aquí está la reducción. Dada cualquier instancia de Max Cut no ponderada , construya un gráfico G ' = ( V ' , E ' ) de la siguiente manera. Deje n = | V | . Deje N = 100 ( n 2 + 2 n ) . Agregue a G el gráfico P ( N ) definido anteriormente (con sus dos rutas A y B ). De cada vértice$G=(V,E)$$G'=(V',E')$$n=|V|$$N = 100(n^2 + 2n)$$G$$P(N)$$A$$B$ añadir un borde a un vértice en A y otro borde de un vértice en B . Esto define la reducción. Para finalizar, demostramos que es correcto:$v\in V$$A$$B$

Reclamación 2: Para cualquier , hay un corte ( C , V ∖ C ) en G de capacidad al menos s , IFF hay un corte conectado en G ' de tamaño al menos s + N 2 + n .$s\ge 0$$(C,V\setminus C)$$G$$s$$G'$$s+N^2+n$

SÓLO SI: Dado cualquier corte en G de capacidad al menos s , considere el corte conectado ( A ∪ C , B ∪ V ∖ C ) en G ′ . Este corte conectado en G ' corta al menos s bordes de C a V ∖ C , más N 2 bordes de A a B , más n de los $(C,V\setminus C)$$G$$s$$(A\cup C, B\cup V\setminus C)$$G'$$G'$$s$$C$$V\setminus C$$N^2$$A$$B$$n$ bordes de V a A ∪ B .$2n$$V$$A\cup B$

IF: suponga que hay un corte conectado en de tamaño al menos s + N 2 + n . A y B están en lados opuestos del corte. (De lo contrario, dado que el segundo corte más grande en P ( N ) corta como máximo N 2 - N / 100 bordes en P ( N ) , el número total de bordes cortados es como máximo N 2 - N / 100 + | E | + 2 |$G'$$s+N^2+n$$A$$B$$P(N)$$N^2-N/100$$P(N)$ .) Let C denotan los vértices en V en el lado del corte con A . Luego hay N 2 bordes en el corte desde A a B , y n de V a A ∪ B , por lo que debe ser al menos s de C a V ∖ C .$N^2-N/100 + |E| + 2|V| \le N^2 - N/100 + n^2 + 2n = N^2$$C$$V$$A$$N^2$$A$$B$$n$$V$$A\cup B$$s$$C$$V\setminus C$

Esto prueba el reclamo y el Lema 2. (QED)

Según Lemmas 1 y 2, dado que Max Cut no ponderado es NP-hard, el problema en la publicación también es NP-hard.