stringtranslate.com

Conjunto independiente (teoría de grafos)

Los nueve vértices azules forman un conjunto máximo independiente para el gráfico de Petersen generalizado GP(12,4).

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 maximal 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 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 .

En un gráfico bipartito sin vértices aislados, el número de vértices en un conjunto independiente máximo es igual al número de aristas en un recubrimiento de aristas mínimo ; este es el teorema de König .

Conjunto independiente maximo

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 está dado por los números de Perrin , y el número de conjuntos independientes maximales en grafos de camino de n -vértices está dado por la secuencia de Padovan . [6] Por lo tanto, ambos números son proporcionales a potencias de 1.324718..., la razón plástica .

Encontrar conjuntos independientes

En informática se han estudiado varios problemas computacionales relacionados con conjuntos independientes.

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 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:

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 del 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 del 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 grafos planares

En los grafos planares , el conjunto independiente máximo puede aproximarse dentro de cualquier razón de aproximación c  < 1 en tiempo polinomial; existen esquemas de aproximación en tiempo polinomial similares en cualquier familia de grafos cerrados bajo la adopción de menores . [17]

En gráficos de grado acotado

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:

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]

También se ha estudiado la cuestión del recuento de conjuntos independientes máximos .

Aplicaciones

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

Notas

  1. ^ Korshunov (1974)
  2. ^ Godsil y Royle (2001), pág. 3.
  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.
  4. ^ 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.
  5. ^ Luna y Moser (1965).
  6. ^ Füredi (1987).
  7. ^ Chiba y Nishizeki (1985).
  8. ^ Berman y Fujito (1995).
  9. ^ Xiao y Nagamochi (2017)
  10. ^ Xiao y Nagamochi (2013)
  11. ^ Minty (1980),Sbihi (1980),Nakamura y Tamura (2001),Faenza, Oriolo y Stauffer (2014),Nobili y Sassano (2015)
  12. ^ Lokshtanov, Vatshelle y Villanger (2014)
  13. ^ Grötschel, Lovász & Schrijver (1993, Capítulo 9: Conjuntos estables en gráficos)
  14. ^ Franco (1976)
  15. ^ Tarjan (1985)
  16. ^ 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.
  17. ^ Banco de Inglaterra (1994);
  18. ^ Halldórsson y Radhakrishnan (1997).
  19. ^ Chlebík, Miroslav; Chlebíková, Janka (2003). "Dureza de aproximación para instancias de ocurrencia pequeña 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.
  20. ^ 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
  21. ^ 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. ISBN 978-0-7695-5135-7.S2CID14160646  .​
  22. ^ Luby (1986).
  23. ^ 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.
  24. ^ 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. ISBN 978-1-4244-8525-3.S2CID 901126  .
  25. ^ 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.
  26. ^ 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.
  27. ^ 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  .​
  28. ^ Skiena, Steven S. (2012). Manual de diseño de algoritmos . Springer. ISBN 978-1-84800-069-8.OCLC 820425142  .
  29. ^ 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

Enlaces externos