Effective Heuristics for Assessing the Similarity of a Set of Graphs

The maximum common subgraph problem has been proven to have NP-hard complexity. Despite this theoretical limit, state-of-the-art algorithms made it viable to solve the problem exactly for some applications. This thesis discusses improvements to the state-of-the-art (a branch and bound algorithm with a smart partitioning strategy) in two areas: the generalization of the algorithm to handle sets of graphs and a best-first search space exploration strategy. The original algorithm is not well suited to serve applications where time is constrained, and approximate solutions can be accepted, as it is designed to explore the solution space exhaustively. The proposed heuristics aim to achieve better approximate solutions in time-bounded problem instances. Experiments demonstrated that our heuristics are scalable to multiple threads with low overhead. Finally, they can handle heterogeneous sets of graphs in sensible ways (i.e., discarding graphs that are not similar to most of the set).