Trova il taglio minimo in un grafico tale che i vertici dati siano disconnessi

Question

Qualche tempo fa ho letto sull'algoritmo generale mininum cut che prende come input un grafico e rimuove un min. numero di spigoli tale che rimangono due componenti sconnessi.

Attualmente sto lavorando a un grafico non orientato con 10k + nodi e 500k + bordi (non più spigoli tra due vertici). Per attribuire interazioni tra nodi ho pensato di calcolare il taglio minimo scollegando due vertici dati (o misure relative al flusso).

Esistono algoritmi efficienti per ottenere un valore (cardinalità del set di taglio minimo) per ogni coppia di vertici nel grafico? Essendo piuttosto nuovo all'argomento, sarei profondamente grato se qualcuno potesse fornire collegamenti a documenti o altre risorse che delineano algoritmi che operano a una ragionevole complessità di runtime.

Grazie!

Answer 1

Esistono diversi algoritmi (vedere Wiki per un'introduzione) che trovano un flusso massimo in una rete. Quelli che conosco (Ford-Fulkerson, Dinic, Karp-Edmond) dovrebbero funzionare bene per la capacità dell'unità (= capacità intera pari a 1 su tutti i bordi) (le capacità variabili aumentano la complessità e aumentano i problemi con capacità non interi)

Per qualsiasi coppia di vertici, si crea una rete dal grafico impostando sorgente/sink su questa coppia. Si ottiene il flusso massimo utilizzando uno degli algoritmi, che si utilizza per ottenere il taglio nel modo seguente:

• Scegliere qualsiasi bordo utilizzato dal flusso. Questo bordo apparterrà al taglio.
• Ripetere, ma ora fare la ricerca di flusso su un grafico senza bordo selezionato (s) fino a quando il flusso è 0

Alla fine, si ha il taglio minimo, dimensione della portata massima.

Se si vuole davvero premere sulla performance, si potrebbe voler dare un'occhiata a questo documento: Flows in Undirected Unit Capacity Networks (1997) di Andrew V. Goldberg, Satish Rao, ma probabilmente sarei con quelli più semplici.