El problema de los conjuntos independientes

El problema de conjuntos independientes pertenece a la clase de problemas NP-completos en el campo de la teoría de grafos . Equivalente al problema de la camarilla .

Definiciones

Un conjunto de vértices en un gráfico se llama independiente si no hay dos vértices de este conjunto que estén conectados por una arista. En otras palabras, el subgrafo inducido por este conjunto consta de vértices aislados. También se dice a veces que cada arista de un gráfico incide como máximo en un vértice de un conjunto independiente. El problema de reconocimiento (problema de decidibilidad) se ve así: ¿un gráfico G dado tiene un conjunto independiente de tamaño k ? El problema de optimización que le corresponde, también conocido como problema de los conjuntos independientes , se formula de la siguiente manera: en un grafo G dado , se requiere encontrar un conjunto independiente de tamaño máximo. Este tamaño se denomina número de independencia , número de densidad interna o holgura y se denota como [1] [2] . ${\ estilo de visualización \ alfa (G)}$

Este problema a veces se denomina encontrar el conjunto independiente más grande . Este concepto no debe confundirse con el conjunto máximo independiente , o el conjunto máximo independiente por inclusión , que se define como un conjunto de vértices tan independiente que cuando se le añade un vértice más (cualquiera) del grafo original, deja de serlo. ser independientes (por lo general, puede haber conjuntos de este tipo de varios y de diferentes tamaños). Un conjunto independiente de inclusión máxima no es siempre el más grande. Al mismo tiempo, todo conjunto independiente mayor es, por definición, también máximo por inclusión. Para encontrar (algún) conjunto independiente máximo con respecto a la inclusión, se puede usar un algoritmo codicioso que se ejecuta en tiempo polinomial, mientras que el problema del conjunto independiente más grande pertenece a la clase de problemas NP-completos.

Un conjunto independiente de máxima inclusión es un conjunto dominante . Cualquier gráfico contiene un máximo de 3 n /3 conjuntos independientes máximos de inclusión [3] , pero la mayoría de los gráficos tienen muchos menos.

El número de conjuntos independientes máximos de inclusión en ciclos de n vértices es números de Perrin , y el número de conjuntos independientes máximos de inclusión en caminos con n vértices viene dado por la secuencia de Padovan [4] . Por tanto, ambos números son proporcionales a la potencia de 1,324718, el número plástico .

El subconjunto independiente más pequeño en un gráfico es cualquier vértice de ese gráfico.

Relación con otros parámetros del gráfico

Un conjunto es independiente si y sólo si es un clique en el complemento del grafo , de manera que los dos conceptos se complementan. Los gráficos suficientemente grandes sin camarillas grandes tienen grandes conjuntos independientes, que es el tema de estudio en la teoría de Ramsey .

Un conjunto es independiente si y sólo si su complemento es una cubierta de vértices . La suma del número de independencia y el número de cobertura de vértices es igual al número de vértices en el gráfico (la primera identidad de Gallai ). ${\ estilo de visualización \ alfa (G)}$ ${\ estilo de visualización \ tau (G)}$

La coloración de los vértices de un grafo corresponde a la división de sus vértices en subconjuntos independientes. Por lo tanto, el número mínimo de colores necesarios para colorear los vértices, el número cromático , no es menor que el cociente del número de vértices y el número de independencia . $GRAMO$ $\ chi (G)$ $GRAMO$ ${\ estilo de visualización \ alfa (G)}$

En gráficos bipartitos que no tienen vértices aislados, el número de vértices en el conjunto independiente más grande es igual al número de aristas en la cubierta de aristas más pequeña (una consecuencia del teorema de König ).

Búsqueda de conjuntos independientes

En informática , se estudian varios problemas computacionales relacionados con conjuntos independientes:

En el problema del conjunto independiente más grande, la entrada es un gráfico no dirigido y la salida es el conjunto independiente más grande en ese gráfico. Si hay varios conjuntos de este tipo, basta con encontrar uno.
En el problema del conjunto independiente de peso máximo, la entrada es un gráfico no dirigido con pesos de vértice y la salida es un conjunto independiente con el peso total máximo. El problema del conjunto independiente máximo de inclusión es un caso especial de este problema con pesos iguales a uno.
En el problema de enumerar conjuntos independientes de inclusión máxima, la entrada es un gráfico no dirigido y la salida es una lista de todos los conjuntos independientes de inclusión máxima. El problema del mayor conjunto independiente se puede resolver como un subproblema de este problema, ya que el mayor conjunto independiente es el máximo por inclusión y debe incluirse en esta lista.
En el problema de tener un conjunto independiente de un tamaño dado, la entrada es un gráfico no dirigido y un número k , y la salida es Sí / No : Sí si el gráfico contiene un conjunto independiente de tamaño k , y No en caso contrario.

Los primeros tres problemas son importantes en aplicaciones prácticas, mientras que el último es importante para la teoría de la completitud NP para problemas relacionados con conjuntos independientes.

El problema de los conjuntos independientes y el problema de la camarilla son duales: una camarilla en G es un conjunto independiente en el complemento de G y viceversa. Por lo tanto, muchos resultados computacionales se pueden aplicar igualmente bien a ambos problemas. Por ejemplo, los resultados asociados con el problema de la camarilla tienen las siguientes consecuencias:

El problema de presencia es NP-completo , lo que significa que no se ha demostrado la existencia (al igual que la inexistencia) de un algoritmo efectivo para resolverlo. Existen algoritmos heurísticos efectivos (que se aproximan a [5] ) para encontrar el conjunto de vértices independientes de peso máximo en un gráfico, un ejemplo de los cuales es el algoritmo de Rusov V.S. y Zakharova D.A. de complejidad O( n 3 ).
El mayor problema de conjuntos independientes es NP-difícil y, además, difícil de aproximar .

Encontrar el conjunto independiente más grande

Este problema a veces se denomina " empaquetamiento de vértices ".

El problema del conjunto independiente más grande y el problema de la camarilla más grande son polinómicamente equivalentes: uno puede encontrar el conjunto independiente más grande encontrando la camarilla máxima en el complemento del gráfico, por lo que a muchos autores no les importa especialmente separar los dos problemas. Ambos problemas son NP-completos, por lo que es poco probable que se resuelvan en tiempo polinomial. Sin embargo, el problema del conjunto independiente más grande se puede resolver de manera más eficiente que en el tiempo O( n 2 2 n ), lo que produce una búsqueda exhaustiva que prueba todos los subconjuntos de vértices para ver si son conjuntos independientes. El algoritmo de Robson [6] resuelve el problema en O(2 0.276 n ) tiempo usando el espacio exponencial. Si hay un límite en el tamaño (espacio polinomial), hay un algoritmo para resolver en el tiempo O*(1.2127 n ) [7] .

A pesar de la estrecha relación entre la camarilla más grande y el conjunto independiente más grande en un gráfico arbitrario, los problemas de encontrar un conjunto independiente y una camarilla pueden diferir significativamente cuando se resuelven en una clase especial de gráficos. Por ejemplo, para gráficos dispersos (gráficos en los que el número de aristas en cualquier subgráfico no es mayor que el número de vértices multiplicado por alguna constante), la camarilla más grande tiene un tamaño limitado y se puede encontrar exactamente en tiempo lineal [8] . Sin embargo, para las mismas clases de grafos, o incluso para el caso de restricciones más estrictas para una clase de grafos con grado acotado, la búsqueda del conjunto independiente más grande es MAXSNP-completo , lo que significa que para alguna constante c (dependiendo en el grado) NP - es difícil encontrar una solución aproximada que difiera en un factor c de la óptima [9] . Sin embargo, se conocen algoritmos aproximados eficientes, pero su eficiencia garantizada es peor que este umbral. Por ejemplo, un algoritmo codicioso crea un conjunto independiente de máxima inclusión eligiendo un vértice con el grado mínimo en cada paso y eliminando a sus vecinos. Este algoritmo logra eficiencia garantizada (Δ+2)/3 en gráficos con grado máximo Δ [10] .

En algunas clases de gráficos (incluidos los gráficos sin garras [11] y los gráficos perfectos [12] ; los árboles también pertenecen a la última clase ), el conjunto independiente más grande se puede encontrar en tiempo polinomial. Para grafos planos , el mayor problema de conjunto independiente sigue siendo NP-completo para una solución exacta, pero se puede aproximar con cualquier eficiencia garantizada c < 1 en tiempo polinomial. Existen esquemas de tiempo polinomial aproximado similares en cualquier familia de grafos cerrados menores [13] [14] .

En gráficos bipartitos, todos los vértices que no están en la cubierta de vértice más pequeña se pueden incluir en el conjunto independiente más grande (ver el teorema de König ). Por lo tanto, el conjunto independiente más grande se puede encontrar utilizando el algoritmo para encontrar las coincidencias más grandes en gráficos bipartitos.

Búsqueda de conjuntos independientes de máxima inclusión

Todos los conjuntos independientes de máxima inclusión se pueden encontrar en tiempo O(3 n /3 ).

Software para encontrar conjuntos independientes

Nombre	Licencia	lenguaje API	Descripción
igrafo	GPL	C, Python, R, Rubí	solución exacta
RedX	BSD	Pitón	solución aproximada, ver procedimiento conjunto_independiente_máximo
opción abierta	BSD	Pitón	soluciones exactas y aproximadas, la capacidad de especificar los vértices que deben incluirse / excluirse. Consulte la clase STAB para obtener detalles y ejemplos.

Conjunto independiente más grande en un árbol

Si el gráfico dado es un árbol , entonces el problema de conjuntos independientes se resuelve efectivamente mediante programación dinámica .

Subestructura óptima del problema

La estructura del árbol en sí sugiere la solución al problema. Es decir, denotamos cualquier vértice como la raíz del árbol y lo llamamos . Denotemos el tamaño del mayor conjunto independiente de vértices del subárbol cuya raíz es el vértice . Entonces la respuesta al problema será . $r$ $yo (tu)$ $tu$ $yo(r)$

Es fácil ver que si incluimos el vértice u en el conjunto independiente más grande, entonces su cardinalidad aumenta en 1, pero no podemos tomar sus hijos (ya que están conectados por una arista al vértice u ); si no incluimos este vértice, entonces la cardinalidad del conjunto independiente más grande será igual a la suma de los tamaños de los conjuntos independientes de los hijos de este vértice. Solo queda elegir el máximo de estas dos opciones para obtener una solución al problema:

I(u)=\max \left\{1\ +\ \sum_{{{\text{nieto}}\ w\ de\ u}}I(w),\ \sum_{{{\text{ child}}\ w\ of\ u}}I(w)\right\},

donde nieto denota cualquier "nieto" del vértice, y niño denota cualquier descendiente del vértice.

Pseudocódigo

Consideramos que en la parte superior se almacena u : $yo (tu)$

función get_independent_set(Nodo u) { si I(u) ya ha sido calculado, devuelva I(u) // cardinalidad del conjunto que se puede obtener si no tomamos el vértice u niños_suma = 0 // cardinalidad del conjunto que se puede obtener tomando el vértice u nietos_sum = 0 // recorrer todos los hijos for i := 1 to child_num hacer suma_hijos = suma_hijos + get_conjunto_independiente(hijos[i]) // recorrer todos los nietos para i:= 1 a nietos_num nietos_sum = nietos_sum + get_independent_set(nietos[i]) // recuerda, para no volver a calcular I(u) = max(1 + suma_nietos, suma_hijos) vuelvo yo(t) }

Llamar a get_independent_set( r ) dará la respuesta al problema. El tiempo de ejecución del algoritmo es obviamente O (|V| + |E|).

Véase también

El algoritmo de Bron-Kerbosh para encontrar el máximo (por inclusión) de conjuntos independientes de vértices.

Notas

↑ Chris Godsil, Gordon Royle. . Teoría algebraica de grafos. - Nueva York: Springer , 2001. - ISBN 0-387-95220-9 . — Pág. 3.
↑ Evstigneev V. A., Kasyanov V. N. . Diccionario de grafos en informática. - Novosibirsk, 200. - (Diseño y optimización de programas, número 17). - ISBN 978-591124-036-3 .
↑ Moon J. W., Moser L. Sobre camarillas en gráficos // Israel Journal of Mathematics. - 1965. - Vol. 3, núm. 1. - Pág. 23–28. -doi : 10.1007/ BF02760024 .
↑ Furedi, Zoltán. El número de conjuntos máximamente independientes en gráficos conectados // Journal of Graph Theory. - 1987. - vol. 11, núm. 4.- Pág. 463-470. -doi : 10.1002 / jgt.3190110403 .
↑ Del artículo de Rusov y Zakharova a continuación: Recientemente, los algoritmos heurísticos, es decir, algoritmos que aún permiten resolver un problema NP-completo, pero con algún error, han sido de gran interés para resolver este tipo de problemas. Los principales criterios para evaluar un algoritmo heurístico son la "eficiencia de tiempo" y el error en relación con el algoritmo exacto.
↑ Robson J. M. Algoritmos para conjuntos independientes máximos // Journal of Algorithms. - 1986. - vol. 7, núm. 3.- Págs. 425-440. - doi : 10.1016/0196-6774(86)90032-5 .
↑ Nicolás Bourgeois, Bruno Escoffier, Vangelis Th. Paschos, Johan M. M. van Rooij. . Un método ascendente y algoritmos rápidos para MAX INDEPENDENT SET // Teoría de algoritmos: SWAT 2010 . - Berlín: Springer , 2010. - (Lecture Notes in Computer Science, vol. 6139). -doi : 10.1007 / 978-3-642-13731-0_7 . — págs. 62–73.
↑ Chiba N., Nishizeki T. Arboricidad y algoritmos de listado de subgrafos // SIAM Journal on Computing . - 1985. - vol. 14, núm. 1.- Pág. 210-223. -doi : 10.1137/ 0214017 .
↑ Piotr Berman, Toshihiro Fujito. . Sobre las propiedades de aproximación del problema de conjuntos independientes para grafos de grado 3 // Cuarto Taller Internacional de Algoritmos y Estructuras de Datos. - Springer , 1995. - (Lecture Notes in Computer Science, vol. 995). -doi : 10.1007/ 3-540-60220-8_84 . - Pág. 449-460.
↑ Halldórsson M. M., Radhakrishnan J. Greed is good: Aproximación de conjuntos independientes en gráficos dispersos y de grado acotado // Algorithmica . - 1997. - vol. 18, núm. 1.- Pág. 145-163. -doi : 10.1007/ BF02523693 . .
↑ Sbihi, 1980 .
↑ Grötschel, Lovász, Schrijver, 1988 .
↑ Brenda S. Baker. Algoritmos de aproximación para problemas NP-completos en grafos planos // Journal of the ACM . - 1994. - vol. 41, núm. 1.- Pág. 153-180. -doi : 10.1145/ 174644.174650 .
↑ Martín Grohe. Ancho de árbol local, menores excluidos y algoritmos de aproximación // Combinatorica . - 2003. - vol. 23, núm. 4.- Pág. 613-632. -doi : 10.1007/ s00493-003-0037-9 .

Literatura

Chris Godsil, Gordon Royle. . Teoría algebraica de grafos. - Nueva York: Springer , 2004. - ISBN 0-387-95220-9 .
Grötschel M., Lovász L., Schrijver A. . 9.4. Coloreando Gráficos Perfectos // Algoritmos Geométricos y Optimización Combinatoria. - Springer , 1988. - (Algoritmos y Combinatoria, vol. 2). — ISBN 0-387-13624-X . - Pág. 296-298.
Karpe, Ricardo. Reducibilidad entre problemas combinatorios // Actas de un simposio sobre la complejidad de los cálculos informáticos. — 1972.
Michael R. Garey, David S. Johnson. . Computadoras e intratabilidad: una guía para la teoría de la integridad NP . - WH Freeman, 1979. - ISBN 0-7167-1045-5 .
Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani. . Capítulo 6. Programación Dinámica // Algoritmos. — Ciencias/Ingeniería/Matemáticas de McGraw-Hill, 2006. — ISBN 0073523402 . — Pág. 336.
Sbihi, Najiba Sbihi. Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile // Matemáticas discretas. - 1980. - vol. 29, núm. 1. - Pág. 53–76. - doi : 10.1016/0012-365X(90)90287-R .

Enlaces

Weisstein, Eric W. Conjunto de vértices independientes máximos en Wolfram MathWorld .
Puntos de referencia desafiantes para la camarilla máxima, el conjunto independiente máximo, la cobertura mínima de vértices y la coloración de vértices
Polikarpova N., Gerasimenko A. Métodos para resolver problemas difíciles
Diapositivas de conferencias de programación dinámica
Video conferencias sobre programación dinámica
Rusov VS, Zakharova D.A. Algoritmo heurístico para encontrar el conjunto de vértices independiente del peso máximo en un gráfico

Problemas NP-completos
Problema de maximización del apilamiento (packing)	Envasado en contenedores embalaje bidimensional embalaje lineal embalaje por peso embalaje por valor El problema de la mochila
teoría de grafos teoría de conjuntos	Problema de cobertura de vértices Haga clic en problema El problema de un conjunto independiente (conjunto) Establecer problema de cobertura Problema de Steiner El problema del viajante de comercio Problema generalizado del viajante de comercio
Problemas algorítmicos	Problema de satisfacibilidad para fórmulas booleanas (en forma normal conjuntiva)
Juegos de lógica y rompecabezas.	Etiquetas generalizadas (juego en N 2 -1) problema de solución más corta Problemas cuyas soluciones se aplican en Tetris Problema de sudoku generalizado Problema de llenado de cuadrados latinos La tarea de Kakuro
Clases de dificultad La investigación de operaciones Mejoramiento optimización combinatoria Matemáticas Aplicadas Teoría de Algoritmos Programación dinámica 21 Problema de Karp NP-completo