En matemáticas, el corte k mínimo es un problema de optimización combinatoria que requiere encontrar un conjunto de aristas cuya eliminación dividiría el gráfico en al menos k componentes conectados. Estos bordes se conocen como k- cut . El objetivo es encontrar el corte k de peso mínimo . Esta partición puede tener aplicaciones en diseño VLSI , minería de datos , elementos finitos y comunicación en computación paralela .
Definicion formal
Dado un gráfico no dirigido G = ( V , E ) con una asignación de pesos a los bordes w : E → N y un número entero k ∈ {2, 3,…, | V |}, divide V en k conjuntos disjuntos F = { C 1 , C 2 ,…, C k } mientras se minimiza
Para un k fijo , el problema es un polinomio resoluble en el tiempo en O (| V | k 2 ). [1] Sin embargo, el problema es NP-completo si k es parte de la entrada. [2] También es NP-completo si especificamos vértices y pide el mínimo -corte que separa estos vértices entre cada uno de los conjuntos. [3]
Aproximaciones
Existen varios algoritmos de aproximación con una aproximación de 2 - 2 / k . Un algoritmo codicioso simple que logra este factor de aproximación calcula un corte mínimo en cada uno de los componentes conectados y elimina el más pesado. Este algoritmo requiere un total de n - 1 cálculos de flujo máximo . Otro algoritmo que logra la misma garantía utiliza la representación de árboles de Gomory-Hu de cortes mínimos. La construcción del árbol de Gomory-Hu requiere n - 1 cálculos de flujo máximo, pero el algoritmo requiere cálculos de flujo máximo de O ( kn ) totales . Sin embargo, es más fácil analizar el factor de aproximación del segundo algoritmo. [4] [5] Además, bajo la Hipótesis de expansión de conjuntos pequeños (una conjetura estrechamente relacionada con la Conjetura de juegos únicos ), el problema es NP-difícil de aproximar dentro de factor para cada constante , [6] lo que significa que los algoritmos de aproximación antes mencionados son esencialmente ajustados para grandes.
Una variante del problema solicita un corte k de peso mínimo donde las particiones de salida tienen tamaños preestablecidos. Esta variante del problema es aproximada dentro de un factor de 3 para cualquier k fijo si se restringe la gráfica a un espacio métrico, es decir, una gráfica completa que satisface la desigualdad del triángulo . [7] Más recientemente, se descubrieron esquemas de aproximación de tiempo polinómico (PTAS) para esos problemas. [8]
Ver también
Notas
- ^ Goldschmidt y Hochbaum 1988 .
- ^ Garey y Johnson, 1979
- ^ [1] , que cita [2]
- ^ Saran y Vazirani 1991 .
- ^ Vazirani 2003 , págs. 40–44.
- ^ Manurangsi 2017
- ^ Guttmann-Beck y Hassin 1999 , págs. 198-207.
- ^ Fernández de la Vega, Karpinski y Kenyon 2004
Referencias
- Goldschmidt, O .; Hochbaum, DS (1988), Proc. 29th Ann. IEEE Symp. sobre Fundamentos de la Computación. Sci. , IEEE Computer Society, págs. 444–451
- Garey, MR; Johnson, DS (1979), Computadoras e intratabilidad: una guía para la teoría de NP-Completeness , WH Freeman, ISBN 978-0-7167-1044-8
- Saran, H .; Vazirani, V. (1991), "Encontrar k cortes dentro del doble del óptimo" , Proc. 32nd Ann. IEEE Symp. sobre Fundamentos de la Computación. Sci , IEEE Computer Society, págs. 743–751
- Vazirani, Vijay V. (2003), Algoritmos de aproximación , Berlín: Springer, ISBN 978-3-540-65367-7
- Guttmann-Beck, N .; Hassin, R. (1999), "Algoritmos de aproximación para corte k mínimo " (PDF) , Algorithmica , págs. 198-207
- Comellas, Francesc; Sapena, Emili (2006), "Un algoritmo multiagente para la partición de grafos. Lecture Notes in Comput. Sci." , Algorithmica , 3907 (2): 279–285, CiteSeerX 10.1.1.55.5697 , doi : 10.1007 / s004530010013 , ISSN 0302-9743 , archivado desde el original el 12 de diciembre de 2009
- Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek ; Woeginger, Gerhard (2000), "Corte k mínimo", Compendio de problemas de optimización de NP
- Fernández de la Vega, W .; Karpinski, M .; Kenyon, C. (2004). "Esquemas de aproximación para bisección métrica y particionamiento" . Actas del decimoquinto simposio anual ACM-SIAM sobre algoritmos discretos . págs. 506–515.
- Manurangsi, P. (2017). "Inaproximación de Biclique de borde máximo, Biclique equilibrado máximo y K-Cut mínimo de la hipótesis de expansión de conjunto pequeño". 44 ° Coloquio Internacional sobre Autómatas, Idiomas y Programación, ICALP 2017 . págs. 79: 1–79: 14. doi : 10.4230 / LIPIcs.ICALP.2017.79 .