Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Certifying Solvers for Clique and Maximum Common (Connected) Subgraph Problems

Gocht, Stephan LU ; McBride, Ross ; McCreesh, Ciaran ; Nordström, Jakob LU ; Prosser, Patrick and Trimble, James (2020) 26th International Conference on Principles and Practice of Constraint Programming, CP 2020 In Lecture Notes in Computer Science 12333. p.338-357
Abstract
An algorithm is said to be certifying if it outputs, together with a solution to the problem it solves, a proof that this solution is correct. We explain how state of the art maximum clique, maximum weighted clique, maximal clique enumeration and maximum common (connected) induced subgraph algorithms can be turned into certifying solvers by using pseudo-Boolean models and cutting planes proofs, and demonstrate that this approach can also handle reductions between problems. The generality of our results suggests that this method is ready for widespread adoption in solvers for combinatorial graph problems.
Please use this url to cite or link to this publication:
author
; ; ; ; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Principles and Practice of Constraint Programming - 26th International Conference, CP 2020, Proceedings
series title
Lecture Notes in Computer Science
editor
Simonis, Helmut
volume
12333
pages
20 pages
publisher
Springer
conference name
26th International Conference on Principles and Practice of Constraint Programming, CP 2020
conference location
Louvain-la-Neuve, Belgium
conference dates
2020-09-07 - 2020-09-11
external identifiers
  • scopus:85091288907
ISSN
0302-9743
1611-3349
ISBN
9783030584740
DOI
10.1007/978-3-030-58475-7_20
language
English
LU publication?
yes
id
5c2383a0-f2dc-4652-89fd-acfdc5e08f79
date added to LUP
2020-10-28 15:16:07
date last changed
2024-04-17 18:01:09
@inproceedings{5c2383a0-f2dc-4652-89fd-acfdc5e08f79,
  abstract     = {{An algorithm is said to be certifying if it outputs, together with a solution to the problem it solves, a proof that this solution is correct. We explain how state of the art maximum clique, maximum weighted clique, maximal clique enumeration and maximum common (connected) induced subgraph algorithms can be turned into certifying solvers by using pseudo-Boolean models and cutting planes proofs, and demonstrate that this approach can also handle reductions between problems. The generality of our results suggests that this method is ready for widespread adoption in solvers for combinatorial graph problems.}},
  author       = {{Gocht, Stephan and McBride, Ross and McCreesh, Ciaran and Nordström, Jakob and Prosser, Patrick and Trimble, James}},
  booktitle    = {{Principles and Practice of Constraint Programming - 26th International Conference, CP 2020, Proceedings}},
  editor       = {{Simonis, Helmut}},
  isbn         = {{9783030584740}},
  issn         = {{0302-9743}},
  language     = {{eng}},
  pages        = {{338--357}},
  publisher    = {{Springer}},
  series       = {{Lecture Notes in Computer Science}},
  title        = {{Certifying Solvers for Clique and Maximum Common (Connected) Subgraph Problems}},
  url          = {{http://dx.doi.org/10.1007/978-3-030-58475-7_20}},
  doi          = {{10.1007/978-3-030-58475-7_20}},
  volume       = {{12333}},
  year         = {{2020}},
}