Breaking Symmetries from a Set-Covering Perspective

Titolo: Rottura delle Simmetrie da una Prospettiva di Copertura degli Insiemi

Autori: Michael Codish e Mikoláš Janota

---

1. Il Problema

I problemi di ricerca sui grafi (come la verifica di esistenza, l'enumerazione o problemi estremali) soffrono di due principali ostacoli computazionali:

1. Spazio di ricerca enorme: Il numero di grafi possibili cresce esponenzialmente con il numero di vertici $n$.
2. Simmetrie (Isomorfismi): Molti grafi sono isomorfi tra loro (ottenibili permutando i vertici). Senza gestione delle simmetrie, gli algoritmi di ricerca esplorano ripetutamente lo stesso oggetto matematico sotto diverse etichette, sprecando risorse.

L'obiettivo è identificare un grafo canonico unico per ogni classe di isomorfismo. Una tecnica comune è l'aggiunta di vincoli di rottura della simmetria (es. vincoli LexLeader) che restringono la ricerca ai soli grafi che sono lessicograficamente minimi rispetto a tutte le loro permutazioni. Tuttavia, il vincolo LexLeader completo richiede un numero super-esponenziale di vincoli (uno per ogni permutazione in $S_n$), rendendolo impraticabile.

L'obiettivo specifico di questo lavoro è trovare rotture di simmetria complete e ottimali, definite come l'insieme minimo di permutazioni necessario per coprire tutti i grafi non canonici, minimizzando così il numero di vincoli lex-constraint aggiunti.

2. Metodologia

Gli autori riformulano il problema della rottura della simmetria come un classico problema di Set Covering (Copertura degli Insiemi).

A. Formalizzazione come Set Covering

• Universo ($U$): L'insieme di tutti i grafi non canonici di ordine $n$.
• Sottoinsiemi ($S$): Per ogni permutazione $\pi \in S_n$, si definisce l'insieme cover($\pi$) come l'insieme dei grafi $G$ tali che $\pi(G) < G$ (il grafi che diventano "più piccoli" applicando la permutazione).
• Obiettivo: Trovare il sottoinsieme minimo di permutazioni $\Pi \subseteq S_n$ tale che l'unione dei loro insiemi cover copra tutti i grafi non canonici. Questo insieme $\Pi$ costituisce una rottura di simmetria completa e ottima.

B. Rappresentazione Simbolica e Pattern

Poiché l'universo dei grafi è di ordine $2^{\binom{n}{2}}$ e il numero di permutazioni è $n!$, la costruzione esplicita della matrice del problema di copertura è impossibile per $n$ anche moderatamente grandi.

• Pattern: Gli autori introducono una rappresentazione compatta degli insiemi di grafi coperti da una permutazione. Invece di elencare i grafi, usano "pattern" (assegnazioni parziali di variabili booleane) derivati dalla risoluzione simbolica del vincolo $\pi(G) < G$.
• Dominanza:
  • Dominanza di Permutazione: Se l'insieme di grafi coperti da $\pi_1$ è un sottoinsieme di quelli coperti da $\pi_2$, $\pi_1$ è ridondante e può essere scartato.
  • Dominanza di Grafo: Se un grafo $G_1$ è coperto da un sottoinsieme di permutazioni che coprono anche $G_2$, allora $G_2$ è ridondante (dominato) e può essere rimosso dall'universo.

C. Identificazione delle "Backbone" (Permutazioni Chiave)

Una permutazione è definita backbone se è l'unica a coprire almeno un grafo non canonico. Queste permutazioni sono essenziali e devono far parte di qualsiasi soluzione ottima.
Il paper propone due approcci ibridi per identificare le backbone senza costruire l'intera matrice:

1. Iterazione sui Grafi: Scansione dei grafi (con ottimizzazioni per "saltare" blocchi di grafi canonici o già coperti) per trovare quelli coperti da una sola permutazione.
2. Iterazione sulle Permutazioni: Utilizzo di chiamate SAT (Satisfiability) per verificare se una permutazione è dominata da un insieme di altre.

D. Ottimizzazioni

Il processo di risoluzione segue tre fasi di ottimizzazione (adattate da tecniche classiche di Set Covering):

1. Dominanza di Permutazione: Rimozione delle permutazioni ridondanti.
2. Dominanza di Grafo: Rimozione dei grafi ridondanti.
3. Identificazione delle Backbone: Rimozione delle permutazioni essenziali e dei grafi che coprono, iterativamente fino a quando il problema residuo è risolvibile.

3. Risultati Principali

Gli autori hanno implementato il loro approccio e ottenuto risultati significativi per grafi di ordine $n \le 10$:

• Ottimalità per $n \le 10$: È stato possibile calcolare le rotture di simmetria complete ottimali (minimo numero di vincoli lex-constraint) per tutti i grafi fino a $n=10$.
• Riduzione della Complessità:
  • Per $n < 10$, il problema di Set Covering residuo è stato risolto interamente tramite le ottimizzazioni (dominanza e backbone), senza bisogno di risolvere un problema di ottimizzazione generale.
  • Per $n=10$, il problema iniziale (di dimensioni astronomiche, $10! \times 2^{45}$) è stato ridotto a un problema di Set Covering di dimensioni gestibili ($199 \times 197$), risolto in 0.01 secondi utilizzando un solver OPB (Optimization Pseudo-Boolean) come RoundingSat.
• Confronto con lo Stato dell'Arte: Le soluzioni ottimali trovate sono state confrontate con le rotture di simmetria "compatte" calcolate in lavori precedenti (Codish et al., 2016). Le nuove soluzioni ottimali sono inferiori o molto vicine (meno del 10% in più) rispetto a quelle precedenti, confermando l'efficacia del metodo.
• Rotture Parziali: L'insieme delle sole permutazioni backbone (senza risolvere il Set Cover completo) fornisce una rottura di simmetria parziale molto precisa, superando le tecniche basate sulle semplici trasposizioni (scambio di coppie di vertici) in termini di rapporto di ridondanza.

4. Contributi Chiave

1. Nuova Formalizzazione: La prima formalizzazione esplicita della rottura della simmetria come problema di Set Covering, aprendo la strada all'uso di decenni di ricerca su tecniche esatte e approssimate per questo problema.
2. Rappresentazione Compatta (Pattern): Introduzione di una tecnica simbolica basata su pattern per rappresentare insiemi esponenziali di grafi, permettendo di manipolare il problema senza esplicitare l'universo.
3. Algoritmi Ibridi: Sviluppo di algoritmi che combinano iterazione su grafi/permutazioni e risoluzione SAT per identificare le permutazioni essenziali (backbone) e dominanti in modo incrementale.
4. Risultati Pratici: Calcolo di soluzioni ottimali per casi complessi ($n=10$) che erano precedentemente fuori portata per metodi esatti basati su vincoli lex-constraint.

5. Significato e Impatto

Questo lavoro rappresenta un passo avanti fondamentale nella risoluzione di problemi di ricerca su grafi:

• Efficienza: Dimostra che è possibile ottenere rotture di simmetria complete e ottimali per istanze non banali, riducendo drasticamente lo spazio di ricerca.
• Generalità: Il framework proposto non è limitato ai grafi ma può essere applicato ad altri problemi di ricerca combinatoria con simmetrie.
• Sinergia Teorico-Pratica: Unisce la teoria della complessità (NP-completezza del Set Cover) con tecniche pratiche di risoluzione (SAT, OPB) e ottimizzazioni simboliche.
• Futuro: Apre la strada alla costruzione di rotture di simmetria parziali altamente efficienti e precise, utili quando le soluzioni complete sono troppo costose da calcolare.

In sintesi, il paper trasforma un problema apparentemente intrattabile di gestione delle simmetrie in un problema di copertura degli insiemi gestibile, fornendo soluzioni ottimali per grafi fino a 10 vertici e stabilendo nuovi standard per l'efficienza nella ricerca combinatoria.