Algoritmo efficiente per minuto minuto con numero specificato di vertici

Question

Considera un grafico con i vertici $ V $ e bordi $ e $ . La versione standard del problema minimo minimo è trovare la partizione di $ V $ in un sottoinsieme (non vuoto) $ C $ e il suo complemento $ \ bar {c} $ in modo da minimizzare il numero di bordi che vanno tra $ C $ e $ \ bar {c} $ . Gli algoritmi sono noti per questo problema che lo risolve in tempo polinomiale. La mia domanda è, cosa succede se si specifica anche il vincolo che $ | c |= n $ per alcuni $ n <| v | $ ? Cioè, desideriamo trovare il set di $ N $ vertici con il numero minimo di bordi che lo collegano al resto dei vertici. Ci sono anche algoritmi efficienti per questo caso? Sono interessato a entrambi in questione se questo problema è formalmente risolvibile in tempo polinomiale (che immagino che sia) e anche in quali algoritmi sono meglio nella pratica.

Answer 1

per $ n=frac {| v |} 2 $ , si chiama bisection minimo, ed è difficile da NP. Esiste una $ o (\ log ^ {3/2} n) $ -approssimazione: " Un'approssimazione polylogaritmica della bisezione minima ".

Se sei interessato, il problema più generale si sta dividendo in più componenti della stessa dimensione, ed è chiamato il partizionamento del grafico equilibrato. Per più di 2 parti non esiste un'approssimazione finita a meno che P= NP: "Bilanciato grafico partitioning" (Andreev, Rakke) , poiché non è possibile controllare in modo efficiente se la risposta è 0.

Se le parti non sono necessariamente equilibrate esattamente (è consentito un piccolo squilibrio), una classe $ o (\ log n) $ esistono algoritmo -approssimazione: "Divisori equilibrati di alberi e applicazioni" .

---

.

alcuni algoritmi (assegni anche https://en.wikipedia.org/wiki/graph_partition e "Riferimenti" Sezioni dei seguenti documenti):

.

• Ricerca locale con vari sapori: Iniziamo con un po 'di partizionamento e quindi proviamo a scambiare i vertici tra le parti per ridurre al minimo il taglio. Per esempio. Compute "guadagno" per ogni vertice (miglioramento se lo spostassi in un'altra parte) e scambiamo i vertici con il massimo guadagno. Il suo vantaggio è che puoi applicarlo dopo qualsiasi altro algoritmo.

• partizionamento spettrale (vedi ad esempio teoria e grafico grafico spettrale Dividendo ): utilizza il secondo eigenvettore di una matrice laplaciana per approssimare il partizionamento (ad esempio spostando la più piccola $ | V | / 2 $ coordinate al primo parte). Funziona sorprendentemente bene. Tuttavia, non sono sicuro che possa essere adattato al caso quando si desidera una bisezione sbilanciata (ad es. $ 1: 2 $ invece di $ 1: 1 $ ).

• Incorporamento lineare: "Distributed bilanciato partitioning tramite embedding lineare" . Incorporiamo i vertici in una matrice unidimensionale riducendo al minimo la somma su tutte le coppie di vertici: la distanza tra loro moltiplicata per il peso del loro bordo. Poi abbiamo appena diviso questa matrice in blocchi consecutivi di dimensioni richieste. Non ha funzionato bene nella mia esperienza.

• (annunci) Il nostro documento: grafico bilanciato multi-dimensionale Partizionamento da Via. Discesa sfumata prevista ", dove abbiamo usato la discesa gradiente per trovare la bisezione minima: per ogni vertice introduciamo una variabile che rappresenta all'incirca una probabilità che il vertice appartenga alla prima parte e riducendo al minimo il taglio riduce all'ottimizzazione vincolata di A funzione quadratica. È un po 'sovraperformato in pratica da una ricerca locale sintonizzata, ma funziona davvero bene quando hai più vincoli di bilanciamento.

A parte il metodo spettrale, tutti possono essere adattati in modo vincente per suddividere il grafico in proporzioni arbitrarie.

Ci sono anche solver standard: kahip , metis . Nella mia esperienza, Kahip era abbastanza buono. Non sono sicuro che supportano la divisione in parti di dimensioni arbitrarie però.