Il problema del massimo comune sottografo: due premi internazionali alla ricerca del DAUIN
Che cosa accomuna un circuito elettronico, una molecola e una rete informatica? A prima vista sembrano appartenere ad ambiti completamente diversi. Dal punto di vista dei modelli matematici, però, possono essere rappresentati nello stesso modo: come grafi, strutture costituite da nodi, che corrispondono agli elementi del sistema, e archi, che ne descrivono le relazioni. Da questa rappresentazione nasce uno dei problemi classici dell'informatica e della matematica applicata: il problema del massimo comune sottografo, al centro della ricerca del dottorando Lorenzo Cardone, svolta presso il Dipartimento di Automatica e Informatica-DAUIN sotto la supervisione dei professori Stefano Quer e Paolo Bernardi, attività che di recente è stata riconosciuta con due importanti premi internazionali.
Il problema consiste nell'individuare, all'interno di due grafi, la struttura più grande che essi condividono: un insieme di nodi e archi che possa essere messo in corrispondenza preservando le relazioni tra gli elementi. Nella variante indotta, considerata in uno dei due lavori premiati, la corrispondenza deve preservare anche l'assenza di collegamenti tra le coppie di nodi selezionate.
È un problema estremamente complesso dal punto di vista computazionale: il numero delle possibili corrispondenze cresce combinatoriamente con la dimensione dei grafi e, nel caso generale, non sono noti algoritmi capaci di garantire la soluzione ottimale in tempo polinomiale. Esplorare esaustivamente tutte le alternative diventa quindi rapidamente impraticabile.
Eppure, riuscire a trovare queste corrispondenze è fondamentale in moltissimi ambiti.
In bioinformatica e chimica computazionale, ad esempio, il confronto tra grafi molecolari permette di individuare sottostrutture comuni e possibili proprietà condivise. Nella sicurezza informatica può aiutare a riconoscere analogie strutturali tra reti, programmi o sistemi complessi. Nella progettazione elettronica, invece, consente di identificare automaticamente porzioni equivalenti di circuiti digitali, semplificando alcune attività di verifica e collaudo.
È proprio quest'ultima applicazione a essere al centro della ricerca del gruppo del DAUIN.
I moderni microprocessori contengono miliardi di transistor e vengono verificati prima della produzione mediante simulazioni software e piattaforme hardware dedicate basate su FPGA (Field-Programmable Gate Array), dispositivi riconfigurabili che possono emulare il comportamento del circuito. L'emulazione su FPGA accelera notevolmente i test rispetto alla sola simulazione, ma i sistemi necessari per ospitare progetti sempre più complessi possono richiedere molte risorse hardware e comportare costi elevati. Riconoscere automaticamente le porzioni equivalenti presenti in circuiti diversi permette di condividere o riutilizzare parte dell'infrastruttura di test, riducendo le risorse hardware dedicate e rendendo più efficiente l'intero processo di verifica.
Il problema del massimo comune sottografo è NP-difficile e appartiene quindi alla classe dei problemi più impegnativi dell'ottimizzazione combinatoria. Anche grafi con poche decine di nodi possono richiedere ore o giorni per certificare la soluzione ottimale. Per questo, nella pratica, un algoritmo efficace deve non solo trovare soluzioni di alta qualità in tempi brevi, ma anche contenere il consumo di memoria e, quando possibile, fornire informazioni utili a valutare quanto la soluzione trovata sia vicina all'ottimo.
Negli ultimi anni il gruppo del DAUIN ha sviluppato nuovi algoritmi proprio con questo obiettivo, ottenendo due importanti riconoscimenti internazionali.
Il primo lavoro, Fast Circuit Analysis via Neighborhood-Guided Maximum Common Subgraph, è valso al dottorando Lorenzo Cardone l'Outstanding Student Presentation Award durante la 31ª edizione dell'IEEE European Test Symposium (ETS 2026).
Realizzato insieme ai docenti Stefano Quer e Paolo Bernardi, lo studio introduce una rappresentazione compatta dei circuiti e una strategia di ricerca guidata dalle informazioni di vicinato dei nodi. Questi accorgimenti riducono lo spazio di ricerca e indirizzano più rapidamente l'algoritmo verso corrispondenze promettenti. Il risultato è la possibilità di analizzare circuiti di grandi dimensioni con un impiego di memoria più contenuto e prestazioni superiori rispetto alle tecniche di confronto considerate nello studio.
Poche settimane dopo è arrivato il secondo riconoscimento. Il professor Stefano Quer e il dottorando Lorenzo Cardone hanno ricevuto, alla 21ª edizione dell'International Conference on Software Technologies, il Best Paper Award 2026 per il lavoro Cooperative Multi-Heuristic Parallelization for the Maximum Common Induced Subgraph Problem.
Se il primo studio migliora l'efficienza del confronto tra grafi, il secondo propone una ricerca parallela cooperativa. Più euristiche vengono eseguite sui diversi core del processore e condividono le migliori soluzioni correnti, utili per potare lo spazio di ricerca; le configurazioni meno produttive ricevono progressivamente meno risorse. La cooperazione consente così di trovare più rapidamente soluzioni migliori e di sfruttare in modo efficace i processori multicore.
Dietro il problema del massimo comune sottografo si sviluppa così una ricerca che combina teoria degli algoritmi, ingegneria informatica e calcolo ad alte prestazioni. Migliorare questi algoritmi può tradursi in tempi di analisi più brevi, minori risorse di calcolo e strumenti più efficaci per la verifica dei circuiti, la bioinformatica, la chimica computazionale e la sicurezza informatica.
“Questi riconoscimenti confermano il valore di una ricerca che coniuga risultati teorici e applicazioni concrete. Migliorare gli algoritmi per il massimo comune sottografo significa rendere possibile l'analisi di problemi sempre più grandi e complessi, con ricadute dirette nella verifica dei circuiti elettronici e, più in generale, in tutti gli ambiti in cui è necessario confrontare strutture rappresentate come grafi”, dichiarano il dottorando Lorenzo Cardone e i professori Stefano Quer e Paolo Bernardi.