Conjunto independiente (teoría de grafos) - Independent set (graph theory)
En la teoría de grafos , un conjunto independiente , conjunto estable , coclique o anticlique es un conjunto de vértices en un gráfico , no hay dos de los cuales son adyacentes. Es decir, es un conjunto de vértices tal que por cada dos vértices adentro , no hay arista que los conecte. De manera equivalente, cada borde del gráfico tiene como máximo un punto final en . Un conjunto es independiente si y solo si es una camarilla en el complemento del gráfico . 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 abreviatura.
Un conjunto independiente máximo es un conjunto independiente que no es un subconjunto propio de ningún otro conjunto independiente.
Un conjunto independiente máximo es un conjunto independiente de mayor tamaño posible para un gráfico dado . Este tamaño se denomina número de independencia de y generalmente se denota por . El problema de optimización de encontrar tal conjunto se denomina problema de conjunto independiente máximo. Es un problema fuertemente NP-difícil . Como tal, es poco probable que exista un algoritmo eficiente para encontrar un conjunto máximo independiente de un gráfico.
Cada conjunto máximo independiente 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 una camarilla en el complemento del gráfico , 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 solo si su complemento es una cobertura de vértice . 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 un vértice 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 la coloración de un vértice, el número cromático , es al menos el cociente entre el número de vértices y el número independiente .
En un gráfico bipartito sin vértices aislados, el número de vértices en un conjunto máximo independiente es igual al número de aristas en una cobertura de aristas mínima ; este es el teorema de Kőnig .
Conjunto independiente máximo
Un conjunto independiente que no es un subconjunto adecuado de otro conjunto independiente se llama máximo . Tales conjuntos son conjuntos dominantes . Cada gráfico contiene como máximo 3 n / 3 conjuntos independientes máximos, pero muchos gráficos tienen muchos menos. El número de conjuntos independientes máximos en los gráficos de ciclo de n - vértices viene dado por los números de Perrin , y el número de conjuntos independientes máximos en los gráficos de trayectoria de n - vértices viene dado por la secuencia de Padovan . Por tanto, ambos números son proporcionales a potencias de 1.324718 ..., el número plástico .
Encontrar conjuntos independientes
En informática , se han estudiado varios problemas computacionales relacionados con conjuntos independientes.
- 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 máximos independientes, solo es necesario generar uno. Este problema a veces se denomina " empaquetamiento de vértices ".
- En el problema del conjunto independiente del 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 el peso total máximo. El problema del conjunto independiente máximo es el caso especial en el que todos los pesos son uno.
- En el problema de listado de conjuntos máximos independientes , la entrada es un gráfico no dirigido y la salida es una lista de todos sus conjuntos independientes máximos. El problema del conjunto independiente máximo puede resolverse utilizando como subrutina un algoritmo para el problema de listado de conjuntos independientes máximos, porque el conjunto independiente máximo debe incluirse entre todos los conjuntos independientes máximos.
- 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 tres primeros de estos problemas son todos 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 NP-completitud a problemas relacionados con conjuntos independientes.
Máximos conjuntos independientes y máximos camarillas
El problema del conjunto independiente y el problema de la camarilla son complementarios: una camarilla en G es un conjunto independiente en el gráfico de complemento de G y viceversa. Por lo tanto, muchos resultados computacionales pueden aplicarse igualmente bien a cualquier problema. 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-hard y también es difícil de aproximar .
A pesar de la estrecha relación entre grupos máximos y conjuntos máximos independientes en gráficos arbitrarios, los problemas de grupos independientes y grupos 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 limitado y se puede encontrar exactamente en tiempo lineal; 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-difícil de encontrar encuentre una solución aproximada que esté dentro de un factor de c del óptimo.
Encontrar conjuntos máximos independientes
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 daría 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 el tiempo O (1.1996 n ) utilizando el espacio polinomial. Cuando se restringe a gráficos con grado máximo 3, se puede resolver en el tiempo O (1.0836 n ).
Para muchas clases de gráficos, se puede encontrar un conjunto independiente del peso máximo en tiempo polinomial. Ejemplos famosos son gráficos sin garra , P 5 gráficos -free y gráficos perfectos . Para los gráficos de cuerdas , se puede encontrar un conjunto independiente del peso máximo en tiempo lineal.
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 cographs es el ejemplo básico de eso. Otra herramienta importante son los separadores de camarillas como los describe Tarjan.
El teorema de Kőnig implica que en un gráfico bipartito, el conjunto independiente máximo se puede encontrar en el tiempo polinomial utilizando un algoritmo de coincidencia bipartito.
Algoritmos de aproximación
En general, el problema del conjunto independiente máximo no se puede aproximar a un factor constante en el tiempo polinomial (a menos que P = NP). De hecho, Max Independent Set en general es Poly-APX-complete , lo que significa que es tan difícil como cualquier problema que se pueda aproximar a un factor polinomial. Sin embargo, existen algoritmos de aproximación eficientes para clases restringidas de gráficos.
En gráficos planos , el conjunto independiente máximo puede aproximarse dentro de cualquier relación de aproximación c <1 en tiempo polinomial; Existen esquemas similares de aproximación polinomial-temporal en cualquier familia de gráficos cerrados para menores .
En los 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 independiente máximo 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 Δ. Los límites de dureza aproximados para tales casos se probaron en Berman y Karpinski (1999) . De hecho, incluso el conjunto independiente máximo en gráficos coloreables de 3 bordes regulares es APX completo .
Conjuntos independientes en gráficos de intersección de intervalos
Un gráfico de intervalo 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 solo si se cruzan. Un conjunto independiente en un gráfico de intervalo es solo 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 polinomial utilizando la primera programación de la fecha límite más temprana .
Conjuntos independientes en gráficas 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 solo un conjunto de formas disjuntas (no superpuestas). 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áficas de intersección sigue siendo NP-completo, pero es más fácil de aproximar que el problema general de conjunto máximo independiente. Se puede encontrar una encuesta reciente en la introducción de Chan & Har-Peled (2012) .
Encontrar conjuntos independientes máximos
El problema de encontrar un conjunto independiente máximo se puede resolver en tiempo polinomial mediante un algoritmo codicioso trivial . Todos los conjuntos independientes máximos se pueden encontrar en el tiempo O (3 n / 3 ) = O (1.4423 n ).
Software para buscar el máximo conjunto independiente
| Nombre | Licencia | Lenguaje API | Breve información |
|---|---|---|---|
| igraph | GPL | C, Python, R, Ruby | solución exacta. "La implementación actual fue trasladada a igraph de la biblioteca de gráficos Very Nauty por Keith Briggs y utiliza el algoritmo del artículo S. Tsukiyama, M. Ide, H. Ariyoshi e I. Shirawaka. Un nuevo algoritmo para generar todos los conjuntos independientes máximos . SIAM J Computing, 6: 505-517, 1977 ". |
| LightGraphs | MIT | Julia | solución exacta. Consulte la documentación para obtener más detalles. |
| NetworkX | BSD | Pitón | solución aproximada, consulte la rutina maximum_independent_set |
| mal | Abierto | Rust (binarios) | solución aproximada mediante muestreo aleatorio del espacio máximo de conjuntos independientes, consulte la página web para obtener más detalles |
Aplicaciones
El conjunto máximo independiente y su problema dual, el mínimo de cobertura de vértices , está involucrado en probar la complejidad computacional de muchos problemas teóricos. También sirven como modelos útiles para problemas de optimización del mundo real, por ejemplo, el conjunto mínimo independiente es un modelo útil para descubrir componentes genéticos estables para diseñar sistemas genéticos modificados genéticamente .
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. Por lo general, se llama coincidencia .
- Una coloración de vértices es una partición del conjunto de vértices en conjuntos independientes.
Notas
Referencias
- Baker, Brenda S. (1994), "Algoritmos de aproximación para problemas NP-completos en gráficas planas", 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", Workshop on Algorithms and Data Structures , Lecture Notes in Computer Science, 955 , Springer-Verlag , pp. 449-460, doi : 10.1007 / 3-540-60220-8_84 , ISBN 978-3-540-60220-0.
- Berman, Piotr; Karpinski, Marek (1999), "Sobre unos resultados de inaproximabilidad más ajustados", Autómatas, lenguajes y programación, 26º Coloquio Internacional, ICALP'99 Praga , Lecture Notes in Computer Science , 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, 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, MR 2678485.
- Chan, TM (2003), "Esquemas de aproximación de tiempo polinómico 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.
- Chan, TM ; Har-Peled, S. (2012), "Algoritmos de aproximación para un conjunto máximo independiente de pseudodiscos", Geometría discreta y computacional , 48 (2): 373, arXiv : 1103.1431 , CiteSeerX 10.1.1.219.2131 , doi : 10.1007 / s00454-012-9417-5 , S2CID 38183751.
- Chiba, N .; Nishizeki, T. (1985), "Arboricity and subgraph Listing algoritmos", SIAM Journal on Computing , 14 (1): 210-223, doi : 10.1137 / 0214017.
- Erlebach, T .; Jansen, K .; Seidel, E. (2005), "Esquemas de aproximación de tiempo polinomial para gráficos de intersección geométrica", SIAM Journal on Computing , 34 (6): 1302, doi : 10.1137 / s0097539702402676.
- Faenza, Y .; Oriolo, G .; Stauffer, G. (2014), "Resolver el problema de conjuntos estables ponderados en gráficos 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 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. 25CS1 maint: posdata ( enlace ).
- Frank, Andras (1976), "Algunos algoritmos polinomiales para ciertos gráficos e hipergráficos ", Congressus Numerantium , XV : 211-226.
- Füredi, Z. (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.
- Godsil, Chris ; Royle, Gordon (2001), Teoría de grafos algebraicos , Nueva York: Springer , ISBN 978-0-387-95220-8.
- Grohe, Martin (2003), "Ancho de árbol local, menores excluidos y algoritmos de aproximación", Combinatorica , 23 (4): 613–632, arXiv : math / 0001128 , doi : 10.1007 / s00493-003-0037-9 , S2CID 11751235.
- Grötschel, M .; Lovász, L .; Schrijver, A. (1988), "9.4 Colorear gráficos perfectos", algoritmos geométricos y optimización combinatoria , algoritmos y combinatoria, 2 , Springer-Verlag , págs. 296-298, ISBN 978-0-387-13624-0.
- 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 de conjuntos independientes máximos", 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.
- Luna, JW; Moser, Leo (1965), "On cliques in graphs", Israel Journal of Mathematics , 3 (1): 23-28, doi : 10.1007 / BF02760024 , MR 0182577 , S2CID 9855414.
- 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 del conjunto estable ponderado en gráficos sin garras , arXiv : 1501.05775 , Bibcode : 2015arXiv150105775N
- Robson, JM (1986), "Algoritmos para conjuntos máximos independientes", 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", Discrete Mathematics (en francés), 29 (1): 53–76, doi : 10.1016 / 0012-365X (90 ) 90287-R , MR 0553650.
- Xiao, Mingyu; Nagamochi, Hiroshi (2017), "Algoritmos exactos para un conjunto máximo independiente", Información y cálculo , 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 de conjunto independiente máximo simple en gráficos de grado 3", Ciencias de la computación teóricas , 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.