Event description
The subgraph isomorphism problem—determining whether a small query graph occurs within a larger target graph—represents a fundamental challenge in computer science and artificial intelligence. Despite being NP-complete, this problem has driven significant algorithmic innovation and found applications across diverse domains.
This seminar traces a fifteen-year research trajectory on subgraph isomorphism, beginning with my master's studies at the University of Catania and continuing as a central theme of my current work. I will present the evolution of algorithmic approaches to this problem and demonstrate how its complexity has motivated exploration across multiple research dimensions.
The talk will cover applications in three main areas: indexing and searching within large molecular databases in computational chemistry, where efficient substructure search is critical for drug discovery and chemical informatics; analysis of biological networks, where subgraph matching helps uncover recurring patterns and functional modules that reveal system behavior; and query processing in modern NoSQL database management systems, where graph pattern matching has become increasingly important.
Throughout this journey, two cross-cutting themes have been paramount: the development of specialized searching strategies that accelerate the search process, and the design of parallel algorithms to exploit modern computing architectures. I will discuss how these technical innovations have enabled practical solutions to what remains a theoretically intractable problem, and outline ongoing challenges and future directions in this active research area.