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

Resumo Técnico: Complexidade de Estrela como um Proxy para a Complexidade Baseada em Informação de Grafos

Enunciado do Problema
O artigo investiga se a "complexidade de estrela", uma medida estrutural de grafos, serve como um proxy prático para a "Complexidade Baseada em Informação" (IBC). A IBC é uma medida de complexidade formal definida pela proporção de descrições em uma linguagem específica que mapeiam para um dado objeto via um classificador. Embora a IBC teórica (baseada em máquinas de Turing universais) seja assintoticamente independente da linguagem de codificação, o artigo hipotetiza que medidas de IBC prática derivadas de diferentes esquemas de codificação também serão assintoticamente equivalentes. Especificamente, o estudo compara uma medida de IBC de grafo padrão ($C$), que codifica grafos via listas de arestas e os classifica por automorfismo, contra a complexidade de estrela, que define a complexidade com base no número mínimo de operações de união e interseção de "estrelas" elementares necessárias para construir um grafo.

Metodologia
A pesquisa emprega uma abordagem empírica comparativa utilizando duas medidas de complexidade distintas:

1. Complexidade de Grafo ($C$): Calculada usando a fórmula $C(x) = \ell - \log_2 \omega(x)$, onde $\ell$ é o comprimento da codificação da lista de arestas e $\omega$ é o número de strings daquela extensão que mapeiam para o mesmo grafo (determinado via algoritmos de automorfismo de grafos usando a biblioteca Nauty).
2. Complexidade de Estrela ($Star(G)$): Definida como o número mínimo de operações de conjunto (união/interseção) de estrelas elementares (um vértice central conectado a todos os outros) necessárias para gerar um grafo.
3. IBC Baseada em Estrela ($C^*$): Uma medida de IBC derivada especificamente da complexidade de estrela. Ela codifica o grafo armazenando a contagem de vértices, a contagem de estrelas e uma "receita" de Notação Polonesa Reversa (RPN) de operações. $C^*$ ajusta o comprimento de bits dessa receita subtraindo $\log_2 \omega$, onde $\omega$ representa o número de receitas equivalentes para um determinado grafo.
4. Estimativa de Limite Superior ($\overline{Star}(G)$): Como computar o $Star(G)$ exato requer uma busca exaustiva de todas as sequências possíveis de operações (o que é computacionalmente inviável para grafos grandes), os autores introduzem um limite superior algorítmico. Este algoritmo constrói um grafo cobrindo vértices de grau máximo com estrelas e cobrindo as arestas restantes via interseções pareadas, então otimiza a expressão usando associatividade de conjuntos.

Execução Experimental
O estudo utilizou o pacote EcoLab, otimizado para execução em GPU (Intel Xe graphics) para alcançar uma aceleração de 23x em relação ao processamento de CPU de thread única. Os experimentos envolveram:

• Busca Exaustiva de Pequena Escala: Gerando todos os grafos com 10 e 22 vértices que possuem uma complexidade de estrela de 8 ou menos. Isso permitiu o cálculo exato de $C$, $Star(G)$e$C^*$ (incluindo a enumeração de receitas equivalentes, $\omega$).
• Amostragem de Grande Escala: Gerando 1.000 grafos aleatórios de Erdős-Rényi com 1.000 vértices para testar a relação entre o limite superior facilmente computável $\overline{Star}(G)$ e a complexidade padrão $C$.

Resultos Principais

• Grafos Pequenos (10 e 22 vértices): A correlação entre a complexidade padrão $C$ e a complexidade de estrela bruta $Star(G)$ foi encontrada como negligenciável (coeficientes de correlação $\rho \approx 0,08$ e $-0,04$, respectivamente). Da mesma forma, a correlação entre $C$ e a IBC derivada de estrela $C^*$ foi fraca ($\rho \approx 0,14$ e próxima de zero).
• Correlação de Medidas: No entanto, $Star(G)$e$C^*$ mostraram uma correlação positiva moderada ($\rho \approx 0,6$), e o limite superior estimado $\overline{Star}(G)$ foi fortemente correlacionado com o $Star(G)$ exato ($\rho \approx 0,85$).
• Grafos Grandes (1.000 vértices): A descoberta mais significativa surgiu da amostragem de grande escala. Uma relação forte, embora não linear, foi observada entre o limite superior computável $\overline{Star}(G)$ e a complexidade baseada em informação $C$.

Significância e Alegações
O artigo conclui que, embora a complexidade de estrela bruta não correlacione linearmente com a complexidade baseada em informação em conjuntos de dados exaustivos pequenos, as duas medidas provavelmente estão medindo a mesma propriedade subjacente para grafos maiores. A forte relação empírica entre o limite superior facilmente computável da complexidade de estrela $\overline{Star}(G)$ e a medida de complexidade de informação padrão $C$ sugere que a complexidade de estrela atua como um proxy válido para a complexidade baseada em informação em cenários práticos. Os autores postulam que isso apoia a hipótesa mais ampla de que diferentes esquemas de codificação de IBC prática são assintoticamente equivalentes. Consequentemente, a complexidade de estrela, sendo mais computacionalmente tratável do que os cálculos de IBC total para grafos grandes, pode servir como um estimador confiável para a complexidade de grafos.