For two given graphs, G and H, the maximum common subgraph problem (MCS) asks for the largest graph contained in both G and H. An important application occurs in cheminformatics, where the similarity of molecular graphs needs to be quantified. Unfortunately, MCS is NP-hard unless additional constraints regarding the properties of G, H, and the subgraph are enforced. A polynomial-time solvable case requires that all these graphs are trees. Known negative complexity results for classes of tree-like graphs set narrow boundaries for generalization.

The project aims to investigate particular tree-like graph classes to design, implement, and experimentally evaluate new polynomial-time algorithms. New NP-hardness proofs for specific cases should refine the complexity status further.

Requirements: Strong interest in algorithms and graph theory

Contact: Nils Kriege