Finding subgraphs with side constraints

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

doi:10.1007/978-3-030-78230-6_22

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 proceeding › Conference contribution

17 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 language	English
Title of host publication	Integration of constraint programming, artificial intelligence, and operations research - 18^thinternational conference, CPAIOR 2021, proceedings
Editors	Peter J. Stuckey
Place of Publication	Cham
Publisher	Springer
Pages	348-364
Number of pages	17
ISBN (Electronic)	9783030782306
ISBN (Print)	9783030782290
DOIs	https://doi.org/10.1007/978-3-030-78230-6_22
Publication status	Published - 5 Jul 2021
Event	18th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2021 - Virtual, Online Duration: 5 Jul 2021 → 8 Jul 2021

Publication series

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

Conference

Conference	18th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2021
City	Virtual, Online
Period	5/07/21 → 8/07/21

Access to Document

10.1007/978-3-030-78230-6_22

Akgun_2021_cpaior2021-finding-subgraphs_AAM
Copyright © Springer Nature Switzerland AG 2021. This work has been made available online in accordance with publisher policies or with permission. Permission for further reuse of this content should be sought from the publisher or the rights holder. This is the author created accepted manuscript following peer review and may differ slightly from the final published version. The final published version of this work is available at https://doi.org/10.1007/978-3-030-78230-6_22.
Accepted author manuscript, 0.99 MB

http://eprints.gla.ac.uk/239426/

Cite this

Akgün, Ö., Enright, J., Jefferson, C., McCreesh, C., Prosser, P., & Zschaler, S. (2021). Finding subgraphs with side constraints. In P. J. Stuckey (Ed.), Integration of constraint programming, artificial intelligence, and operations research - 18^thinternational conference, CPAIOR 2021, proceedings (pp. 348-364). (Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics); Vol. 12735). Springer. https://doi.org/10.1007/978-3-030-78230-6_22

Akgün, Özgür ; Enright, Jessica ; Jefferson, Christopher et al. / Finding subgraphs with side constraints. Integration of constraint programming, artificial intelligence, and operations research - 18^thinternational conference, CPAIOR 2021, proceedings. editor / Peter J. Stuckey. Cham : Springer, 2021. pp. 348-364 (Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics)).

@inproceedings{d586090d1c36443da26e5656438fc8ab,

title = "Finding subgraphs with side constraints",

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.",

author = "{\"O}zg{\"u}r Akg{\"u}n and Jessica Enright and Christopher Jefferson and Ciaran McCreesh and Patrick Prosser and Steffen Zschaler",

note = "Funding: This research was supported by the Engineering and Physical Sciences Research Council [grant number EP/P026842/1].; 18th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2021 ; Conference date: 05-07-2021 Through 08-07-2021",

year = "2021",

month = jul,

day = "5",

doi = "10.1007/978-3-030-78230-6_22",

language = "English",

isbn = "9783030782290",

series = "Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics)",

publisher = "Springer",

pages = "348--364",

editor = "Stuckey, {Peter J.}",

booktitle = "Integration of constraint programming, artificial intelligence, and operations research - 18th international conference, CPAIOR 2021, proceedings",

address = "Netherlands",

}

Akgün, Ö, Enright, J, Jefferson, C, McCreesh, C, Prosser, P & Zschaler, S 2021, Finding subgraphs with side constraints. in PJ Stuckey (ed.), Integration of constraint programming, artificial intelligence, and operations research - 18^thinternational conference, CPAIOR 2021, proceedings. Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics), vol. 12735, Springer, Cham, pp. 348-364, 18th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2021, Virtual, Online, 5/07/21. https://doi.org/10.1007/978-3-030-78230-6_22

Finding subgraphs with side constraints. / Akgün, Özgür; Enright, Jessica; Jefferson, Christopher et al.
Integration of constraint programming, artificial intelligence, and operations research - 18^thinternational conference, CPAIOR 2021, proceedings. ed. / Peter J. Stuckey. Cham: Springer, 2021. p. 348-364 (Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics); Vol. 12735).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Finding subgraphs with side constraints

AU - Akgün, Özgür

AU - Enright, Jessica

AU - Jefferson, Christopher

AU - McCreesh, Ciaran

AU - Prosser, Patrick

AU - Zschaler, Steffen

N1 - Funding: This research was supported by the Engineering and Physical Sciences Research Council [grant number EP/P026842/1].

PY - 2021/7/5

Y1 - 2021/7/5

N2 - 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.

AB - 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.

UR - https://doi.org/10.1007/978-3-030-78230-6

U2 - 10.1007/978-3-030-78230-6_22

DO - 10.1007/978-3-030-78230-6_22

M3 - Conference contribution

AN - SCOPUS:85111464769

SN - 9783030782290

T3 - Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics)

SP - 348

EP - 364

BT - Integration of constraint programming, artificial intelligence, and operations research - 18th international conference, CPAIOR 2021, proceedings

A2 - Stuckey, Peter J.

PB - Springer

CY - Cham

T2 - 18th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2021

Y2 - 5 July 2021 through 8 July 2021

ER -

Akgün Ö, Enright J, Jefferson C, McCreesh C, Prosser P, Zschaler S. Finding subgraphs with side constraints. In Stuckey PJ, editor, Integration of constraint programming, artificial intelligence, and operations research - 18^thinternational conference, CPAIOR 2021, proceedings. Cham: Springer. 2021. p. 348-364. (Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics)). Epub 2021 Jun 17. doi: 10.1007/978-3-030-78230-6_22

Finding subgraphs with side constraints

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Modelling and Optimisation with Graphs: Modelling and Optimisation with Graphs

Cite this

Finding subgraphs with side constraints

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Projects

Modelling and Optimisation with Graphs: Modelling and Optimisation with Graphs

Cite this