Between subgraph isomorphism and maximum common subgraph

Ruth Hoffmann, Ciaran McCreesh, Craig Reilly

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Citations (Scopus)

Abstract

When a small pattern graph does not occur inside a larger target graph, we can ask how to find "as much of the pattern as possible" inside the target graph. In general, this is known as the maximum common subgraph problem, which is much more computationally challenging in practice than subgraph isomorphism. We introduce a restricted alternative, where we ask if all but k vertices from the pattern can be found in the target graph. This allows for the development of slightly weakened forms of certain invariants from subgraph isomorphism which are based upon degree and number of paths. We show that when k is small, weakening the invariants still retains much of their effectiveness. We are then able to solve this problem on the standard problem instances used to benchmark subgraph isomorphism algorithms, despite these instances being too large for current maximum common subgraph algorithms to handle. Finally, by iteratively increasing k, we obtain an algorithm which is also competitive for the maximum common subgraph problem.
Original languageEnglish
Title of host publicationThirty-First AAAI Conference on Artificial Intelligence
Subtitle of host publicationFebruary 4–9, 2017, San Francisco, California USA
Place of PublicationPalo Alto
PublisherAAAI Press
Pages3907-3914
Number of pages8
Publication statusPublished - 13 Feb 2017
Event31st AAAI Conference on Artificial Intelligence, AAAI 2017 - San Francisco, United States
Duration: 4 Feb 201710 Feb 2017
http://www.aaai.org/Conferences/AAAI/2017/aaai17call.php

Conference

Conference31st AAAI Conference on Artificial Intelligence, AAAI 2017
Country/TerritoryUnited States
CitySan Francisco
Period4/02/1710/02/17
Internet address

Fingerprint

Dive into the research topics of 'Between subgraph isomorphism and maximum common subgraph'. Together they form a unique fingerprint.

Cite this