GRALS: Un framework di ricerca locale guidato da GCN per il problema del vertex cover minimo

Uno studio recente pubblicato su arXiv (2503.06396) presenta GRALS, un metodo di ricerca locale volto a risolvere il problema del vertex cover minimo (MVC), che identifica il più piccolo insieme di vertici in grado di coprire tutti gli archi di un grafo non orientato. Essendo una sfida chiave di ottimizzazione combinatoria NP-hard, MVC ha implicazioni significative per l'analisi di reti e la progettazione di sistemi. Le euristiche di ricerca locale sono particolarmente efficaci per istanze di grandi dimensioni, offrendo un buon equilibrio tra qualità della soluzione e velocità computazionale. A differenza dei tradizionali algoritmi di ricerca locale ad alte prestazioni che utilizzano un approccio di rottura e riparazione, GRALS combina le probabilità a priori dei vertici da una rete convoluzionale a grafi (GCN) con un operatore di espansione, rivelazione ed eliminazione (ERE), guidando la ricerca verso aree più promettenti e migliorando la struttura della soluzione. Gli autori non hanno incluso risultati sperimentali o confronti nell'abstract.