Conjunto independiente maximo

En teoría de grafos , un conjunto independiente maximal ( MIS ) o conjunto estable maximal es un conjunto independiente que no es un subconjunto de ningún otro conjunto independiente. En otras palabras, no hay ningún vértice fuera del conjunto independiente que pueda unirse a él porque es maximal con respecto a la propiedad del conjunto independiente.

Por ejemplo, en el grafo P ₃ , un camino con tres vértices a , b y c , y dos aristas ab y bc , los conjuntos { b } y { a , c } son ambos máximamente independientes. El conjunto { a } es independiente, pero no es máximamente independiente, porque es un subconjunto del conjunto independiente más grande { a , c }. En este mismo grafo, las camarillas máximas son los conjuntos { a , b } y { b , c }.

Un MIS también es un conjunto dominante en el gráfico, y cada conjunto dominante que sea independiente debe ser máximamente independiente, por lo que los MIS también se denominan conjuntos dominantes independientes .

Un grafo puede tener muchos MIS de tamaños muy variables; ^[a] el MIS más grande, o posiblemente varios de igual tamaño, de un grafo se denomina conjunto independiente máximo . Los grafos en los que todos los conjuntos independientes máximos tienen el mismo tamaño se denominan grafos bien cubiertos .

La frase "conjunto independiente máximo" también se utiliza para describir subconjuntos máximos de elementos independientes en estructuras matemáticas distintas de los gráficos, y en particular en espacios vectoriales y matroides .

Los MIS tienen dos problemas algorítmicos asociados: encontrar un único MIS en un gráfico determinado y enumerar todos los MIS en un gráfico determinado.

Para un gráfico , un conjunto independiente es un conjunto independiente maximalista si para , se cumple una de las siguientes condiciones: ^[1]${\displaystyle G=(V,E)}$ ${\estilo de visualización S}$${\displaystyle v\en V}$

1. ${\displaystyle v\en S}$
2. ${\displaystyle N(v)\cap S\neq \conjunto vacío}$donde denota los vecinos de${\estilo de visualización N(v)}$${\estilo de visualización v}$

Lo anterior se puede reformular como un vértice que pertenece al conjunto independiente o tiene al menos un vértice vecino que pertenece al conjunto independiente. Como resultado, cada arista del grafo tiene al menos un punto final que no está en . Sin embargo, no es cierto que cada arista del grafo tenga al menos un punto final, o incluso un punto final en${\estilo de visualización S}$${\estilo de visualización S}$

Tenga en cuenta que cualquier vecino de un vértice en el conjunto independiente no puede estar en porque estos vértices son disjuntos según la definición del conjunto independiente.${\estilo de visualización S}$${\estilo de visualización S}$

Si S es un conjunto independiente maximal en algún grafo, es un clique maximal o un subgrafo completo maximal en el grafo complementario . Un clique maximal es un conjunto de vértices que induce un subgrafo completo , y que no es un subconjunto de los vértices de ningún subgrafo completo mayor. Es decir, es un conjunto S tal que cada par de vértices en S está conectado por una arista y a cada vértice que no está en S le falta una arista en al menos un vértice en S . Un grafo puede tener muchos cliques maximal, de distintos tamaños; encontrar el más grande de estos es el problema del clique máximo .

Algunos autores incluyen la maximalidad como parte de la definición de camarilla y se refieren a las camarillas maximalistas simplemente como camarillas.

El complemento de un conjunto independiente maximal, es decir, el conjunto de vértices que no pertenecen al conjunto independiente, forma una cubierta de vértices mínima . Es decir, el complemento es una cubierta de vértices , un conjunto de vértices que incluye al menos un punto final de cada arista, y es mínima en el sentido de que ninguno de sus vértices puede eliminarse mientras se conserva la propiedad de que es una cubierta. Las cubiertas de vértices mínimas se han estudiado en mecánica estadística en conexión con el modelo de gas reticular de esferas duras , una abstracción matemática de las transiciones de estado fluido-sólido. ^[2]

Todo conjunto independiente maximal es un conjunto dominante , un conjunto de vértices tal que cada vértice del grafo pertenece al conjunto o es adyacente al conjunto. Un conjunto de vértices es un conjunto independiente maximal si y solo si es un conjunto dominante independiente.

Ciertas familias de grafos también han sido caracterizadas en términos de sus camarillas máximas o conjuntos independientes máximos. Algunos ejemplos incluyen los grafos irreducibles de camarilla máxima y los grafos irreducibles de camarilla máxima hereditarios. Se dice que un grafo es irreducible de camarilla máxima si cada camarilla máxima tiene una arista que no pertenece a ninguna otra camarilla máxima, y ​​que es irreducible de camarilla máxima hereditario si la misma propiedad es verdadera para cada subgrafo inducido. ^[3] Los grafos irreducibles de camarilla máxima hereditarios incluyen grafos sin triángulos , grafos bipartitos y grafos de intervalo .

Los cografos pueden caracterizarse como grafos en los que cada camarilla máxima intersecta cada conjunto independiente máximo, y en los que la misma propiedad es verdadera en todos los subgrafos inducidos.

Moon y Moser (1965) demostraron que cualquier grafo con n vértices tiene como máximo 3 ^{n /3} camarillas máximas. Complementariamente, cualquier grafo con n vértices también tiene como máximo 3 ^{n /3} conjuntos independientes máximos. Un grafo con exactamente 3 ^{n /3} conjuntos independientes máximos es fácil de construir: simplemente tome la unión disjunta de grafos triangulares n /3 . Cualquier conjunto independiente máximo en este grafo se forma eligiendo un vértice de cada triángulo. El grafo complementario, con exactamente 3 ^{n /3} camarillas máximas, es un tipo especial de grafo de Turán ; debido a su conexión con el límite de Moon y Moser, estos grafos también se denominan a veces grafos Moon-Moser. Son posibles límites más estrictos si se limita el tamaño de los conjuntos independientes máximos: el número de conjuntos independientes máximos de tamaño k en cualquier grafo de n vértices es como máximo

${\displaystyle \lfloor n/k\rfloor ^{k-(n{\bmod {k}})}\lfloor n/k+1\rfloor ^{n{\bmod {k}}}.}$

Los grafos que alcanzan este límite son nuevamente grafos de Turán. ^[4]

Ciertas familias de grafos pueden, sin embargo, tener límites mucho más restrictivos en el número de conjuntos independientes máximos o camarillas máximas. Si todos los grafos de n -vértices en una familia de grafos tienen O( n ) aristas, y si cada subgrafo de un grafo en la familia también pertenece a la familia, entonces cada grafo en la familia puede tener como máximo O( n ) camarillas máximas, todas las cuales tienen tamaño O(1). ^[5] Por ejemplo, estas condiciones son verdaderas para los grafos planares : cada grafo planar de n -vértices tiene como máximo 3 n  − 6 aristas, y un subgrafo de un grafo planar es siempre planar, de lo cual se sigue que cada grafo planar tiene O( n ) camarillas máximas (de tamaño como máximo cuatro). Los grafos de intervalos y los grafos cordales también tienen como máximo n camarillas máximas, aunque no siempre sean grafos dispersos .

El número de conjuntos independientes máximos en gráficos de ciclos de n vértices está dado por los números de Perrin , y el número de conjuntos independientes máximos en gráficos de rutas 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 relación plástica .

Dado un gráfico G(V,E), es fácil encontrar un único MIS utilizando el siguiente algoritmo:

1. Inicializar I en un conjunto vacío.
2. Mientras V no esté vacío:
   • Elija un nodo v∈V;
   • Añadir v al conjunto I;
   • Eliminar de V el nodo v y todos sus vecinos.
3. Regresar I.

El siguiente algoritmo encuentra un MIS en el tiempo O(log n ). ^{[1] [7] [8]}

1. Inicializar I en un conjunto vacío.
2. Mientras V no esté vacío:
   • Elija un conjunto aleatorio de vértices S ⊆ V, seleccionando cada vértice v independientemente con probabilidad 1/(2d(v)), donde d es el grado de v (el número de vecinos de v).
   • Para cada arista de E, si ambos puntos extremos están en el conjunto aleatorio S, entonces se elimina de S el punto extremo cuyo grado es menor (es decir, tiene menos vecinos). Se rompen los empates arbitrariamente, por ejemplo, usando un orden lexicográfico en los nombres de los vértices.
   • Suma el conjunto S a I.
   • Eliminar de V el conjunto S y todos los vecinos de los nodos en S.
3. Regresar I.

ANÁLISIS : Para cada nodo v, dividir sus vecinos en vecinos inferiores (cuyo grado es menor que el grado de v) y vecinos superiores (cuyo grado es mayor que el grado de v), rompiendo los empates como en el algoritmo.

Se considera que un nodo es v malo si más de 2/3 de sus vecinos son vecinos superiores. Se considera que una arista es mala si ambos puntos finales son malos; de lo contrario, la arista es buena .

• Al menos la mitad de todas las aristas son siempre buenas. PRUEBA: Construya una versión dirigida de G dirigiendo cada arista al nodo con el grado más alto (rompiendo los empates arbitrariamente). Entonces, para cada nodo malo, la cantidad de aristas salientes es más del doble de la cantidad de aristas entrantes. Entonces, cada arista mala que ingresa a un nodo v se puede emparejar con un conjunto distinto de dos aristas que salen del nodo v. Por lo tanto, la cantidad total de aristas es al menos el doble de la cantidad de aristas malas.
• Para cada nodo bueno u, la probabilidad de que un vecino de u sea seleccionado para S es al menos una cierta constante positiva. PRUEBA: la probabilidad de que NINGÚN vecino de u sea seleccionado para S es, como máximo, la probabilidad de que ninguno de los vecinos inferiores de u sea seleccionado. Para cada vecino inferior v, la probabilidad de que no sea seleccionado es (1-1/2d(v)), que es como máximo (1-1/2d(u)) (ya que d(u)>d(v)). El número de tales vecinos es al menos d(u)/3, ya que u es bueno. Por lo tanto, la probabilidad de que ningún vecino inferior sea seleccionado es como máximo 1-exp(-1/6).
• Para cada nodo u que se selecciona para S, la probabilidad de que u sea eliminado de S es como máximo 1/2. PRUEBA: Esta probabilidad es como máximo la probabilidad de que un vecino superior de u sea seleccionado para S. Para cada vecino superior v, la probabilidad de que sea seleccionado es como máximo 1/2d(v), que es como máximo 1/2d(u) (ya que d(v)>d(u)). Por límite de unión, la probabilidad de que no se seleccione ningún vecino superior es como máximo d(u)/2d(u) = 1/2.
• Por lo tanto, para cada nodo bueno u, la probabilidad de que un vecino de u sea seleccionado para S y permanezca en S es una cierta constante positiva. Por lo tanto, la probabilidad de que u sea eliminado, en cada paso, es al menos una constante positiva.
• Por lo tanto, para cada arista buena e, la probabilidad de que e se elimine, en cada paso, es al menos una constante positiva. Por lo tanto, el número de aristas buenas disminuye al menos en un factor constante en cada paso.
• Dado que al menos la mitad de los bordes son buenos, el número total de bordes también disminuye en un factor constante en cada paso.
• Por lo tanto, el número de pasos es O(log m ), donde m es el número de aristas. Esto está limitado por .${\displaystyle O(\log(n))}$

Un gráfico del peor caso, en el que el número promedio de pasos es , es un gráfico formado por n /2 componentes conectados, cada uno con 2 nodos. El grado de todos los nodos es 1, por lo que cada nodo se selecciona con una probabilidad de 1/2, y con una probabilidad de 1/4 no se eligen los dos nodos de un componente. Por lo tanto, el número de nodos se reduce en un factor de 4 en cada paso, y el número esperado de pasos es .${\displaystyle \Theta (\log(n))}$${\displaystyle \log _{4}(n)}$

El siguiente algoritmo es mejor que el anterior en el sentido de que siempre se agrega al menos un nuevo nodo en cada componente conectado: ^{[9] [8]}

1. Inicializar I en un conjunto vacío.
2. Mientras V no esté vacío, cada nodo v hace lo siguiente:
   • Selecciona un número aleatorio r(v) en [0,1] y lo envía a sus vecinos;
   • Si r(v) es menor que el número de todos los vecinos de v, entonces v se inserta en I, se retira de V y se lo cuenta a sus vecinos;
   • Si v escucha que uno de sus vecinos se metió en I, entonces v se retira de V.
3. Regresar I.

Tenga en cuenta que en cada paso, el nodo con el número más pequeño en cada componente conectado siempre ingresa a I, por lo que siempre hay algún progreso. En particular, en el peor caso del algoritmo anterior ( n /2 componentes conectados con 2 nodos cada uno), se encontrará un MIS en un solo paso.

ANÁLISIS :

• Un nodo tiene probabilidad al menos de ser eliminado. PRUEBA: Para cada arista que conecta un par de nodos , reemplácela con dos aristas dirigidas, una desde y la otra . Observe que ahora es el doble de grande. Para cada par de aristas dirigidas , defina dos eventos: y , elimina preventivamente y elimina preventivamente , respectivamente. El evento ocurre cuando y , donde es un vecino de y es vecino . Recuerde que a cada nodo se le da un número aleatorio en el mismo rango [0, 1]. En un ejemplo simple con dos nodos disjuntos, cada uno tiene probabilidad de ser el más pequeño. Si hay tres nodos disjuntos, cada uno tiene probabilidad de ser el más pequeño. En el caso de , tiene probabilidad al menos de ser el más pequeño porque es posible que un vecino de también sea vecino de , por lo que un nodo se cuenta dos veces. Usando la misma lógica, el evento también tiene probabilidad al menos de ser eliminado.${\estilo de visualización v}$${\displaystyle {\frac {1}{d(v)+d(w)}}}$${\estilo de visualización (v,w)}$${\estilo de visualización (v,w)}$${\estilo de visualización (w,v)}$${\estilo de visualización |E|}$${\estilo de visualización (v,w)}$${\displaystyle (v\rightarrow w)}$${\displaystyle (w\rightarrow v)}$${\estilo de visualización v}$${\estilo de visualización w}$${\estilo de visualización w}$${\estilo de visualización v}$${\displaystyle (v\rightarrow w)}$${\displaystyle r(v)<r(w)}$${\displaystyle r(v)<r(x)}$${\estilo de visualización w}$${\estilo de visualización v}$${\estilo de visualización x}$${\estilo de visualización w}$${\displaystyle {\frac {1}{2}}}$${\displaystyle {\frac {1}{3}}}$${\estilo de visualización v}$${\displaystyle {\frac {1}{d(v)+d(w)}}}$${\estilo de visualización v}$${\estilo de visualización w}$${\displaystyle (w\rightarrow v)}$${\displaystyle {\frac {1}{d(w)+d(v)}}}$
• Cuando ocurren los eventos y , eliminan y dirigen los bordes salientes, respectivamente. PRUEBA: En el evento , cuando se elimina , también se eliminan todos los nodos vecinos. La cantidad de bordes salientes dirigidos de eliminados es . Con la misma lógica, elimina los bordes salientes dirigidos.${\displaystyle (v\rightarrow w)}$${\displaystyle (w\rightarrow v)}$${\estilo de visualización d(w)}$${\estilo de visualización d(v)}$${\displaystyle (v\rightarrow w)}$${\estilo de visualización v}$${\estilo de visualización w}$${\estilo de visualización w}$${\estilo de visualización d(w)}$${\displaystyle (w\rightarrow v)}$${\estilo de visualización d(v)}$
• En cada iteración del paso 2, en expectativa, se eliminan la mitad de las aristas. PRUEBA: Si el evento ocurre, entonces se eliminan todos los vecinos de; por lo tanto, el número esperado de aristas eliminadas debido a este evento es al menos . Lo mismo es cierto para el evento inverso , es decir, el número esperado de aristas eliminadas es al menos . Por lo tanto, para cada arista no dirigida , el número esperado de aristas eliminadas debido a que uno de estos nodos tiene el valor más pequeño es . Sumando todas las aristas, , da un número esperado de aristas eliminadas en cada paso, pero cada arista se cuenta dos veces (una vez por dirección), lo que da aristas eliminadas en expectativa en cada paso.${\displaystyle (v\rightarrow w)}$${\estilo de visualización w}$${\displaystyle {\frac {d(w)}{d(v)+d(w)}}}$${\displaystyle (w\rightarrow v)}$${\displaystyle {\frac {d(v)}{d(w)+d(v)}}}$${\estilo de visualización (w,v)}$${\displaystyle {\frac {d(w)+d(v)}{d(w)+d(v)}}=1}$${\displaystyle \sum _{{v,w}\in E}1=|E|}$${\estilo de visualización |E|}$${\displaystyle {\frac {|E|}{2}}}$
• Por lo tanto, el tiempo de ejecución esperado del algoritmo es . [ ^8]$Estilo de visualización 3 log _{4/3}(m)+1$${\displaystyle O(\log(n))}$

En lugar de aleatorizar en cada paso, es posible aleatorizar una vez, al comienzo del algoritmo, fijando un orden aleatorio en los nodos. Dado este ordenamiento fijo, el siguiente algoritmo paralelo logra exactamente el mismo MIS que el algoritmo #Sequential (es decir, el resultado es determinista): ^[10]

1. Inicializar I en un conjunto vacío.
2. Mientras V no esté vacío:
   • Sea W el conjunto de vértices en V sin vecinos anteriores (según el ordenamiento fijo);
   • Añade W a I;
   • Eliminar de V los nodos del conjunto W y todos sus vecinos.
3. Regresar I.

Entre los algoritmos totalmente secuenciales y los totalmente paralelos, existe un continuo de algoritmos que son en parte secuenciales y en parte paralelos. Dado un orden fijo en los nodos y un factor δ∈(0,1], el siguiente algoritmo devuelve el mismo MIS:

1. Inicializar I en un conjunto vacío.
2. Mientras V no esté vacío:
   • Seleccione un factor δ∈(0,1].
   • Sea P el conjunto de δ n nodos que están primeros en el ordenamiento fijo.
   • Sea W un MIS en P utilizando el algoritmo totalmente paralelo.
   • Añade W a I;
   • Eliminar de V todos los nodos en el prefijo P, y todos los vecinos de los nodos en el conjunto W.
3. Regresar I.

Al establecer δ=1/ n se obtiene el algoritmo totalmente secuencial; al establecer δ=1 se obtiene el algoritmo totalmente paralelo.

ANÁLISIS : Con una selección adecuada del parámetro δ en el algoritmo parcialmente paralelo, es posible garantizar que finalice después de, como máximo, log(n) llamadas al algoritmo completamente paralelo, y el número de pasos en cada llamada es, como máximo, log(n). Por lo tanto, el tiempo de ejecución total del algoritmo parcialmente paralelo es . Por lo tanto, el tiempo de ejecución del algoritmo completamente paralelo también es, como máximo , . Los principales pasos de la prueba son:${\displaystyle O(\log ^{2}(n))}$${\displaystyle O(\log ^{2}(n))}$

• Si, en el paso i , seleccionamos , donde D es el grado máximo de un nodo en el grafo, entonces WHP todos los nodos restantes después del paso i tienen grado como máximo . Por lo tanto, después de log( D ) pasos, todos los nodos restantes tienen grado 0 (ya que D < n ), y se pueden eliminar en un solo paso.${\displaystyle \delta = 2^{i}\log {(n)}/D}$${\displaystyle D/2^{i}}$
• Si, en cualquier paso, el grado de cada nodo es como máximo d , y seleccionamos (para cualquier constante C ), entonces WHP el camino más largo en el grafo dirigido determinado por el ordenamiento fijo tiene longitud . Por lo tanto, el algoritmo completamente paralelo toma como máximo pasos (ya que el camino más largo es un límite en el peor de los casos para la cantidad de pasos en ese algoritmo).${\displaystyle \delta = C\log {(n)}/d}$${\displaystyle O(\log(n))}$${\displaystyle O(\log(n))}$
• Combinando estos dos hechos obtenemos que, si seleccionamos , entonces WHP el tiempo de ejecución del algoritmo parcialmente paralelo es .${\displaystyle \delta = 2^{i}\log {(n)}/D}$${\displaystyle O(\log(D)\log(n))=O(\log ^{2}(n))}$

Un algoritmo para listar todos los conjuntos independientes máximos o camarillas máximas en un grafo puede usarse como una subrutina para resolver muchos problemas de grafos NP-completos. Obviamente, las soluciones al problema del conjunto independiente máximo, el problema de camarilla máxima y el problema de dominación independiente mínima deben ser todos conjuntos independientes máximos o camarillas máximas, y pueden encontrarse mediante un algoritmo que enumera todos los conjuntos independientes máximos o camarillas máximas y retiene los que tienen el tamaño más grande o más pequeño. De manera similar, la cobertura mínima de vértices puede encontrarse como el complemento de uno de los conjuntos independientes máximos. Lawler (1976) observó que enumerar conjuntos independientes máximos también puede usarse para encontrar 3-coloraciones de grafos: un grafo puede ser 3-coloreado si y solo si el complemento de uno de sus conjuntos independientes máximos es bipartito . Usó este enfoque no solo para 3-coloración sino como parte de un algoritmo de coloración de grafos más general, y otros autores han refinado enfoques similares para la coloración de grafos desde entonces. ^[11] Otros problemas más complejos también pueden modelarse como la búsqueda de un grupo o conjunto independiente de un tipo específico. Esto motiva el problema algorítmico de enumerar todos los conjuntos independientes máximos (o equivalentemente, todos los grupos máximos) de manera eficiente.

Es sencillo convertir una prueba del límite 3 ^{n /3} de Moon y Moser sobre el número de conjuntos independientes máximos en un algoritmo que enumera todos esos conjuntos en tiempo O(3 ^{n /3} ). ^[12] Para grafos que tienen el mayor número posible de conjuntos independientes máximos, este algoritmo toma un tiempo constante por conjunto de salida. Sin embargo, un algoritmo con este límite de tiempo puede ser altamente ineficiente para grafos con números más limitados de conjuntos independientes. Por esta razón, muchos investigadores han estudiado algoritmos que enumeran todos los conjuntos independientes máximos en tiempo polinomial por conjunto de salida. ^[13] El tiempo por conjunto independiente máximo es proporcional al de la multiplicación de matrices en grafos densos, o más rápido en varias clases de grafos dispersos. ^[14]

El problema de conteo asociado a conjuntos independientes máximos ha sido investigado en la teoría de la complejidad computacional . El problema pregunta, dado un grafo no dirigido, cuántos conjuntos independientes máximos contiene. Este problema es #P -hard incluso cuando la entrada está restringida a ser un grafo bipartito . ^[15]

Sin embargo, el problema se puede solucionar en algunas clases específicas de gráficos; por ejemplo, se puede solucionar en cografos . ^[16]

Originalmente se pensó que el problema del conjunto independiente máximo no era trivial de paralelizar debido al hecho de que el conjunto independiente máximo lexicográfico resultó ser P-completo ; sin embargo, se ha demostrado que una solución paralela determinista podría darse mediante una reducción del problema de empaquetamiento de conjuntos máximo o del problema de correspondencia máxima o mediante una reducción del problema de 2-satisfacibilidad . ^{[17] [18]} Normalmente, la estructura del algoritmo dado sigue otros algoritmos de gráficos paralelos, es decir, subdividen el gráfico en problemas locales más pequeños que se pueden resolver en paralelo ejecutando un algoritmo idéntico.${\displaystyle NC^{1}}$$Estilo de visualización NC2$

La investigación inicial sobre el problema del conjunto independiente máximo comenzó con el modelo PRAM y desde entonces se ha ampliado para producir resultados para algoritmos distribuidos en clústeres de computadoras . Los numerosos desafíos que implica diseñar algoritmos paralelos distribuidos se aplican también al problema del conjunto independiente máximo. En particular, encontrar un algoritmo que presente un tiempo de ejecución eficiente y sea óptimo en la comunicación de datos para subdividir el gráfico y fusionar el conjunto independiente.

En 1984, Karp et al. demostraron que una solución paralela determinista en PRAM para el conjunto independiente máximo pertenecía al zoológico de complejidad de la clase de Nick de . ^[19] Es decir, su algoritmo encuentra un conjunto independiente máximo en usando , donde es el tamaño del conjunto de vértices. En el mismo artículo, también se proporcionó una solución paralela aleatoria con un tiempo de ejecución de usando procesadores. Poco después, Luby y Alon et al. mejoraron este resultado de forma independiente, llevando el problema del conjunto independiente máximo al ámbito de con un tiempo de ejecución usando procesadores, donde es el número de aristas en el gráfico. ^{[18] [7] [20]} Para demostrar que su algoritmo está en , presentaron inicialmente un algoritmo aleatorio que usa procesadores pero que podría desaleatorizarse con procesadores adicionales. Hoy en día, sigue siendo una pregunta abierta si el problema del conjunto independiente máximo está en .$Estilo de visualización NC_{4}$$Estilo de visualización O(log ^{4}n)$${\displaystyle O((n/\log n)^{3})}$${\estilo de visualización n}$$Estilo de visualización O(log ^{4}n)$${\displaystyle O(n^{2})}$$Estilo de visualización NC_{2}$${\displaystyle O(\log ^{2}n)}$$Estilo de visualización O(mn^{2})}$${\estilo de visualización m}$$Estilo de visualización NC_{2}$${\displaystyle O(m)}$${\displaystyle O(n^{2})}$$Estilo de visualización NC_{1}$

Los algoritmos distribuidos de conjuntos independientes máximos están fuertemente influenciados por algoritmos en el modelo PRAM. El trabajo original de Luby y Alon et al. ha dado lugar a varios algoritmos distribuidos. ^{[21] [22] [23] [20]} En términos de intercambio de bits, estos algoritmos tenían un límite inferior de tamaño de mensaje por ronda de bits y requerirían características adicionales del gráfico. Por ejemplo, sería necesario conocer el tamaño del gráfico o se podría consultar el grado máximo de vértices vecinos para un vértice dado. En 2010, Métivier et al. redujeron el tamaño de mensaje requerido por ronda a , que es óptimo y eliminó la necesidad de cualquier conocimiento adicional del gráfico. ^[24]${\displaystyle O(\log n)}$${\estilo de visualización O(1)}$