Detección de clases de grafos en el modelo interactivo de verificación distribuida

Abstract

En este trabajo se estudia el modelo interactivo de verificación distribuida. En este modelo hay dos entidades: un probador con poder ilimitado, identificado como Merlín, y un verificador distribuido identificado como Arturo, que corresponde a una red de comunicación representada por un grafo conexo G. Cada nodo del grafo interactúa con Merlín en una serie de interacciones en las que lanza monedas y recibe una respuesta de éste que puede depender de la topología de la red, así como de las interacciones pasadas. El objetivo de estas interacciones es convencer con buena probabilidad a los nodos de que la topología de la red satisface algún predicado. Luego del último mensaje enviado por Merlín, sigue una ronda de verificación entre cada nodo y sus vecinos. Se dirá que las interacciones son de tipo Arturo-Merlín (dAM) o Merlín-Arturo (dMA) dependiendo de si la ronda de verificación es determinista o aleatorizada, donde en el segundo caso los nodos realizan un nuevo lanzamiento de monedas previo al intercambio de mensajes.

El primer capítulo se centra en definir este modelo y sus variantes, además de presentar el marco teórico de este trabajo. En el segundo capítulo se describe el diseño de protocolos usando sólo una ronda de interacción para distintas clases de grafos. De aquí se desprenden protocolos eficientes para problemas como la detección de grafos de intervalos, grafos cordales, grafos de arcos circulares, entre otros. En el tercer capítulo, se continúa presentando protocolos interactivos, pero permitiendo múltiples rondas de interacción. Aquí se estudian problemas como la presencia de una cierta estructura como subgrafo o menor, para luego ver el caso de la ausencia de estructuras. Se desprenden protocolos para clases tales como cografos, grafos de distancia hereditaria y grafos libres de triángulos.

En el cuarto capítulo se deja de lado el diseño de protocolos para estudiar la construcción de cotas inferiores: mediante distintas técnicas se obtienen cotas inferiores para el cálculo de la degenerancia y la detección de cografos. Luego, se presenta una técnica general para obtener cotas inferiores basada en el pegado de soluciones correctas de forma de engañar a la red. Se obtienen cotas para una ronda y para múltiples rondas de interacción en que la aleatoriedad es compartida entre los nodos. De aquí se desprende que los resultados obtenidos para varios de los problemas anteriores son ajustados. Por último, se extiende un resultado previo sobre el problema de Simetría que consiste en decidir si un grafo admite un automorfismo no trivial. De aquí se obtiene una cota inferior en múltiples rondas de interacción cuando la fuente de aleatoriedad es privada para cada nodo.

Finalmente, en el quinto capítulo, se estudian los efectos sobre el modelo al cambiar la fuente de aleatoriedad, comparando el caso en que ésta es "compartida" entre los nodos de la red y el caso en que es "privada". Se obtiene que hay diferencias en el poder del modelo dependiendo de si la última interacción le corresponde a Merlín o Arturo. Si ésta es de tipo dAM se tiene que el modelo a moneda privada admite protocolos con un costo asintóticamente más pequeño que el segundo, aún para múltiples rondas de interacción. Por otro lado, si Arturo es el último en interactuar, el uso de moneda compartida permite una mejora sustancial en el largo de los mensajes por sobre aquellos con moneda privada.