Finding subgraphs with side constraints

Özgür Akgün, Jessica Enright, Christopher Jefferson, Ciaran McCreesh*, Patrick Prosser, Steffen Zschaler

*Corresponding author for this work

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

12 Downloads (Pure)

Abstract

The subgraph isomorphism problem is to find a small “pattern” graph inside a larger “target” graph. There are excellent dedicated solvers for this problem, but they require substantial programming effort to handle the complex side constraints that often occur in practical applications of the problem; however, general purpose constraint solvers struggle on more difficult graph instances. We show how to combine the state of the art Glasgow Subgraph Solver with the Minion constraint programming solver to get a “subgraphs modulo theories” solver that is both performant and flexible. We also show how such an approach can be driven by the Essence high level modelling language, giving ease of modelling and prototyping to non-expert users. We give practical examples involving temporal graphs, typed graphs from software engineering, and costed subgraph isomorphism problems.

Original languageEnglish
Title of host publicationIntegration of constraint programming, artificial intelligence, and operations research - 18th international conference, CPAIOR 2021, proceedings
EditorsPeter J. Stuckey
Place of PublicationCham
PublisherSpringer
Pages348-364
Number of pages17
ISBN (Electronic)9783030782306
ISBN (Print)9783030782290
DOIs
Publication statusPublished - 5 Jul 2021
Event18th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2021 - Virtual, Online
Duration: 5 Jul 20218 Jul 2021

Publication series

NameLecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics)
Volume12735
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference18th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2021
CityVirtual, Online
Period5/07/218/07/21

Fingerprint

Dive into the research topics of 'Finding subgraphs with side constraints'. Together they form a unique fingerprint.

Cite this