A Partitioning Algorithm for Maximum Common Subgraph Problems

We introduce a new branch and bound algorithm for the maximum common subgraph and maximum common connected subgraph problems which is based around vertex labelling and partitioning. Our method in some ways resembles a traditional constraint programming approach, but uses a novel compact domain store and supporting inference algorithms which dramatically reduce the memory and computation requirements during search, and allow better dual viewpoint ordering heuristics to be calculated cheaply. Experiments show a speedup of more than an order of magnitude over the state of the art, and demonstrate that we can operate on much larger graphs without running out of memory.

Authors

• Ciaran McCreesh University of Glasgow, Scotland (UK)
• Patrick Prosser Toby Walsh
• James Trimble

Keywords

• Combinatorial & Heuristic Search: Combinatorial search/optimisation
• Constraints and Satisfiability: Constraint Optimisation
• Constraints and Satisfiability: Constraint Satisfaction