Cómo obtener el costo mínimo de desconectar un nodo entre sí en un gráfico

Question

En un gráfico dado, quiero calcular el costo mínimo de desconectar un nodo uno del otro en un gráfico. Ejemplo:
En este gráfico, supongamos que quiero desconectar node A, node C y node F eliminando algunos bordes entre estos nodos. es decir, al eliminar edge A-B y edge F-E, los nodos A, C y F se desconectarán. Aquí, costo significa la longitud del borde que se está eliminando. en este ejemplo, el costo mínimo total para desconectar Node A, Node C y Node F entre sí es 2 + 1 = 3.
¿Puede alguien dar alguna pista? No puedo categorizar este problema, si este es un tipo de shortest path problem o minimum spanning tree problem?

Answer 1

Esto se llama problema de corte multiterminal . Lamentablemente parece que no hay una entrada de Wikipedia. El problema es que, dado un gráfico ponderado y un subconjunto de vértices llamados terminales , calcule el conjunto de bordes de peso mínimo cuya eliminación desconecta cada par de terminales. La mala noticia es que este problema es NP-hard, por lo que si realmente necesita una solución óptima en una instancia que no puede ser forzada, es probable que deba recurrir a la programación entera. La buena noticia es que hay un algoritmo simple de 2 aproximaciones (no es el mejor factor conocido, pero puede que tenga que repasar su programación lineal y leer la literatura de investigación para usar las "mejores"), lo que se puede lograr tomando la unión de cortes de st separando cada terminal de los demás.