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 no hay dos adyacentes. Es decir, es un conjunto de vértices tal que por cada dos vértices en , no hay ninguna arista que los conecte. De manera equivalente, cada arista del gráfico tiene como máximo un punto final en . Un conjunto es independiente si y sólo si es una camarilla 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 denominado "conjuntos internamente estables", de los cuales "conjunto estable" es una abreviación. [1]
Un conjunto máximo independiente es un conjunto independiente del mayor tamaño posible para un gráfico determinado . Este tamaño se llama número de independencia de y generalmente se denota por . [2] El problema de optimización para encontrar dicho conjunto se denomina problema de conjunto máximo independiente. Es un problema fuertemente NP-difícil . [3] Como tal, es poco probable que exista un algoritmo eficiente para encontrar un conjunto máximo independiente de un gráfico.
Todo conjunto máximo independiente también es máximo, pero la implicación inversa no necesariamente se cumple.
Propiedades
Relación con otros parámetros del gráfico
Un conjunto es independiente si y sólo si es una camarilla en el complemento del grafo , por lo que los dos conceptos son complementarios. De hecho, los gráficos suficientemente grandes sin grandes camarillas tienen grandes conjuntos independientes, un tema que se explora en la teoría de Ramsey .
Un conjunto es independiente si y sólo si su complemento es una cobertura de vértices . [4] Por lo tanto, la suma del tamaño del conjunto independiente más grande y el tamaño de una cobertura mínima de vértices es igual al número de vértices en el gráfico.
La coloración de los vértices de un gráfico 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 y el número independiente .
Un conjunto independiente que no es un subconjunto propio de otro conjunto independiente se llama máximo . Estos conjuntos son conjuntos dominantes . Cada gráfico contiene como máximo 3 n /3 conjuntos independientes máximos, [5] pero muchos gráficos tienen muchos menos. El número de conjuntos independientes máximos en gráficos de ciclos de n -vértices viene dado por los números de Perrin , y el número de conjuntos independientes máximos en gráficos de trayectorias de n -vértices viene dado por la secuencia de Padovan . [6] Por lo tanto, ambos números son proporcionales a potencias de 1,324718..., la relación plástica .
En el problema del conjunto máximo independiente , la entrada es un gráfico no dirigido y la salida es un conjunto máximo independiente en el gráfico. Si hay varios conjuntos independientes máximos, solo es necesario generar uno. Este problema a veces se denomina " empaquetamiento de vértices ".
En el problema del conjunto independiente de peso máximo , la entrada es un gráfico no dirigido con pesos en sus vértices y la salida es un conjunto independiente con peso total máximo. El problema del conjunto máximo independiente 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 gráfico no dirigido y la salida es una lista de todos sus conjuntos independientes máximos. El problema de conjuntos máximos independientes se puede resolver utilizando como subrutina un algoritmo para el problema de listado de conjuntos máximos independientes, porque el conjunto máximo independiente debe incluirse entre todos los conjuntos máximos independientes.
En el problema de decisión de conjuntos independientes , 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 de conjuntos independientes no lo es, pero es necesario para aplicar la teoría de la completitud NP a problemas relacionados con conjuntos independientes.
Conjuntos independientes máximos y camarillas máximas.
El problema de conjunto independiente y el problema de camarilla son complementarios: una camarilla en G es un conjunto independiente en el gráfico complemento de G y viceversa. Por lo tanto, muchos resultados computacionales pueden aplicarse igualmente bien a cualquiera de los 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 independiente máximo es NP-difícil y también es difícil de aproximar .
A pesar de la estrecha relación entre camarillas máximas y conjuntos independientes máximos en gráficos arbitrarios, los problemas de conjuntos independientes y camarillas pueden ser muy diferentes cuando se restringen a clases especiales de gráficos. Por ejemplo, para gráficos dispersos (gráficos en los que el número de aristas es como máximo una constante multiplicado por el número de vértices en cualquier subgrafo), la camarilla máxima tiene un tamaño acotado y se puede encontrar exactamente en tiempo lineal; [7] sin embargo, para las mismas clases de gráficos, o incluso para la clase más restringida de gráficos de grados acotados, encontrar el conjunto independiente máximo es MAXSNP-completo , lo que implica que, para alguna constante c (dependiendo del grado) es NP -Es difícil encontrar una solución aproximada que esté dentro de un factor de c del óptimo. [8]
Algoritmos exactos
El problema de conjunto máximo independiente es NP-difícil. Sin embargo, se puede resolver de manera más eficiente que el tiempo O( n 2 2 n ) que daría un ingenuo algoritmo de fuerza bruta que examina cada subconjunto de vértices y verifica si es un conjunto independiente.
A partir de 2017, se puede resolver en el 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 el tiempo O (1,0836 n ). [10]
Para muchas clases de gráficos, se puede encontrar un conjunto independiente de peso máximo en tiempo polinómico. Ejemplos famosos son los gráficos sin garras , [11] los gráficos sin P 5 [12] y los gráficos perfectos . [13] Para gráficos 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 del conjunto independiente del peso máximo; el algoritmo de tiempo lineal en cografos es el ejemplo básico para ello. Otra herramienta importante son los separadores de camarillas descritos por Tarjan. [15]
El teorema de Kőnig implica que en un gráfico bipartito el conjunto independiente máximo se puede encontrar en tiempo polinómico utilizando un algoritmo de coincidencia bipartito.
Algoritmos de aproximación
En general, el problema del conjunto máximo independiente no puede aproximarse a un factor constante en tiempo polinómico (a menos que P = NP). De hecho, el conjunto independiente máximo en general es Poly-APX-completo , lo que significa que es tan difícil como cualquier problema que pueda aproximarse a un factor polinómico. [16] Sin embargo, existen algoritmos de aproximación eficientes para clases restringidas de gráficos.
En gráficos planos
En gráficos planos , el conjunto independiente máximo se puede aproximar dentro de cualquier relación de aproximación c <1 en tiempo polinómico; Existen esquemas similares de aproximación en tiempo polinomial en cualquier familia de gráficos cerrados con menores . [17]
En gráficos de grados acotados
En gráficos de grados acotados, se conocen algoritmos de aproximación efectivos con relaciones de aproximación que son constantes para un valor fijo del grado máximo; por ejemplo, un algoritmo codicioso que forma un conjunto máximo independiente eligiendo, en cada paso, el vértice de grado mínimo en el gráfico y eliminando sus vecinos, logra una relación de aproximación de (Δ+2)/3 en gráficos con grado máximo Δ. [18] Los límites de dureza de aproximación para tales casos fueron probados en Berman y Karpinski (1999). De hecho, incluso el conjunto Max Independent en 3 gráficos regulares coloreables de 3 bordes 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 un borde entre dos intervalos si y sólo si se cruzan. Un conjunto independiente en un gráfico de intervalos es simplemente un conjunto de intervalos que no se superponen. El problema de encontrar conjuntos máximos independientes en gráficos de intervalo se ha estudiado, por ejemplo, en el contexto de la programación de trabajos : dado un conjunto de trabajos que deben ejecutarse en una computadora, encuentre un conjunto máximo de trabajos que se puedan ejecutar sin interferir juntos. Este problema se puede resolver exactamente en tiempo polinómico utilizando la primera programación con 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 un borde entre dos formas si y solo si se cruzan. Un conjunto independiente en un gráfico de intersección geométrica es simplemente un conjunto de formas disjuntas (que no se superponen). El problema de encontrar conjuntos máximos 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 máximo independiente en gráficos de intersección sigue siendo NP-completo, pero es más fácil de aproximar que el problema general del conjunto máximo independiente. Se puede encontrar una encuesta reciente en la introducción de Chan y Har-Peled (2012).
En gráficos sin d-claw
Una d-garra en un gráfico 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 gráfico d - sin garras es un gráfico que no tiene un subgrafo d -garra. Considere el algoritmo que comienza con un conjunto vacío y le agrega incrementalmente un vértice arbitrario siempre que no sea adyacente a ningún vértice existente. En d -gráficos sin garras, cada vértice agregado invalida como máximo d -1 vértices del conjunto máximo independiente; por lo tanto, este algoritmo trivial logra un algoritmo de aproximación ( d -1) para el conjunto independiente máximo. De hecho, es posible obtener relaciones de aproximación mucho mejores:
Neuwohner [20] presentó un algoritmo de tiempo polinómico que, para cualquier constante ε>0, encuentra una aproximación ( d /2-1/63,700,992+ε) para el conjunto independiente de peso máximo en un gráfico d -claw free.
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 codicioso paralelo trivial . [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 no resuelto en informática :
¿Existe un algoritmo de aproximación de tiempo totalmente polinomial para el número de conjuntos independientes en gráficos bipartitos?
El problema de conteo #IS pregunta, dado un gráfico no dirigido, cuántos conjuntos independientes contiene. Este problema es intratable, es decir, es ♯P -completo, ya en gráficos con grado máximo tres. [23] Se sabe además que, suponiendo que NP es diferente de RP , el problema no se puede aproximar fácilmente en el sentido de que no tiene un esquema de aproximación de tiempo totalmente polinomial con aleatorización (FPRAS), incluso en gráficos con grado máximo. seis; [24] sin embargo, tiene un esquema de aproximación de tiempo totalmente polinomial (FPTAS) en el caso en que el grado máximo sea cinco. [25] El problema #BIS, de contar conjuntos independientes en gráficos bipartitos , también es ♯P -completo, ya en gráficos con grado máximo tres. [26]
No se sabe si #BIS admite un FPRAS. [27]
El conjunto máximo independiente y su complemento, el problema de cobertura mínima de vértices , participan 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 máximo independiente es un modelo útil para descubrir componentes genéticos estables para diseñar sistemas genéticos diseñados . [29]
Ver también
Un conjunto independiente de aristas es un conjunto de aristas de las cuales no hay dos que tengan un vértice en común. Generalmente se le llama coincidencia .
Una coloración de vértice es una partición del conjunto de vértices en conjuntos independientes.
Notas
^ Korshunov (1974)
^ Godsil y Royle (2001), pág. 3.
^ Garey, señor; Johnson, DS (1 de julio de 1978). "Resultados " sólidos "de integridad de NP: motivación, ejemplos e implicaciones". Revista de la ACM . 25 (3): 499–508. doi : 10.1145/322077.322090 . ISSN 0004-5411. S2CID 18371269.
^ Prueba: un conjunto V de vértices es un conjunto independiente. si y sólo si cada arista del gráfico es adyacente a como máximo un miembro de V, si y sólo si cada arista del gráfico es adyacente a al menos un miembro que no está en V, si y sólo si el complemento de V es un vértice cubrir.
^ Luna y Moser (1965).
^ Furedi (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)
^ Bazgán, Cristina ; Escoffier, Bruno; Paschos, Vangelis Th. (2005). "Completitud en clases de aproximación estándar y diferencial: integridad poli-(D)APX y (D)PTAS". Informática Teórica . 339 (2–3): 272–292. doi : 10.1016/j.tcs.2005.03.007 . S2CID 1418848.
^ Panadero (1994); Grohe (2003).
^ Halldórsson y Radhakrishnan (1997).
^ Chlebík, Miroslav; Chlebíková, Janka (2003). "Dureza de aproximación para casos pequeños de problemas NP-difíciles". Actas de la V Conferencia Internacional sobre Algoritmos y Complejidad . Apuntes de conferencias sobre informática. vol. 2653, págs. 152-164. doi :10.1007/3-540-44849-7_21. ISBN978-3-540-40176-6.
^ Neuwohner, Meike (7 de junio de 2021), Un algoritmo de aproximación mejorado para el problema del conjunto independiente de peso máximo en gráficos libres de d-Claw , arXiv : 2106.03545
^ Cygan, Marek (octubre de 2013). "Aproximación mejorada para coincidencias tridimensionales mediante búsqueda local de ancho de ruta acotado". 2013 54º Simposio Anual del IEEE sobre Fundamentos de la Informática . págs. 509–518. arXiv : 1304.1424 . doi :10.1109/FOCS.2013.61. ISBN978-0-7695-5135-7. S2CID 14160646.
^ Luby (1986).
^ Dyer, Martín; 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.
^ Astuto, Allan (2010). "Transición computacional en el umbral de unicidad". 2010 51º Simposio Anual del IEEE sobre Fundamentos de la Informática . págs. 287–296. doi :10.1109/FOCS.2010.34. ISBN978-1-4244-8525-3. S2CID 901126.
^ Bezáková, Ivona; Galanis, Andrés; Goldberg, Leslie Ann; Guo, Heng; Štefankovič, Daniel (2019). "Aproximación mediante decadencia de correlación cuando falla una fuerte mezcla espacial". 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 gráficos planos regulares de 3". Informática 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; Fomín, Fedor; Goldberg, Leslie Ann; Lapinskas, John (1 de octubre de 2019). "Una perspectiva de parámetros fijos sobre #BIS". Algorítmica . 81 (10): 3844–3864. doi : 10.1007/s00453-019-00606-4 . hdl : 1983/ecb5c34c-d6be-44ec-97ea-080f57c5e6af . ISSN 1432-0541. S2CID 3626662.
^ Cañón, Sarah; Perkins, voluntad (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. ISBN978-1-61197-599-4. S2CID 174799567.
^ Skiena, Steven S. (2012). El manual de diseño de algoritmos . Saltador. ISBN978-1-84800-069-8. OCLC 820425142.
^ Hossain, Ayaan; López, Eriberto; Halper, Sean M.; Cetnar, Daniel P.; Reis, Alejandro C.; Strickland, Devin; Klavins, Eric; Salis, Howard M. (13 de julio de 2020). "Diseño automatizado de miles de piezas no repetitivas para la ingeniería de sistemas genéticos estables". Biotecnología de la Naturaleza . 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 gráficos planos", 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 gráficos de grado 3", Algoritmos y estructuras de datos , 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.
Berman, Piotr; Karpinski, Marek (1999), "Sobre algunos resultados de inaproximabilidad más estrictos", Autómatas, lenguajes y programación, 26º Coloquio Internacional, ICALP'99 Praga , Apuntes de conferencias sobre informática , vol. 1644, Praga: Springer-Verlag , págs. 200-209, doi :10.1007/3-540-48523-6, ISBN 978-3-540-66224-2, S2CID 23288736
Burgués, Nicolás; Escoffier, Bruno; Paschos, Vangelis Th.; van Rooij, Johan MM (2010), "Un método ascendente y algoritmos rápidos para MAX INDEPENDENT SET", Teoría de algoritmos - 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, señor 2678485.
Chan, TM (2003), "Esquemas de aproximación en tiempo polinomial para empaquetar y perforar objetos grasos", 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), "Resolver el problema del conjunto estable ponderado en gráficos sin garras", Journal of the ACM , 61 (4): 1–41, doi :10.1145/2629600, S2CID 1995056.
Fomin, Fedor V.; Grandoni, Fabricio; Kratsch, Dieter (2009), "Un enfoque de medir y conquistar para el análisis de algoritmos exactos", Journal of the ACM , 56 (5): 1–32, doi :10.1145/1552285.1552286, S2CID 1186651, artículo no. 25,.
Frank, András (1976), "Algunos algoritmos polinomiales para ciertos gráficos e hipergráficos", Congressus Numerantium , XV : 211–226.
Füredi, Zoltán (1987), "El número de conjuntos independientes máximos en gráficos conectados", 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 gráficos dispersos y de grados acotados", 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 gráficos 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 máximos independientes de vértices en gráficos 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 gráficos 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 independiente máximo", 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 cuellos de botella: un algoritmo simple de conjunto máximo independiente en gráficos de grado 3", Ciencias de la Computación Teórica , 469 : 92–104, doi : 10.1016/j.tcs.2012.09.022.
Tarjan, RE (1985), "Descomposición por separadores de camarillas", Matemáticas discretas , 55 (2): 221–232, doi : 10.1016/0012-365x(85)90051-2.
