The subgraph isomorphism problem is NP-complete and has applications in bioinformatics, network analysis, and computer vision. This thesis presents an empirical evaluation of five solvers for the induced subgraph isomorphism problem: RI, VF3, PathLAD, SICS, and the Glasgow Subgraph Solver. We tested them on synthetic graphs (minimum spanning trees, scale-free networks, and Erdős–Rényi graphs), real networks from the SNAP collection, and non-matching instances. The evaluation focused on runtime and memory usage. Results indicate that solver performance depends strongly on graph structure and pattern size: Glasgow excels on small and medium cases, RI on larger instances, PathLAD on dense graphs, SICS on real and scale-free networks, while VF3 is most effective on sparse tree-like structures. The thesis contributes a comparative analysis to guide the selection of suitable solvers for specific scenarios.
|
