El problema de la degenerancia de grafos en Congested Clique

Abstract

La computación distribuida, rama de las ciencias de la computación, se focaliza en estu- diar sistemas distribuidos, tales como internet, redes sociales o protocolos de mensajería. La información se encuentra distribuida entre las distintas entidades que conforman el sistema y el objetivo último es resolver algún problema global. Para ello las distintas entidades se comunican mediante los canales de la red hasta que encuentran la solución. Esta memoria comienza estudiando el problema de la degenerancia de un grafo en los modelos de computación distribuida UCAST y BCAST, donde la degenerancia de un grafo G se define como el máximo grado mínimo de un subgrafo F de G. Los modelos distribuidos UCAST y BCAST corresponden a redes completas de n individuos, los cuales se comunican de manera síncrona por los canales de la red en rondas. En el primer caso, cada individuo por ronda puede enviar diferentes mensajes por cada uno de sus canales. En el segundo caso, cada individuo por ronda envía a través de sus canales el mismo mensaje. En general, se suele decir que BCAST es una restricción de UCAST. Primero, se construye un protocolo aleatorio en el modelo UCAST que calcula una (1 + ε)- aproximación de la degenerancia en O(log n) rondas con mensajes de largo O(log n). En el modelo BCAST se demuestra que el problema de calcular la degenerancia es difícil en 1 ronda. Más específicamente, se demuestra que todo protocolo aleatorio de 1 ronda que calcule exactamente la degenerancia debe enviar un mensaje de largo Ω(n). En el mismo modelo, se construye un protocolo aleatorio de 2 rondas con mensajes de largo O(log 2 n) que calcula una (1 + ε)-aproximación de la degenerancia para grafos α-densos. Finalmente, se construye un protocolo determinista que calcula una (2 + ε)-aproximación de la degenerancia en O(log n) rondas con mensajes de largo O(log n). Como segunda parte de este trabajo, y motivado por el protocolo en BCAST que calcula una (2 + ε)-aproximación de la degenerancia, se estudia la siguiente dinámica sobre grafos: Durante cada iteración, eliminar todos los vértices que tengan grado a lo más el grado prome- dio del grafo +1. Se conjetura que para todo grafo G de n vértices la dinámica toma O(log n) iteraciones en vaciar el grafo. Se aborda el problema estudiando clases de grafos tales como: bosques, grafos planares, grafos con degenerancia acotada y grafos unión disjunta de cliques. Finalmente, se estudian diversos problemas en el modelo BCAST. Se comienza estudiando el problema de calcular el conjunto independiente maximal con un vértice fijo. Se prueba que el problema es difícil en 1 ronda y luego se contruye un protocolo que en O(log n) rondas, usando mensaje de largo O(log n), calcula el conjunto independiente. Se estudia también el problema de calcular el número cromático de un grafo. Se prueba que el problema resulta difícil en 1 ronda. Concluyendo el capítulo, se estudian los problemas de encontrar conjuntos dominantes de tamaño k y conjuntos -dominantes de tamaño k, en ambos casos se demuestra que los problemas son difíciles en 1 ronda.