Masterprüfung mit Defensio, Jonathan Trummer

17.12.2021 10:00 - 11:30

„Engineering Maximum Common Subgraph Algorithms for Large Graphs“

The Maximum Common Subgraph problem is to find the largest subgraph common to two given graphs. This problem finds applications in a wide variety of fields, for example it can be utilized to find common substructures between two molecules, which may be useful in the fields of chemistry, molecular science and computational drug discovery. As the problem is NP-complete, finding an optimal solution requires exhaustively exploring the solution space. Various different approaches have been applied to the Maximum Common Subgraph problem, such as reducing it to the Maximum Clique or Minimum Vertex-Cover problems, applying Constraint-Satisfaction Programming or utilizing a partitioning approach. We propose two methods of data reduction, which may be used to reduce the sizes of the input graphs and can thus simplify the problem. Additionally, we propose two methods of computing upper bounds, as means to terminate the search for solutions as soon as the best solution found matches the upper bound. We explore the exploitation of symmetries, as to reduce the search space which needs to be explored, and we evaluate an Independent Set solver as an alternative solver. Finally, we extensively evaluate existing approaches and our techniques experimentally, where we show that a heuristic independent set solver may significantly outperform existing approaches both in terms of running time as well as result quality, given a maximum execution time per problem instance. We additionally introduce a pre-processing phase for a partitioning-based solver, which is able to reduce the running time on instances of one instance group by over 80%.

Organiser:

SPL 5

Location:
online Videokonferenz