Come ottenere il costo minimo di disconnessione di alcuni nodi gli uni dagli altri in un grafico

Question

In un dato grafico, voglio calcolare il costo minimo di disconnessione di alcuni nodi gli uni dagli altri in un grafico. Esempio:
In questo grafico, diciamo che voglio disconnettere node A, node C e node F l'uno con l'altro rimuovendo alcuni spigoli tra questi nodi. Ad esempio, rimuovendo edge A-B e edge F-E, i nodi A, C e F verranno disconnessi. Qui costo indica la lunghezza del bordo che viene rimosso. in questo esempio, il costo totale minimo per la disconnessione di Node A, Node C e Node F tra loro è 2 + 1 = 3.
Qualcuno può fornire qualche suggerimento. Non riesco a classificare questo problema, se si tratta di una specie di shortest path problem o minimum spanning tree problem?

Answer 1

Questo è chiamato il problema di taglio multiterminale . Sfortunatamente non sembra esserci una voce di Wikipedia. Il problema è che, dato un grafico ponderato e un sottoinsieme di vertici chiamati terminali , calcolare il set di spigoli di peso minimo la cui rimozione disconnette ogni coppia di terminali. La cattiva notizia è che questo problema è NP-difficile, quindi se hai davvero bisogno di una soluzione ottimale su un'istanza che non può essere forzata bruta, probabilmente dovrai passare alla programmazione di interi. La buona notizia è che c'è un semplice algoritmo di 2-approssimazione (non il miglior fattore conosciuto, ma potrebbe essere necessario rispolverare la programmazione lineare e leggere la letteratura di ricerca per usare quelli "migliori"), che può essere ottenuto prendendo l'unione di st cuts che separa ciascun terminale dagli altri.