Is star complexity a proxy for information based complexity of graphs?

Resumen Técnico: La Complejidad de Estrella como Proxy de la Complejidad Basada en la Información de los Grafos

Planteamiento del Problema
El artículo investiga si la "complejidad de estrella", una medida estructural de los grafos, sirve como un proxy práctico para la "Complejidad Basada en la Información" (IBC, por sus siglas en inglés). La IBC es una medida de complejidad formal definida por la proporción de descripciones en un lenguaje específico que mapean a un objeto dado mediante un clasificador. Si bien la IBC teórica (basada en máquinas de Turing universales) es asintóticamente independiente del lenguaje de codificación, el artículo plantea la hipótesis de que las medidas de IBC prácticas derivadas de diferentes esquemas de codificación también serán asintóticamente equivalentes. Específicamente, el estudio compara una medida de IBC de grafos estándar ($C$), que codifica grafos mediante listas de adyacencia y los clasifica por automorfismo, contra la complejidad de estrella, que define la complejidad basándose en el número mínimo de operaciones de unión e intersección de "estrellas" elementales necesarias para construir un grafo.

Metodología
La investigación emplea un enfoque empírico comparativo utilizando dos medidas de complejidad distintas:

1. Complejidad de Grafo ($C$): Calculada mediante la fórmula $C(x) = \ell - \log_2 \omega(x)$, donde $\ell$ es la longitud de la codificación de la lista de adyacencia y $\omega$ es el número de cadenas de esa longitud que mapean al mismo grafo (determinado mediante algoritmos de automorfismo de grafos usando la librería Nauty).
2. Complejidad de Estrella ($Star(G)$): Definida como el número mínimo de operaciones de conjuntos (unión/intersección) de estrellas elementales (un vértice central conectado a todos los demás) necesarias para generar un grafo.
3. IBC Basada en Estrellas ($C^*$): Una medida de IBC derivada específicamente de la complejidad de estrella. Codifica el grafo almacenando el número de vértices, el número de estrellas y una "receta" de Notación Polaca Inversa (RPN) de operaciones. $C^*$ ajusta la longitud de bits de esta receta restando $\log_2 \omega$, donde $\omega$ representa el número de recetas equivalentes para un grafo dado.
4. Estimación del Límite Superior ($\overline{Star}(G)$): Dado que calcular el $Star(G)$ exacto requiere una búsqueda exhaustiva de todas las secuencias posibles de operaciones (lo cual es computacionalmente inviable para grafos grandes), los autores introducen un límite superior algorítmico. Este algoritmo construye un grafo cubriendo los vértices de grado máximo con estrellas y cubriendo los bordes restantes mediante intersecciones por pares, luego optimiza la expresión mediante asociatividad de conjuntos.

Ejecución Experimental
El estudio utilizó el paquete EcoLab, optimizado para ejecución en GPU (Intel Xe graphics) para lograr una aceleración de 23x respecto al procesamiento de CPU de un solo hilo. Los experimentos consistieron en:

• Búsqueda Exhaustiva a Pequeña Escala: Generación de todos los grafos con 10 y 22 vértices que tienen una complejidad de estrella de 8 o menos. Esto permitió el cálculo exacto de $C$, $Star(G)$y$C^*$, incluyendo la enumeración de recetas equivalentes ($\omega$).
• Muestreo a Gran Escala: Generación de 1,000 grafos aleatorios de Erdős-Rényi con 1,000 vértices para probar la relación entre el límite superior fácilmente computable $\overline{Star}(G)$ y la complejidad estándar $C$.

Resultos Clave

• Grafos Pequeños (10 y 22 vértices): Se encontró que la correlación entre la complejidad estándar $C$ y la complejidad de estrella bruta $Star(G)$ era insignificante (coeficientes de correlación $\rho \approx 0.08$ y $-0.04$, respectivamente). Del mismo modo, la correlación entre $C$ y la IBC derivada de estrellas $C^*$ fue débil ($\rho \approx 0.14$ y cercana a cero).
• Correlación de Medidas: Sin embargo, $Star(G)$y$C^*$ mostraron una correlación positiva moderada ($\rho \approx 0.6$), y el límite superior estimado $\overline{Star}(G)$ mostró una fuerte correlación con el $Star(G)$ exacto ($\rho \approx 0.85$).
• Grafos Grandes (1,000 vértices): El hallazgo más significativo surgió del muestreo a gran escala. Se observó una relación fuerte, aunque no lineal, entre el límite superior computable $\overline{Star}(G)$ y la complejidad basada en la información $C$.

Significancia y Reivindicaciones
El artículo concluye que, si bien la complejidad de estrella bruta no se correlaciona linealmente con la complejidad basada en la información en conjuntos de datos exhaustivos pequeños, es probable que ambas medidas estén midiendo la misma propiedad subyacente para grafos más grandes. La fuerte relación empírica entre el límite superior fácilmente computable de la complejidad de estrella ($\overline{Star}(G)$) y la medida de IBC estándar ($C$) sugiere que la complejidad de estrella actúa como un proxy válido para la complejidad basada en la información en escenarios prácticos. Los autores postulan que esto respalda la hipótesis general de que diferentes esquemas de codificación de IBC práctica son asintóticamente equivalentes. En consecuencia, la complejidad de estrella, al ser más tratable computacionalmente que los cálculos completos de IBC para grafos grandes, puede servir como un estimador fiable de la complejidad de un grafo.