Conjunto independiente máximo

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

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

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

1. Inicializa I como 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 de forma independiente con una probabilidad de 1/(2d(v)), donde d es el grado de v (el número de vecinos de v).
   • Para cada arista en E, si ambos extremos pertenecen al conjunto aleatorio S, se elimina de S el extremo cuyo grado sea menor (es decir, que tenga menos vecinos). Los empates se resuelven arbitrariamente, por ejemplo, utilizando un orden lexicográfico en los nombres de los vértices.
   • Añade el conjunto S a I.
   • Eliminar de V el conjunto S y todos los vecinos de los nodos en S.
3. Regreso I.

ANÁLISIS : Para cada nodo v, divida 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), resolviendo los empates como en el algoritmo.

Un nodo se considera malo si más de 2/3 de sus vecinos son vecinos superiores. Una arista se considera mala si ambos extremos son malos; de lo contrario, la arista es buena .

• Al menos la mitad de todas las aristas son siempre buenas. PRUEBA: Construimos una versión dirigida de G dirigiendo cada arista al nodo con el grado más alto (resolviendo los empates arbitrariamente). Así, para cada nodo malo, el número de aristas salientes es más del doble del número de aristas entrantes. Por lo tanto, cada arista mala que entra en un nodo v puede emparejarse con un conjunto distinto de dos aristas que salen del nodo v. En consecuencia, el número total de aristas es al menos el doble del número 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 seleccionado 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 el límite de la unión, la probabilidad de que ningún vecino superior sea seleccionado 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 constante positiva. En consecuencia, la probabilidad de que u sea eliminado, en cada paso, es al menos una constante positiva.
• Por lo tanto, para cada arista válida e, la probabilidad de que e sea eliminada en cada paso es al menos una constante positiva. Así, el número de aristas válidas disminuye al menos en un factor constante en cada paso.
• Dado que al menos la mitad de las aristas son buenas, el número total de aristas 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á acotado por${\displaystyle O(\log(n))}$.

Un gráfico del peor caso, en el que el número promedio de pasos es${\displaystyle \Theta (\log(n))}$es un grafo formado por n /2 componentes conexas, cada una 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 ambos nodos de una 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 \log _{4}(n)}$.

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

1. Inicializa I como un conjunto vacío.
2. Mientras V no esté vacío, cada nodo v realiza 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 comunica a sus vecinos;
   • Si v se entera de que uno de sus vecinos entró en I, entonces v se retira de V.
3. Regreso I.

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

ANÁLISIS :

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

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

1. Inicializa I como un conjunto vacío.
2. Mientras V no esté vacío:
   • Sea W el conjunto de vértices en V que no tienen vecinos anteriores (según el orden fijo);
   • Suma W a I;
   • Elimina de V los nodos del conjunto W y todos sus vecinos.
3. Regreso I.

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

1. Inicializa I como un conjunto vacío.
2. Mientras V no esté vacío:
   • Seleccione un factor δ∈(0,1].
   • Sea P el conjunto de δ n nodos que son los primeros en el orden fijo.
   • Sea W un MIS en P que utiliza el algoritmo totalmente paralelo.
   • Suma W a I;
   • Elimina de V todos los nodos del prefijo P y todos los vecinos de los nodos del conjunto W.
3. Regreso I.

Si se establece δ=1/ n , se obtiene el algoritmo totalmente secuencial ; si se establece δ=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 totalmente paralelo, y el número de pasos en cada llamada es como máximo log(n). Por lo tanto, el tiempo total de ejecución del algoritmo parcialmente paralelo es${\displaystyle O(\log ^{2}(n))}$Por lo tanto, el tiempo de ejecución del algoritmo totalmente paralelo también es como máximo${\displaystyle O(\log ^{2}(n))}$Los pasos principales de la demostración son:

• Si, en el paso i , seleccionamos${\displaystyle \delta =2^{i}\log {(n)}/D}$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${\displaystyle D/2^{i}}$. Por lo tanto, después de log( D ) pasos, todos los nodos restantes tienen grado 0 (ya que D < n ), y pueden eliminarse en un solo paso.
• Si, en cualquier paso, el grado de cada nodo es como máximo d , y seleccionamos${\displaystyle \delta =C\log {(n)}/d}$(para cualquier constante C ), entonces WHP el camino más largo en el grafo dirigido determinado por el orden fijo tiene longitud${\displaystyle O(\log(n))}$Por lo tanto, el algoritmo totalmente paralelo toma como máximo${\displaystyle O(\log(n))}$pasos (ya que el camino más largo es un límite en el peor de los casos para el número de pasos en ese algoritmo).
• La combinación de estos dos hechos nos da que, si seleccionamos${\displaystyle \delta =2^{i}\log {(n)}/D}$, entonces WHP el tiempo de ejecución del algoritmo parcialmente paralelo es${\displaystyle O(\log(D)\log(n))=O(\log ^{2}(n))}$.

El problema del conjunto independiente máximo se consideró originalmente no trivial de paralelizar debido a 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 ser dada por un${\displaystyle NC^{1}}$reducción ya sea del problema de empaquetamiento de conjuntos máximos o del problema de emparejamiento máximo o por un${\displaystyle NC^{2}}$reducción del problema de 2-satisfacibilidad . ^{[ 17 ] [ 18 ]} Por lo general, la estructura del algoritmo dado sigue otros algoritmos de grafos paralelos, es decir, subdividen el grafo en problemas locales más pequeños que se pueden resolver en paralelo ejecutando un algoritmo idéntico.

La investigación inicial sobre el problema del conjunto independiente máximo se basó en el modelo PRAM y, posteriormente, se amplió para generar resultados sobre algoritmos distribuidos en clústeres de computadoras . Los numerosos desafíos del diseño de algoritmos paralelos distribuidos también se aplican al problema del conjunto independiente máximo. En particular, se trata de encontrar un algoritmo que presente un tiempo de ejecución eficiente y sea óptimo en la comunicación de datos para subdividir el grafo 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 clases de Nick .${\displaystyle NC_{4}}$. ^{[ 19 ]} Es decir, su algoritmo encuentra un conjunto independiente maximal en${\displaystyle O(\log ^{4}n)}$usando${\displaystyle O((n/\log n)^{3})}$, dónde${\displaystyle n}$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${\displaystyle O(\log ^{4}n)}$usando${\displaystyle O(n^{2})}$procesadores. Poco después, Luby y Alon et al. mejoraron independientemente este resultado, llevando el problema del conjunto independiente máximo al ámbito de${\displaystyle NC_{2}}$con un${\displaystyle O(\log ^{2}n)}$tiempo de ejecución usando${\displaystyle O(mn^{2})}$procesadores, donde${\displaystyle m}$es el número de aristas en el grafo. ^{[ 18 ] [ 7 ] [ 20 ]} Para demostrar que su algoritmo está en${\displaystyle NC_{2}}$, inicialmente presentaron un algoritmo aleatorio que utiliza${\displaystyle O(m)}$procesadores pero podría desaleatorizarse con un adicional${\displaystyle O(n^{2})}$procesadores. Hoy en día, sigue siendo una cuestión abierta si el problema del conjunto independiente máximo está en${\displaystyle NC_{1}}$.

Los algoritmos distribuidos de conjunto independiente máximo están fuertemente influenciados por los algoritmos del 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 del tamaño del mensaje por ronda de${\displaystyle O(\log n)}$bits y requeriría características adicionales del grafo. Por ejemplo, sería necesario conocer el tamaño del grafo o consultar el grado máximo de los vértices vecinos para un vértice dado. En 2010, Métivier et al. redujeron el tamaño de mensaje requerido por ronda a${\displaystyle O(1)}$, lo cual es óptimo y eliminó la necesidad de cualquier conocimiento adicional sobre grafos. ^{[ 24 ]}