Conjunto independiente (teoría de grafos)

En la teoría del gráfico, una conjunto independiente, conjunto estable, colegiales o anticlique es un conjunto de vértices en un gráfico, no dos de los cuales están adyacentes. Es decir, es un conjunto ${displaystyle S.$ de vértices tales que por cada dos vértices en ${displaystyle S.$, no hay borde que conecta los dos. Equivalentemente, cada borde en el gráfico tiene en la mayoría de un punto final en ${displaystyle S.$. Un conjunto es independiente si y sólo 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 han sido llamados "grupos internally estables", de los cuales "stable set" es un acortamiento.

Un conjunto independiente máximo es un conjunto independiente que no es un subconjunto propio de ningún otro conjunto independiente.

A máximo independiente es un conjunto independiente de mayor tamaño posible para un gráfico dado ${displaystyle G.$. Este tamaño se llama Número de independencia de ${displaystyle G.$ y generalmente se denota ${displaystyle alpha (G)}$. El problema de optimización de encontrar tal conjunto se llama el máximo problema de conjunto independiente. Es un problema fuertemente NP-hard. 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, grafos 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 cubierta de vértice. Por lo tanto, la suma del tamaño del conjunto independiente más grande ${displaystyle alpha (G)}$ y el tamaño de una cubierta mínima de vértice ${displaystyle beta (G)}$ es igual al número de vértices en el gráfico.

Un vértice para colorear un gráfico ${displaystyle G.$ corresponde a una partición de su vértice en subconjuntos independientes. De ahí el número mínimo de colores necesarios en un colorante de vértice, el Número cromático ${displaystyle chi (G)}$, es al menos el cociente del número de vértices en ${displaystyle G.$ y el número independiente ${displaystyle alpha (G)}$.

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 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 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, pero muchos gráficos tienen muchos menos. El número de conjuntos independientes máximos en gráficos de ciclo de n-vértice está dado por los números de Perrin, y el número de conjuntos independientes máximos en gráficos de ruta de n-vértice está dado por Secuencia padova. 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 máximo independiente problema, la entrada es un gráfico no dirigido, y la salida es un conjunto máximo independiente en el gráfico. Si hay múltiples conjuntos máximo independiente, sólo uno necesita ser salida. Este problema a veces se conoce como "relleno de vértice".
• En el set independiente de peso máximo problema, la entrada es un gráfico no dirigido con pesos en sus vértices y la salida es un conjunto independiente con el máximo peso total. El problema de conjunto máximo independiente es el caso especial en el que todos los pesos son uno.
• En el Lista máxima independiente de conjunto problema, la entrada es un gráfico no dirigido, y la salida es una lista de todos sus conjuntos máximo independiente. El problema de conjunto máximo independiente se puede resolver utilizando como una subrutina un algoritmo para el problema de lista de conjuntos máximo independiente, porque el conjunto máximo independiente debe ser incluido entre todos los conjuntos máximo independiente.
• En el decisión independiente problema, 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 de lo 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 complementario 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 conjunto independiente es NP-completo, y por lo tanto no se cree que haya un algoritmo eficiente para resolverlo.
• El problema de conjunto máximo independiente es NP-hard 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; sin embargo, para las mismas clases de gráficos, o incluso para la clase más restringida de gráficos 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 esté dentro de un factor de c del óptimo.

Algoritmos exactos

El problema del conjunto máximo independiente es NP-difícil. Sin embargo, se puede resolver de manera más eficiente que el tiempo O(n² 2ⁿ) que se daría mediante un ingenuo algoritmo de fuerza bruta que examina cada subconjunto de vértices y comprueba si es un conjunto independiente.

A partir de 2017, se puede resolver en el tiempo O(1.1996ⁿ) utilizando el espacio polinomial. Cuando se restringe a gráficos con grado máximo 3, se puede resolver en el tiempo O(1.0836ⁿ).

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, los gráficos sin P₅ y los gráficos perfectos. Para gráficos cordales, se puede encontrar un conjunto independiente de 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 cografos es el ejemplo básico para ello. Otra herramienta importante son los separadores de camarillas descritos por Tarjan.

El teorema de Kőnig implica que en un gráfico bipartito el conjunto independiente máximo se puede encontrar en tiempo polinomial usando un algoritmo de coincidencia bipartito.

Algoritmos de aproximación

En general, el problema del conjunto máximo independiente no se puede aproximar 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. 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.

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 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 de aproximación para tales casos se demostraron en Berman & Karpinski (1999). De hecho, incluso el conjunto Max Independent en 3 gráficos regulares coloreables de 3 bordes es APX completo.

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 solo 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 sólo 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 & Har-Peled (2012).

En gráficos sin d-claw

Una d-claw en un gráfico es un conjunto de vértices d+1, uno de los cuales (el "centro") está conectado a los otros vértices d, pero los otros vértices d no están conectados entre sí. Un gráfico sin garra d es un gráfico que no tiene un subgrafo con garra d. 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 gráficos d-claw-free, cada vértice agregado invalida como máximo los vértices d-1 del conjunto independiente máximo; 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 presentó un algoritmo de tiempo polinomio que, para cualquier constante ε Conf0, encuentra un (d/2-1/63,700,992+ε)-aproximación para el máximo peso independiente establecido en un d- Gráfico libre de garras.
• Cygan presentó un algoritmo de tiempo cuasi-polynomial que, para cualquier ε ratio0, 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. Todos los conjuntos independientes máximos se pueden encontrar en el tiempo O(3^n/3) = O(1.4423ⁿ).

Contando conjuntos independientes

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. 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 polinómico con aleatorización (FPRAS), incluso en gráficos con grado máximo seis; sin embargo, tiene un esquema de aproximación de tiempo totalmente polinomial (FPTAS) en el caso en que el grado máximo sea cinco. 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. No se sabe si #BIS admite un FPRAS.

Aplicaciones

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