algoritmo eficiente para corte mínimo con un número específico de vértices

Question

Considere un gráfico con vértices $v$ y bordes $E$.La versión estándar del problema de corte mínimo es encontrar la partición de $v$ en un subconjunto (no vacío) $C$ y su complemento $\bar{C}$ para minimizar el número de bordes que van entre $C$ y $\bar{C}$.Para este problema se conocen algoritmos que lo resuelven en tiempo polinomial.Mi pregunta es, ¿qué pasa si además se especifica la restricción que $ | C | = n $ para algunos $n < |V|$?Es decir, deseamos encontrar el conjunto de $n$ vértices con el mínimo número de aristas que lo conecten con el resto de los vértices.¿Existen también algoritmos eficientes para este caso?Estoy interesado tanto en la cuestión de si este problema se puede resolver formalmente en tiempo polinomial (que supongo que lo es) como en qué algoritmos son mejores en la práctica.

Answer 1

Para $n= \frac {|V|} 2$, se llama Bisección Mínima y es NP-duro.existe un $O(\log^{3/2} n)$-aproximación: "Una aproximación polilogarítmica de la bisección mínima".

Si está interesado, el problema más general es dividir en varios componentes del mismo tamaño y se llama partición de gráficos equilibrados.Para más de 2 partes no existe una aproximación finita a menos que P=NP: "Partición de gráficos equilibrada" (Andreev, Rakke), ya que no se puede comprobar de manera eficiente si la respuesta es 0.

Si las piezas no están necesariamente exactamente equilibradas (se permite un pequeño desequilibrio), se $O(\logn)$-Existe un algoritmo de aproximación: "Particiones equilibradas de árboles y aplicaciones".

---

Algunos algoritmos (ver también https://en.wikipedia.org/wiki/Graph_partition y secciones de "referencias" de los siguientes artículos):

• Búsqueda local con varios sabores:Comenzamos con algunas particiones y luego intentamos intercambiar vértices entre partes para minimizar el corte.P.ej.Calculamos la "ganancia" para cada vértice (mejora si lo movemos a otra parte) e intercambiamos los vértices con la ganancia máxima.Su ventaja es que puedes aplicarlo después de cualquier otro algoritmo.

• Partición espectral (ver p.ej. Teoría de grafos espectrales y partición de grafos):utiliza el segundo vector propio de una matriz laplaciana para aproximar la partición (p. ej.moviendo el más pequeño $|V|/2$ coordenadas a la primera parte).Funciona sorprendentemente bien.Sin embargo, no estoy seguro de que pueda adaptarse al caso en el que desee una bisección desequilibrada (p. ej. $1:2$ en lugar de $1:1$).

• Incrustación lineal: "Partición equilibrada distribuida mediante incrustación lineal".Incrustamos vértices en una matriz unidimensional mientras minimizamos la suma de todos los pares de vértices:la distancia entre ellos multiplicada por el peso de su borde.Luego simplemente dividimos esta matriz en fragmentos consecutivos de los tamaños requeridos.No funcionó tan bien en mi experiencia.

• (Anuncios) Nuestro periódico: "Partición gráfica equilibrada multidimensional a través de un descenso de gradiente proyectado", donde utilizamos el descenso de gradiente para encontrar la bisección mínima:para cada vértice introducimos una variable que representa aproximadamente una probabilidad de que el vértice pertenezca a la primera parte, y minimizar el corte se reduce a la optimización restringida de una función cuadrática.En la práctica, su rendimiento es un poco superado por una búsqueda local ajustada, pero funciona muy bien cuando tienes múltiples restricciones de equilibrio.

Aparte del método espectral, todos ellos pueden adaptarse trivialmente para dividir el gráfico en proporciones arbitrarias.

También hay solucionadores estándar: KaHIP, MÉTIS.En mi experiencia, KaHIP fue bastante bueno.Sin embargo, no estoy seguro de que admitan la división en partes de tamaños arbitrarios.