Breaking Symmetries from a Set-Covering Perspective

Resumo Técnico: Quebra de Simetrias sob uma Perspectiva de Cobertura de Conjuntos

1. O Problema

Os problemas de busca em grafos (encontrar grafos com propriedades estruturais específicas) enfrentam dois desafios principais: o espaço de busca exponencialmente grande e a presença massiva de simetrias. Qualquer permutação dos vértices de um grafo resulta em um grafo isomorfo (simétrico), o que leva a esforço de busca redundante ao explorar o mesmo objeto múltiplas vezes.

O objetivo é restringir a busca a um único grafo "canônico" por classe de isomorfismo. A abordagem clássica utiliza restrições de quebra de simetria (como a restrição LexLeader), que exigem que o grafo seja lexicograficamente menor do que qualquer uma de suas permutações. No entanto, a restrição LexLeader completa envolve um número superexponencial de permutações ($n!$), tornando-a impraticável. Trabalhos anteriores buscaram conjuntos menores de permutações que ainda garantem a quebra completa de simetrias, mas a otimização do tamanho desses conjuntos (número mínimo de restrições) permanece um desafio.

2. Metodologia

Os autores propõem uma mudança de paradigma: formalizar a quebra de simetria como um Problema de Cobertura de Conjuntos (Set-Cover Problem).

• Definição de Cobertura: Uma permutação $\pi$ "cobre" um grafo $G$ se a aplicação de $\pi$ em $G$ resultar em um grafo lexicograficamente menor ($\pi(G) < G$).
• Objetivo: Um conjunto de permutações é uma quebra de simetria completa se e somente se cobrir todos os grafos não-canônicos. O problema torna-se encontrar o menor conjunto de permutações que cobre todo o universo de grafos não-canônicos.
• Desafio de Escala: O universo (todos os grafos não-canônicos) tem tamanho da ordem de $2^{n^2/2}$ e o conjunto de subconjuntos (permutações) tem tamanho $n!$. Para $n=10$, isso é computacionalmente intratável de forma explícita.

Para lidar com essa escala, os autores desenvolvem uma abordagem simbólica baseada em três otimizações clássicas de cobertura de conjuntos, adaptadas para este contexto:

1. Representação Concisa via Padrões (Patterns): Em vez de listar grafos individualmente, eles representam o conjunto de grafos cobertos por uma permutação usando "padrões" (conjunções de igualdades entre variáveis booleanas). Isso permite manipular conjuntos exponenciais de grafos de forma compacta.
2. Dominação de Permutações: Se o conjunto de grafos cobertos por $\pi_1$ é um subconjunto dos cobertos por $\pi_2$, então $\pi_1$ é dominado por $\pi_2$ e pode ser descartado.
3. Dominação de Grafos: Se um grafo $G_1$ é coberto por um subconjunto das permutações que cobrem $G_2$, então $G_2$ é dominado por $G_1$ e pode ser removido da consideração.
4. Identificação de "Backbones" (Espinhas Dorsais): Uma permutação é um backbone se ela é a única que cobre um determinado grafo. Essas permutações são essenciais e devem fazer parte de qualquer solução ótima.

Algoritmos Propostos:

• Cálculo de Backbones: Utilizam duas abordagens combinadas: iteração sobre grafos (com "saltos" heurísticos para pular grafos já cobertos ou canônicos) e iteração sobre permutações usando chamadas SAT (Satisfiability) para verificar se uma permutação é essencial.
• Resolução do Problema: Após aplicar as otimizações simbólicas (dominação e backbones), o problema restante é formulado como um problema de otimização pseudo-booleana (OPB) e resolvido usando o solver RoundingSat.

3. Contribuições Principais

• Formalização Teórica: Estabelece a equivalência entre a quebra de simetria completa e o problema de cobertura de conjuntos, abrindo portas para técnicas de otimização e aproximação já existentes na literatura de CS.
• Otimização Simbólica: Desenvolve métodos para realizar as otimizações de cobertura (dominação e identificação de backbones) sem construir explicitamente a matriz gigante do problema, operando diretamente sobre representações simbólicas (padrões) e usando SAT.
• Soluções Ótimas: Apresenta as primeiras quebras de simetria completas e ótimas (número mínimo de restrições lexicográficas) para grafos de ordem $n \le 10$.
• Quebras Parciais Eficientes: Demonstra que o conjunto de backbones encontrado pode ser usado como uma quebra de simetria parcial altamente precisa, superando métodos anteriores baseados em transposições.

4. Resultados

Os experimentos foram realizados para grafos de ordem $n$ de 4 a 10:

• Ordem $n \le 9$: O problema foi resolvido inteiramente através das otimizações (dominação e backbones). O conjunto final de permutações foi encontrado sem necessidade de resolver um problema de cobertura geral complexo.
• Ordem $n = 10$: O problema inicial (com $10!$ permutações e $2^{45}$ grafos) foi reduzido via otimizações simbólicas para uma matriz de apenas 199 linhas e 197 colunas. O problema residual foi resolvido em 0,01 segundos, resultando em um conjunto ótimo de 7.853 permutações.
• Comparação: As soluções ótimas encontradas são ligeiramente menores (menos de 10% de redução) do que os conjuntos de canonização reportados em trabalhos anteriores (ex: [19]), mas garantem a minimalidade absoluta.
• Quebra Parcial: O uso de apenas os backbones (conjunto muito menor, ex: 131 permutações para $n=10$) fornece uma quebra de simetria parcial com uma razão de redundância significativamente melhor do que métodos baseados em transposições.

5. Significado e Impacto

Este trabalho é significativo por várias razões:

1. Eficiência Computacional: Demonstra que problemas de simetria, tradicionalmente vistos como intratáveis devido ao tamanho do espaço de busca, podem ser "domados" através da reformulação como problemas de cobertura de conjuntos e aplicação agressiva de otimizações simbólicas.
2. Novo Paradigma: Oferece uma nova lente teórica para a quebra de simetria, permitindo a aplicação de décadas de pesquisa em algoritmos de cobertura de conjuntos (exatos e aproximados) para melhorar a busca em grafos.
3. Aplicabilidade Prática: As soluções ótimas para $n \le 10$ servem como benchmarks e ferramentas práticas para verificação formal e enumeração de grafos. Além disso, a abordagem de backbones oferece uma estratégia viável para quebras de simetria parciais em problemas maiores onde soluções completas são impossíveis.
4. Escalabilidade: A metodologia de "saltar" sobre grafos canônicos ou já cobertos e o uso de representações de padrões permitem lidar com instâncias que seriam impossíveis de processar com abordagens explícitas.

Em suma, o artigo transforma um problema de simetria complexo em um problema de cobertura de conjuntos gerenciável, utilizando técnicas avançadas de SAT e otimização para encontrar soluções teoricamente ótimas para grafos de até 10 vértices.