Podando un dígrafo fuertemente conectado

Dado un dígrafo G fuertemente conectado con bordes ponderados, me gustaría identificar los bordes que probablemente no sean parte de ningún subgráfico mínimo fuertemente conectado (MSCS) de G.

Un método para encontrar tales bordes es un algoritmo de Floyd-Warshall modificado. Usando el algoritmo Floyd-Warshall, uno puede identificar qué bordes nunca son la mejor opción para pasar del vértice i al j. Estos nodos no pueden ser parte de un MSCS porque es mejor reemplazarlos con otros dos o más bordes.

La técnica de poda Floyd-Warshall funciona bastante bien cuando los pesos de los bordes varían significativamente, pero muy poco cuando los pesos de los bordes son similares pero de gran magnitud.

¿Conoces algún método de poda efectivo para pesas de borde grandes y similares? ¿Es este problema equivalente a un problema más común que no reconozco? ¿Se ha estudiado este tipo de poda antes en la literatura?

Asumimos que los pesos de borde son enteros positivos. Dado un gráfico dirigido G con pesos de borde, llame a un borde e redundante si e no pertenece a ningún subgrafo de G con un peso mínimo fuertemente conectado .

Afirmamos que a menos que P = NP, no existe un algoritmo de tiempo polinómico que siempre encuentre un borde redundante en un gráfico dirigido dado con pesos de borde siempre que haya uno. Más precisamente:

Teorema . Dado un gráfico dirigido G con pesos de borde, es NP-difícil encontrar un borde redundante en G o declarar que G no tiene un borde redundante.

Prueba . La observación clave es que si G tiene un subgrafo de expansión con un peso mínimo único fuertemente conectado, entonces puede calcular ese subgrafo eliminando los bordes redundantes uno por uno. Por lo tanto, queda por demostrar que la singularidad no hace que el problema del subgrafo de expansión de peso mínimo fuertemente conectado sea más fácil, pero esto lo demuestra el próximo Lema. QED .

Lema . Dado un gráfico dirigido G con pesos de borde, es NP-difícil calcular el peso del subgrafo de expansión de peso mínimo fuertemente conectado de G incluso bajo la promesa de que G tiene un subgrafo de expansión de peso mínimo y fuertemente conectado.

Prueba . Como saben , el problema sin la promesa es NP-duro (incluso para el caso de la unidad de peso) por una reducción del problema del circuito de Hamilton. Reducimos el problema sin la promesa al problema con la promesa.

Deje G ser un gráfico dirigido con pesos de borde. Etiqueta de los bordes de G por e ₀ , e ₁ , ..., e _{m -1} , donde m es el número de aristas en G . Let w _i ser el peso dado del borde ae _i . Sea el nuevo peso w ′ _i = 2 ^m w _i +2 ⁱ . Entonces es fácil verificar que G con los nuevos pesos tiene un subgrafo de expansión de peso mínimo único fuertemente conectado. También es fácil verificar que el peso mínimoW de un subgrafo de expansión fuertemente conectado en G con los pesos originales se puede calcular a partir del peso mínimo W 'en G con los nuevos pesos como W = ⌊ W ′ / 2 ^m ⌋. QED .