Conjunto independiente maximo

Conjunto independiente que no es un subconjunto de ningún otro conjunto independiente

El gráfico del cubo tiene seis conjuntos independientes diferentes (dos de ellos son máximos), mostrados como vértices rojos.

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 .

Los dos gráficos P ₃ superiores son conjuntos independientes máximos, mientras que los dos inferiores son conjuntos independientes, pero no máximos. El conjunto independiente máximo está representado por la parte superior izquierda.

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 .

Dos conjuntos independientes para el gráfico de estrellas S ₈ muestran cuán diferentes en tamaño pueden ser dos conjuntos independientes máximos (siendo el de la derecha el máximo).

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.

Definición

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)}$ ${\displaystyle S}$ ${\displaystyle v\in V}$

1. ${\displaystyle v\in S}$
2. ${\displaystyle N(v)\cap S\neq \emptyset }$donde denota los vecinos de ${\displaystyle N(v)}$ ${\displaystyle 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 ${\displaystyle S}$ ${\displaystyle 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. ${\displaystyle S}$ ${\displaystyle S}$

Conjuntos de vértices relacionados

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.

A la izquierda se encuentra un conjunto independiente máximo. En el medio hay una camarilla, , en el complemento del grafo. A la derecha hay una cubierta de vértices en el complemento del conjunto independiente máximo. ${\displaystyle K_{3}}$

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.

Caracterización de familias de grafos

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.

Limitar el número de conjuntos

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 .

Encontrar un único conjunto independiente máximo

Algoritmo secuencial

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.

Algoritmo paralelo de selección aleatoria [Algoritmo de Luby]

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)}$

Algoritmo paralelo de prioridad aleatoria

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. ${\displaystyle v}$ ${\displaystyle {\frac {1}{d(v)+d(w)}}}$ ${\displaystyle (v,w)}$ ${\displaystyle (v,w)}$ ${\displaystyle (w,v)}$ ${\displaystyle |E|}$ ${\displaystyle (v,w)}$ ${\displaystyle (v\rightarrow w)}$ ${\displaystyle (w\rightarrow v)}$ ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle w}$ ${\displaystyle v}$ ${\displaystyle (v\rightarrow w)}$ ${\displaystyle r(v)<r(w)}$ ${\displaystyle r(v)<r(x)}$ ${\displaystyle w}$ ${\displaystyle v}$ ${\displaystyle x}$ ${\displaystyle w}$ ${\displaystyle {\frac {1}{2}}}$ ${\displaystyle {\frac {1}{3}}}$ ${\displaystyle v}$ ${\displaystyle {\frac {1}{d(v)+d(w)}}}$ ${\displaystyle v}$ ${\displaystyle 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)}$ ${\displaystyle d(w)}$ ${\displaystyle d(v)}$ ${\displaystyle (v\rightarrow w)}$ ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle w}$ ${\displaystyle d(w)}$ ${\displaystyle (w\rightarrow v)}$ ${\displaystyle 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)}$ ${\displaystyle w}$ ${\displaystyle {\frac {d(w)}{d(v)+d(w)}}}$ ${\displaystyle (w\rightarrow v)}$ ${\displaystyle {\frac {d(v)}{d(w)+d(v)}}}$ ${\displaystyle (w,v)}$ ${\displaystyle {\frac {d(w)+d(v)}{d(w)+d(v)}}=1}$ ${\displaystyle \sum _{{v,w}\in E}1=|E|}$ ${\displaystyle |E|}$ ${\displaystyle {\frac {|E|}{2}}}$
• Por lo tanto, el tiempo de ejecución esperado del algoritmo es . [ ^8] ${\displaystyle 3\log _{4/3}(m)+1}$ ${\displaystyle O(\log(n))}$

Algoritmo paralelo de permutación aleatoria [Algoritmo de Blelloch]

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))}$

Listado de todos los conjuntos independientes máximos

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]

Contando conjuntos independientes máximos

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]

Paralelización de la búsqueda de conjuntos independientes máximos

Historia

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}}$ ${\displaystyle NC^{2}}$

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.

Clase de complejidad

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 . ${\displaystyle NC_{4}}$ ${\displaystyle O(\log ^{4}n)}$ ${\displaystyle O((n/\log n)^{3})}$ ${\displaystyle n}$ ${\displaystyle O(\log ^{4}n)}$ ${\displaystyle O(n^{2})}$ ${\displaystyle NC_{2}}$ ${\displaystyle O(\log ^{2}n)}$ ${\displaystyle O(mn^{2})}$ ${\displaystyle m}$ ${\displaystyle NC_{2}}$ ${\displaystyle O(m)}$ ${\displaystyle O(n^{2})}$ ${\displaystyle NC_{1}}$

Comunicación e intercambio de datos

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)}$ ${\displaystyle O(1)}$

Notas al pie

1. Erdős (1966) muestra que la cantidad de tamaños diferentes de MIS en un gráfico de n vértices puede ser tan grande como n – log n – O (log log n ) y nunca es mayor que n – log n .

Notas

1. Algoritmo de Luby, en: Notas de clase sobre algoritmos aleatorios, última actualización por Eric Vigoda el 2 de febrero de 2006
2. Weigt y Hartmann (2001).
3. Sistema de información sobre inclusiones de clases de grafos: grafos irreducibles de clique maximal Archivado 2007-07-09 en Wayback Machine y grafos irreducibles de clique maximal hereditarios Archivado 2007-07-08 en Wayback Machine .
4. Byskov (2003). Para resultados anteriores relacionados, véase Croitoru (1979) y Eppstein (2003).
5. Chiba y Nishizeki (1985). Chiba y Nishizeki expresan la condición de tener O( n ) aristas de manera equivalente, en términos de que la arboricidad de los grafos de la familia sea constante.
6. Bisdorff y Marichal (2008); Euler (2005); Furedi (1987).
7. Luby, M. (1986). "Un algoritmo paralelo simple para el problema del conjunto independiente máximo". Revista SIAM de informática . 15 (4): 1036–1053. CiteSeerX  10.1.1.225.5475 . doi :10.1137/0215074.
8. "Principios de computación distribuida (lectura 7)" (PDF) . ETH Zurich. Archivado desde el original (PDF) el 21 de febrero de 2015 . Consultado el 21 de febrero de 2015 .
9. Métivier, Y.; Robson, JM; Saheb-Djahromi, N.; Zemmari, A. (2010). "Un algoritmo MIS distribuido aleatorio de complejidad de bits óptima". Computación distribuida . 23 (5–6): 331. doi :10.1007/s00446-010-0121-5. S2CID  36720853.
10. Blelloch, Guy; Fineman, Jeremy; Shun, Julian (2012). "El conjunto independiente secuencial maximal voraz y el emparejamiento son paralelos en promedio". arXiv : 1202.3205 [cs.DS].
11. Eppstein (2003); Byskov (2003).
12. Eppstein (2003). Para un límite de coincidencia para el algoritmo Bron-Kerbosch ampliamente utilizado , véase Tomita, Tanaka y Takahashi (2006).
13. Bomze y col. (1999); Eppstein (2005); Jennings y Motycková (1992); Johnson, Yannakakis y Papadimitriou (1988); Lawler, Lenstra y Rinnooy Kan (1980); Liang, Dhall y Lakshmivarahan (1991); Makino y Uno (2004); Mishra y Pitt (1997); Stix (2004); Tsukiyama et al. (1977); Yu y Chen (1993).
14. Makino y Uno (2004); Epstein (2005).
15. Provan, J. Scott; Ball, Michael O. (noviembre de 1983). "La complejidad de contar cortes y de calcular la probabilidad de que un gráfico esté conectado". Revista SIAM de informática . 12 (4): 777–788. doi :10.1137/0212053. ISSN  0097-5397.
16. Corneil, DG; Lerchs, H.; Burlingham, L. Stewart (1 de julio de 1981). "Gráficos reducibles en complemento". Matemáticas Aplicadas Discretas . 3 (3): 163–174. doi :10.1016/0166-218X(81)90013-5. ISSN  0166-218X.
17. Cook, Stephen (junio de 1983). "Una visión general de la complejidad computacional". Commun. ACM . 26 (6): 400–408. doi : 10.1145/358141.358144 . S2CID  14323396.
18. Barba, Luis (octubre de 2012). "REVISIÓN DE LA LITERATURA: Algoritmos paralelos para el problema de conjuntos independientes maximalistas en grafos" (PDF) .
19. Karp, RM; Wigderson, A. (1984). "Un algoritmo paralelo rápido para el problema de conjuntos independientes máximos". Proc. 16.º Simposio ACM sobre teoría de la computación .
20. Alon, Noga; Laszlo, Babai; Alon, Itai (1986). "Un algoritmo paralelo aleatorio rápido y simple para el problema de conjuntos independientes máximos". Journal of Algorithms . 7 (4): 567–583. doi :10.1016/0196-6774(86)90019-2.
21. Peleg, David (2000). Computación distribuida: un enfoque sensible a la localidad . doi :10.1137/1.9780898719772. ISBN 978-0-89871-464-7.
22. Lynch, NA (1996). "Algoritmos distribuidos". Morgan Kaufmann .
23. Wattenhofer, R. "Capítulo 4: Conjunto independiente máximo" (PDF) .
24. Métivier, Y.; Robson, JM; Saheb-Djahromi, N.; Zemmari, A. (2010). "Un algoritmo MIS distribuido aleatorio de complejidad de bits óptima". Computación distribuida .

Referencias

• Bisdorff, Raymond; Marichal, Jean-Luc (2008), "Contando conjuntos independientes máximos no isomorfos del gráfico de n ciclos", Journal of Integer Sequences , 11 : 08.5.7, arXiv : math.CO/0701647.
• Bomze, IM; Budinich, M.; Pardalos, PM; Pelillo, M. (1999), "El problema de la camarilla máxima", Handbook of Combinatorial Optimization , vol. 4, Kluwer Academic Publishers, págs. 1–74, CiteSeerX  10.1.1.48.4074.
• Byskov, JM (2003), "Algoritmos para la coloración k y la búsqueda de conjuntos independientes máximos", Actas del decimocuarto simposio anual ACM-SIAM sobre algoritmos discretos, Soda '03, págs. 456–457, ISBN 9780898715385.
• Chiba, N.; Nishizeki, T. (1985), "Algoritmos de arboricidad y listado de subgrafos", SIAM Journal on Computing , 14 (1): 210–223, doi :10.1137/0214017, S2CID  207051803.
• Croitoru, C. (1979), "Sobre establos en gráficos", Proc. Tercer Col. Investigación de operaciones , Universidad Babeş-Bolyai , Cluj-Napoca, Rumania, págs. 55–60.
• Eppstein, D. (2003), "Conjuntos independientes máximos pequeños y coloración de gráficos exacta y más rápida" (PDF) , Journal of Graph Algorithms and Applications , 7 (2): 131–140, arXiv : cs.DS/0011009 , CiteSeerX  10.1.1.342.4049 , doi :10.7155/jgaa.00064.
• Eppstein, D. (2005), "Todos los conjuntos independientes máximos y dominancia dinámica para grafos dispersos", Proc. Decimosexto Simposio Anual ACM-SIAM sobre Algoritmos Discretos , vol. 5, págs. 451–459, arXiv : cs.DS/0407036 , doi :10.1145/1597036.1597042, S2CID  2769046.
• Erdős, P. (1966), "Sobre camarillas en grafos", Israel Journal of Mathematics , 4 (4): 233–234, doi : 10.1007/BF02771637 , MR  0205874, S2CID  121993028.
• Euler, R. (2005), "El número de Fibonacci de un gráfico de cuadrícula y una nueva clase de secuencias de números enteros", Journal of Integer Sequences , 8 (2): 05.2.6, Bibcode :2005JIntS...8...26E.
• Füredi, Z. (1987), "El número de conjuntos independientes máximos en grafos conexos", Journal of Graph Theory , 11 (4): 463–470, doi :10.1002/jgt.3190110403.
• Jennings, E.; Motycková, L. (1992), "Un algoritmo distribuido para encontrar todos los grupos máximos en un grafo de red", Proc. Primer Simposio Latinoamericano de Informática Teórica , Lecture Notes in Computer Science, vol. 583, Springer-Verlag, págs. 281–293
• Johnson, DS ; Yannakakis, M. ; Papadimitriou, CH (1988), "Sobre la generación de todos los conjuntos independientes máximos", Information Processing Letters , 27 (3): 119–123, doi :10.1016/0020-0190(88)90065-8.
• Lawler, EL (1976), "Una nota sobre la complejidad del problema del número cromático", Information Processing Letters , 5 (3): 66–67, doi :10.1016/0020-0190(76)90065-X.
• Lawler, EL ; Lenstra, JK ; Rinnooy Kan, AHG (1980), "Generación de todos los conjuntos independientes máximos: algoritmos de tiempo polinomial y de dureza NP" (PDF) , SIAM Journal on Computing , 9 (3): 558–565, doi :10.1137/0209042, S2CID  29527771.
• Leung, JY-T. (1984), "Algoritmos rápidos para generar todos los conjuntos independientes máximos de grafos de intervalo, arco circular y cordales", Journal of Algorithms , 5 : 22–35, doi :10.1016/0196-6774(84)90037-3.
• Liang, YD; Dhall, SK; Lakshmivarahan, S. (1991), "Sobre el problema de encontrar todos los conjuntos independientes de peso máximo en gráficos de intervalos y arcos circulares", Actas del Simposio de 1991 sobre Computación Aplicada , págs. 465–470, doi :10.1109/SOAC.1991.143921, ISBN 0-8186-2136-2, Identificador único  122685841
• Makino, K.; Uno, T. (2004), "Nuevos algoritmos para enumerar todas las camarillas máximas", Proc. Ninth Scandinavian Workshop on Algorithm Theory , Lecture Notes in Computer Science, vol. 3111, Springer-Verlag, págs. 260–272, CiteSeerX  10.1.1.138.705 , doi :10.1007/978-3-540-27810-8_23, ISBN 978-3-540-22339-9. ISBN 9783540223399 , 9783540278108 . 
• Mishra, N.; Pitt, L. (1997), "Generación de todos los conjuntos independientes máximos de hipergrafos de grado acotado", Proc. Décima Conferencia sobre Teoría del Aprendizaje Computacional , págs. 211–217, doi :10.1145/267460.267500, ISBN 978-0-89791-891-6, Número de identificación del sujeto  5254186.
• Moon, JW; Moser, L. (1965), "Sobre camarillas en grafos", Israel Journal of Mathematics , 3 : 23–28, doi : 10.1007/BF02760024 , MR  0182577, S2CID  9855414.
• Stix, V. (2004), "Encontrar todas las camarillas máximas en gráficos dinámicos", Optimización computacional y aplicaciones , 27 (2): 173–186, CiteSeerX  10.1.1.497.6424 , doi :10.1023/B:COAP.0000008651.28952.b6, S2CID  17824282
• Tomita, E.; Tanaka, A.; Takahashi, H. (2006), "La complejidad temporal del peor caso para generar todas las camarillas máximas y experimentos computacionales", Theoretical Computer Science , 363 (1): 28–42, doi : 10.1016/j.tcs.2006.06.015.
• Tsukiyama, S.; Ide, M.; Ariyoshi, H.; Shirakawa, I. (1977), "Un nuevo algoritmo para generar todos los conjuntos independientes máximos", SIAM Journal on Computing , 6 (3): 505–517, doi :10.1137/0206036.
• Weigt, Martin; Hartmann, Alexander K. (2001), "Coberturas de vértices mínimas en grafos aleatorios de conectividad finita: una imagen de gas reticular de esferas duras", Phys. Rev. E , 63 (5): 056127, arXiv : cond-mat/0011446 , Bibcode :2001PhRvE..63e6127W, doi :10.1103/PhysRevE.63.056127, PMID  11414981, S2CID  16773685.
• Yu, C.-W.; Chen, G.-H. (1993), "Generar todos los conjuntos independientes máximos en gráficos de permutación", Internat. J. Comput. Math. , 47 (1–2): 1–8, doi :10.1080/00207169308804157.