Certificación local de clases de grafos definidos por ciclos prohibidos: caso menores y caso inducido

Abstract

Esta investigación se centra en la certificación local de clases de grafos. Un algoritmo de certificación local de grafos consta de dos etapas. En la primera etapa, un probador externo entrega a cada nodo un mensaje llamado certificado. Luego, cada vértice ejecuta un algoritmo local utilizando este certificado y los certificados que pueda recopilar de sus vecinos. Si el grafo pertenece a la clase, debe existir una asignación de certificados tal que todos los nodos acepten. Si el grafo no pertenece a la clase, para cualquier asignación de certificados, debe haber al menos un nodo que rechace.

El objetivo en este tipo de problemas es minimizar el tamaño de los certificados asignados. El gold standard en la certificación local es utilizar certificados de tamaño O(log n) bits, donde n es la cantidad de vértices del grafo.

En particular, estamos interesados en certificar las clases de grafos definidas por sus menores prohibidos. Ejemplos clásicos de estas clases son los grafos planares (aquellos sin K_5 y K_{3,3} como menor) y los grafos plano exteriores (aquellos sin K_4 y K_{2,3} como menor).

Se sabe por un resultado del año 2021, que, para cualquier grafo H es posible certificar localmente un grafo sin H como menor utilizando O(log n) bits, siempre y cuando H tenga a lo más 4 vértices. Este resultado también se mantiene para algunos grafos de 5 vértices, en particular para los ciclos de longitud 5.\\

En esta tesis, estudiamos la certificación de la clase formada por todos aquellos grafos que no tienen como menores a ciclos de largo mayor o igual 6, diseñando un algoritmo de certificación utilizando técnicas previamente desarrolladas en el área.

Dentro del contexto de ciclos inducidos prohibidos, consideramos los grafos cordales, que son aquellos que no tienen ciclos inducidos de longitud mayor a 3. Se sabe que estos grafos pueden certificarse con O(log n) bits.

Extendemos este problema a la certificación de grafos k-cordales, definidos como aquellos sin ciclos inducidos de longitud mayor a k. En esta investigación, presentamos un algoritmo de certificación que utiliza O(n log n) bits para una subclase de grafos 4-cordales. Esta subclase está caracterizada por una construcción en orejas, similar a la descomposición de orejas clásica de los grafos 2-conexos.