En teoría de grafos , un conjunto independiente , conjunto estable , coclique o anticlique es un conjunto de vértices en un grafo , de los cuales ninguno es adyacente. Es decir, es un conjunto de vértices tal que por cada dos vértices en , no hay ninguna arista que conecte los dos. Equivalentemente, cada arista en el grafo tiene como máximo un punto final en . Un conjunto es independiente si y solo si es una clique en el complemento del grafo . El tamaño de un conjunto independiente es el número de vértices que contiene. Los conjuntos independientes también se han llamado "conjuntos internamente estables", de los cuales "conjunto estable" es una abreviatura. [1]
Un conjunto independiente máximo es un conjunto independiente del mayor tamaño posible para un gráfico dado . Este tamaño se denomina número de independencia de y generalmente se denota por . [2] El problema de optimización para encontrar dicho conjunto se denomina problema del conjunto independiente máximo. Es un problema fuertemente NP-hard . [3] Como tal, es poco probable que exista un algoritmo eficiente para encontrar un conjunto independiente máximo de un gráfico.
Todo conjunto independiente máximo también es máximo, pero la implicación inversa no se cumple necesariamente.
Propiedades
Relación con otros parámetros del gráfico
Un conjunto es independiente si y solo si es un clique en el complemento del grafo , por lo que los dos conceptos son complementarios. De hecho, los grafos suficientemente grandes sin cliques grandes tienen conjuntos independientes grandes, un tema que se explora en la teoría de Ramsey .
Un conjunto es independiente si y sólo si su complemento es una cubierta de vértices . [4] Por lo tanto, la suma del tamaño del conjunto independiente más grande y el tamaño de una cubierta de vértices mínima es igual al número de vértices en el gráfico.
La coloración de los vértices de un grafo corresponde a una partición de su conjunto de vértices en subconjuntos independientes. Por lo tanto, el número mínimo de colores necesarios en una coloración de vértices, el número cromático , es al menos el cociente del número de vértices en y el número independiente .
Un conjunto independiente que no es un subconjunto propio de otro conjunto independiente se denomina maximal . Tales conjuntos son conjuntos dominantes . Cada grafo contiene como máximo 3 n /3 conjuntos independientes maximales, [5] pero muchos grafos tienen muchos menos. El número de conjuntos independientes maximales en grafos de ciclo de n -vértices viene dado por los números de Perrin , y el número de conjuntos independientes maximales en grafos de camino de n -vértices viene dado por la sucesión de Padovan . [6] Por lo tanto, ambos números son proporcionales a potencias de 1.324718..., la razón plástica .
En el problema del conjunto máximo independiente , la entrada es un grafo no dirigido y la salida es un conjunto máximo independiente en el grafo. Si hay varios conjuntos máximos independientes, solo es necesario que uno sea la salida. Este problema a veces se denomina " empaquetamiento de vértices ".
En el problema de conjuntos independientes de peso máximo , la entrada es un grafo no dirigido con pesos en sus vértices y la salida es un conjunto independiente con el máximo peso total. El problema de conjuntos independientes de peso máximo es el caso especial en el que todos los pesos son uno.
En el problema de listado de conjuntos independientes máximos , la entrada es un grafo no dirigido y la salida es una lista de todos sus conjuntos independientes máximos. El problema de conjuntos independientes máximos se puede resolver utilizando como subrutina un algoritmo para el problema de listado de conjuntos independientes máximos, porque el conjunto independiente máximo debe estar incluido entre todos los conjuntos independientes máximos.
En el problema de decisión de conjunto independiente , la entrada es un gráfico no dirigido y un número k , y la salida es un valor booleano : verdadero si el gráfico contiene un conjunto independiente de tamaño k , y falso en caso contrario.
Los primeros tres de estos problemas son importantes en aplicaciones prácticas; el problema de decisión del conjunto independiente no lo es, pero es necesario para aplicar la teoría de NP-completitud a problemas relacionados con conjuntos independientes.
Máximo de conjuntos independientes y máximo de camarillas
El problema de los conjuntos independientes y el problema de la camarilla son complementarios: una camarilla en G es un conjunto independiente en el grafo complementario de G y viceversa. Por lo tanto, muchos resultados computacionales pueden aplicarse igualmente bien a cualquiera de los dos problemas. Por ejemplo, los resultados relacionados con el problema de la camarilla tienen los siguientes corolarios:
El problema de decisión de conjuntos independientes es NP-completo y, por lo tanto, no se cree que exista un algoritmo eficiente para resolverlo.
El problema del conjunto máximo independiente es NP-difícil y también es difícil de aproximar .
A pesar de la estrecha relación entre los grupos máximos y los conjuntos independientes máximos en grafos arbitrarios, los problemas de grupos independientes y grupos pueden ser muy diferentes cuando se limitan a clases especiales de grafos. Por ejemplo, para grafos dispersos (grafos en los que el número de aristas es como máximo una constante multiplicada por el número de vértices en cualquier subgrafo), el grupo máximo tiene un tamaño acotado y se puede encontrar exactamente en tiempo lineal; [7] sin embargo, para las mismas clases de grafos, o incluso para la clase más restringida de grafos de grado acotado, encontrar el conjunto independiente máximo es MAXSNP-completo , lo que implica que, para alguna constante c (dependiendo del grado), es NP-difícil encontrar una solución aproximada que se encuentre dentro de un factor de c del óptimo. [8]
Algoritmos exactos
El problema del conjunto independiente máximo es NP-hard. Sin embargo, se puede resolver de manera más eficiente que el tiempo O( n 2 2 n ) que se obtendría con un algoritmo de fuerza bruta ingenuo que examina cada subconjunto de vértices y verifica si es un conjunto independiente.
A partir de 2017 se puede resolver en tiempo O(1,1996 n ) utilizando el espacio polinomial. [9] Cuando se restringe a gráficos con grado máximo 3, se puede resolver en tiempo O(1,0836 n ). [10]
Para muchas clases de grafos, se puede encontrar un conjunto independiente de peso máximo en tiempo polinomial. Ejemplos famosos son los grafos sin garras , [11] los grafos sin P 5 [12] y los grafos perfectos . [13] Para los grafos cordales , se puede encontrar un conjunto independiente de peso máximo en tiempo lineal. [14]
La descomposición modular es una buena herramienta para resolver el problema de los conjuntos independientes de peso máximo; el algoritmo de tiempo lineal en cografos es el ejemplo básico de ello. Otra herramienta importante son los separadores de camarillas, como los describe Tarjan. [15]
El teorema de König implica que en un gráfico bipartito el conjunto independiente máximo se puede encontrar en tiempo polinomial utilizando un algoritmo de coincidencia bipartita.
Algoritmos de aproximación
En general, el problema del conjunto independiente máximo no se puede aproximar a un factor constante en tiempo polinomial (a menos que P = NP). De hecho, el conjunto independiente máximo en general es poli-APX-completo , lo que significa que es tan difícil como cualquier problema que se pueda aproximar a un factor polinomial. [16] Sin embargo, existen algoritmos de aproximación eficientes para clases restringidas de grafos.
En los grafos de grado acotado, se conocen algoritmos de aproximación eficaces con razones de aproximación que son constantes para un valor fijo del grado máximo; por ejemplo, un algoritmo voraz que forma un conjunto independiente máximo eligiendo, en cada paso, el vértice de grado mínimo en el grafo y eliminando sus vecinos, logra una razón de aproximación de (Δ+2)/3 en grafos con grado máximo Δ. [18] Los límites de dureza de aproximación para tales casos fueron probados en Berman & Karpinski (1999). De hecho, incluso el conjunto independiente máximo en grafos 3-regulares de 3 aristas coloreables es APX-completo . [19]
En gráficos de intersección de intervalos
Un gráfico de intervalos es un gráfico en el que los nodos son intervalos unidimensionales (por ejemplo, intervalos de tiempo) y hay una arista entre dos intervalos si y solo si se intersecan. Un conjunto independiente en un gráfico de intervalos es simplemente un conjunto de intervalos que no se superponen. El problema de encontrar conjuntos independientes máximos en gráficos de intervalos se ha estudiado, por ejemplo, en el contexto de la programación de trabajos : dado un conjunto de trabajos que se deben ejecutar en una computadora, encuentre un conjunto máximo de trabajos que se puedan ejecutar sin interferir entre sí. Este problema se puede resolver exactamente en tiempo polinomial utilizando la programación de fecha límite más temprana .
En gráficos de intersección geométrica
Un gráfico de intersección geométrica es un gráfico en el que los nodos son formas geométricas y hay una arista entre dos formas si y solo si se intersecan. Un conjunto independiente en un gráfico de intersección geométrica es simplemente un conjunto de formas disjuntas (no superpuestas). El problema de encontrar el máximo de conjuntos independientes en gráficos de intersección geométrica se ha estudiado, por ejemplo, en el contexto de la colocación automática de etiquetas : dado un conjunto de ubicaciones en un mapa, encuentre un conjunto máximo de etiquetas rectangulares disjuntas cerca de estas ubicaciones.
Encontrar un conjunto independiente máximo en grafos de intersección sigue siendo un problema NP-completo, pero es más fácil de aproximar que el problema general del conjunto independiente máximo. Se puede encontrar un estudio reciente en la introducción de Chan y Har-Peled (2012).
En gráficos sin garra D
Una d-garra en un grafo es un conjunto de d +1 vértices, uno de los cuales (el "centro") está conectado a los otros d vértices, pero los otros d vértices no están conectados entre sí. Un grafo sin d - garra es un grafo que no tiene un subgrafo con d -garra. Considere el algoritmo que comienza con un conjunto vacío y le agrega de manera incremental un vértice arbitrario siempre que no sea adyacente a ningún vértice existente. En los grafos sin d-garra, cada vértice agregado invalida como máximo d -1 vértices del conjunto independiente máximo; por lo tanto, este algoritmo trivial obtiene un algoritmo de aproximación ( d -1) para el conjunto independiente máximo. De hecho, es posible obtener proporciones de aproximación mucho mejores:
Neuwohner [20] presentó un algoritmo de tiempo polinomial que, para cualquier constante ε>0, encuentra una aproximación ( d /2-1/63,700,992+ε) para el conjunto independiente del peso máximo en un grafo libre de d -claw.
Cygan [21] presentó un algoritmo de tiempo cuasi-polinomial que, para cualquier ε>0, alcanza una aproximación (d+ε)/3.
Encontrar conjuntos independientes máximos
El problema de encontrar un conjunto independiente máximo se puede resolver en tiempo polinomial mediante un algoritmo trivial paralelo voraz . [22] Todos los conjuntos independientes máximos se pueden encontrar en el tiempo O(3 n /3 ) = O(1.4423 n ).
Contando conjuntos independientes
Problema sin resolver en informática :
¿Existe un algoritmo de aproximación en tiempo completamente polinomial para el número de conjuntos independientes en gráficos bipartitos?
El problema de conteo #IS pregunta, dado un grafo no dirigido, cuántos conjuntos independientes contiene. Este problema es intratable, es decir, es ♯P -completo, ya en grafos con grado máximo tres. [23] Se sabe además que, suponiendo que NP es diferente de RP , el problema no se puede aproximar de manera tratable en el sentido de que no tiene un esquema de aproximación de tiempo polinomial completo con aleatorización (FPRAS), incluso en grafos con grado máximo seis; [24] sin embargo, tiene un esquema de aproximación de tiempo polinomial completo (FPTAS) en el caso en que el grado máximo sea cinco. [25] El problema #BIS, de contar conjuntos independientes en grafos bipartitos , también es ♯P -completo, ya en grafos con grado máximo tres. [26]
No se sabe si #BIS admite un FPRAS. [27]
El conjunto independiente máximo y su complemento, el problema de cobertura mínima de vértices , intervienen en la demostración de la complejidad computacional de muchos problemas teóricos. [28] También sirven como modelos útiles para problemas de optimización del mundo real, por ejemplo, el conjunto independiente máximo es un modelo útil para descubrir componentes genéticos estables para diseñar sistemas genéticos diseñados . [29]
Véase también
Un conjunto de aristas independientes es un conjunto de aristas en el que no hay dos que tengan un vértice en común. Se suele llamar conjunto coincidente .
Una coloración de vértices es una partición del conjunto de vértices en conjuntos independientes.
Notas
^ Korshunov (1974)
^ Godsil y Royle (2001), pág. 3.
^ Garey, MR; Johnson, DS (1 de julio de 1978). "Resultados de NP-Completitud "fuertes": motivación, ejemplos e implicaciones". Revista de la ACM . 25 (3): 499–508. doi : 10.1145/322077.322090 . ISSN 0004-5411. S2CID 18371269.
^ Demostración: Un conjunto V de vértices es un conjunto independiente. si y solo si cada arista del grafo es adyacente a como máximo un miembro de V, si y solo si cada arista del grafo es adyacente a al menos un miembro que no está en V, si y solo si el complemento de V es una cubierta de vértices.
^ Luna y Moser (1965).
^ Füredi (1987).
^ Chiba y Nishizeki (1985).
^ Berman y Fujito (1995).
^ Xiao y Nagamochi (2017)
^ Xiao y Nagamochi (2013)
^ Minty (1980),Sbihi (1980),Nakamura y Tamura (2001),Faenza, Oriolo y Stauffer (2014),Nobili y Sassano (2015)
^ Bazgan, Cristina ; Escoffier, Bruno; Paschos, Vangelis Th. (2005). "Completitud en clases de aproximación estándar y diferencial: Completitud poli-(D)APX- y (D)PTAS". Ciencias Informáticas Teóricas . 339 (2–3): 272–292. doi : 10.1016/j.tcs.2005.03.007 . S2CID 1418848.
^ Banco de Inglaterra (1994);
^ Halldórsson y Radhakrishnan (1997).
^ Chlebík, Miroslav; Chlebíková, Janka (2003). "Dureza de aproximación para instancias de ocurrencia pequeñas de problemas NP-difíciles". Actas de la 5.ª Conferencia internacional sobre algoritmos y complejidad . Apuntes de clase en informática. Vol. 2653. págs. 152–164. doi :10.1007/3-540-44849-7_21. ISBN.978-3-540-40176-6.
^ Neuwohner, Meike (7 de junio de 2021), Un algoritmo de aproximación mejorado para el problema de conjunto independiente de peso máximo en gráficos libres d-Claw , arXiv : 2106.03545
^ Cygan, Marek (octubre de 2013). "Aproximación mejorada para la correspondencia tridimensional mediante búsqueda local de ancho de ruta limitado". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science . págs. 509–518. arXiv : 1304.1424 . doi :10.1109/FOCS.2013.61. ISBN978-0-7695-5135-7.S2CID14160646 .
^ Luby (1986).
^ Dyer, Martin; Greenhill, Catherine (1 de abril de 2000). "Sobre cadenas de Markov para conjuntos independientes". Revista de algoritmos . 35 (1): 17–49. doi :10.1006/jagm.1999.1071. ISSN 0196-6774.
^ Sly, Allan (2010). "Transición computacional en el umbral de unicidad". 2010 IEEE 51st Annual Symposium on Foundations of Computer Science . págs. 287–296. doi :10.1109/FOCS.2010.34. ISBN978-1-4244-8525-3.S2CID 901126 .
^ Bezáková, Ivona; Galanis, Andreas; Goldberg, Leslie Ann; Guo, Heng; Štefankovič, Daniel (2019). "Aproximación a través de la desintegración de la correlación cuando falla la mezcla espacial fuerte". Revista SIAM de Computación . 48 (2): 279–349. arXiv : 1510.09193 . doi :10.1137/16M1083906. ISSN 0097-5397. S2CID 131975798.
^ Xia, Mingji; Zhang, Peng; Zhao, Wenbo (24 de septiembre de 2007). "Complejidad computacional de problemas de conteo en grafos planos 3-regulares". Ciencias de la Computación Teórica . Teoría y Aplicaciones de Modelos de Computación. 384 (1): 111–125. doi :10.1016/j.tcs.2007.05.023. ISSN 0304-3975., citado en Curticapean, Radu; Dell, Holger; Fomin, Fedor; Goldberg, Leslie Ann; Lapinskas, John (1 de octubre de 2019). "Una perspectiva de parámetros fijos sobre #BIS". Algorithmica . 81 (10): 3844–3864. doi : 10.1007/s00453-019-00606-4 . hdl : 1983/ecb5c34c-d6be-44ec-97ea-080f57c5e6af . ISSN 1432-0541. S2CID 3626662.
^ Cannon, Sarah; Perkins, Will (2020). Chawla, Shuchi (ed.). Actas del decimocuarto simposio anual ACM-SIAM sobre algoritmos discretos. Filadelfia, PA: Sociedad de Matemáticas Industriales y Aplicadas. arXiv : 1906.01666 . doi :10.1137/1.9781611975994.88. ISBN.978-1-61197-599-4.S2CID174799567 .
^ Skiena, Steven S. (2012). Manual de diseño de algoritmos . Springer. ISBN978-1-84800-069-8.OCLC 820425142 .
^ Hossain, Ayaan; Lopez, Eriberto; Halper, Sean M.; Cetnar, Daniel P.; Reis, Alexander C.; Strickland, Devin; Klavins, Eric; Salis, Howard M. (13 de julio de 2020). "Diseño automatizado de miles de partes no repetitivas para la ingeniería de sistemas genéticos estables". Nature Biotechnology . 38 (12): 1466–1475. doi :10.1038/s41587-020-0584-2. ISSN 1546-1696. PMID 32661437. S2CID 220506228.
Referencias
Baker, Brenda S. (1994), "Algoritmos de aproximación para problemas NP-completos en grafos planares", Journal of the ACM , 41 (1): 153–180, doi : 10.1145/174644.174650 , S2CID 9706753.
Berman, Piotr; Fujito, Toshihiro (1995), "Sobre las propiedades de aproximación del problema de conjuntos independientes para grafos de grado 3", Algorithms and Data Structures , Lecture Notes in Computer Science, vol. 955, Springer-Verlag , págs. 449–460, doi :10.1007/3-540-60220-8_84, ISBN 978-3-540-60220-0.
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis Th.; van Rooij, Johan MM (2010), "Un método de abajo hacia arriba y algoritmos rápidos para MAX INDEPENDENT SET", Algorithm Theory - SWAT 2010 , Lecture Notes in Computer Science, vol. 6139, Berlín: Springer, págs. 62–73, Bibcode :2010LNCS.6139...62B, doi :10.1007/978-3-642-13731-0_7, ISBN 978-3-642-13730-3, Sr. 2678485.
Chan, TM (2003), "Esquemas de aproximación en tiempo polinomial para empacar y perforar objetos gordos", Journal of Algorithms , 46 (2): 178–189, CiteSeerX 10.1.1.21.5344 , doi :10.1016/s0196-6774(02)00294-8.
Erlebach, T.; Jansen, K.; Seidel, E. (2005), "Esquemas de aproximación en tiempo polinomial para gráficos de intersección geométrica", SIAM Journal on Computing , 34 (6): 1302, doi :10.1137/s0097539702402676.
Faenza, Yuri; Oriolo, Gianpaolo; Stauffer, Gautier (2014), "Resolución del problema del conjunto estable ponderado en grafos sin garras", Journal of the ACM , 61 (4): 1–41, doi :10.1145/2629600, S2CID 1995056.
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter (2009), "Un enfoque de medida y conquista para el análisis de algoritmos exactos", Journal of the ACM , 56 (5): 1–32, doi :10.1145/1552285.1552286, S2CID 1186651, artículo n.º 25,.
Frank, András (1976), "Algunos algoritmos polinomiales para ciertos grafos e hipergrafos", Congressus Numerantium , XV : 211–226.
Füredi, Zoltán (1987), "El número de conjuntos independientes máximos en grafos conexos", Journal of Graph Theory , 11 (4): 463–470, doi :10.1002/jgt.3190110403.
Halldórsson, MM; Radhakrishnan, J. (1997), "La codicia es buena: aproximación de conjuntos independientes en grafos dispersos y de grado acotado", Algorithmica , 18 (1): 145–163, CiteSeerX 10.1.1.145.4523 , doi : 10.1007/BF02523693 , S2CID 4661668.
Korshunov, AD (1974), "Coeficiente de estabilidad interna", Kibernetika (en ucraniano), 10 (1): 17–28, doi :10.1007/BF01069014, S2CID 120343511.
Lokshtanov, D.; Vatshelle, M.; Villanger, Y. (2014), "Conjuntos independientes en grafos libres de P 5 en tiempo polinomial", SODA (Simposio sobre algoritmos discretos) : 570–581.
Luby, Michael (1986), "Un algoritmo paralelo simple para el problema del conjunto independiente máximo", SIAM Journal on Computing , 15 (4): 1036–1053, CiteSeerX 10.1.1.225.5475 , doi :10.1137/0215074, MR 0861369.
Minty, GJ (1980), "Sobre conjuntos independientes máximos de vértices en grafos sin garras", Journal of Combinatorial Theory, Serie B , 28 (3): 284–304, doi : 10.1016/0095-8956(80)90074-x.
Nakamura, D.; Tamura, A. (2001), "Una revisión del algoritmo de Minty para encontrar un conjunto estable de peso máximo en un gráfico sin garras", Journal of Operations Research Society Japan , 44 (2): 194–204, doi : 10.15807/jorsj.44.194.
Nobili, P.; Sassano, A. (2015), Un algoritmo O(n^2 log n) para el problema de conjunto estable ponderado en grafos sin garras , arXiv : 1501.05775 , Bibcode :2015arXiv150105775N
Robson, JM (1986), "Algoritmos para conjuntos independientes máximos", Journal of Algorithms , 7 (3): 425–440, doi :10.1016/0196-6774(86)90032-5.
Sbihi, Najiba (1980), "Algorithme de recherche d'un stable de cardinalité Maximum dans un graphe sans étoile", Matemáticas discretas (en francés), 29 (1): 53–76, doi : 10.1016/0012-365X(90 )90287-R , SEÑOR 0553650.
Xiao, Mingyu; Nagamochi, Hiroshi (2017), "Algoritmos exactos para el conjunto máximo independiente", Información y computación , 255 : 126–146, arXiv : 1312.6260 , doi : 10.1016/j.ic.2017.06.001, S2CID 1714739.
Xiao, Mingyu; Nagamochi, Hiroshi (2013), "Confinar conjuntos y evitar casos de cuello de botella: un algoritmo simple de conjunto independiente máximo en grafos de grado 3", Theoretical Computer Science , 469 : 92–104, doi : 10.1016/j.tcs.2012.09.022.
Tarjan, RE (1985), "Descomposición por separadores de camarillas", Discrete Mathematics , 55 (2): 221–232, doi : 10.1016/0012-365x(85)90051-2.
