Certifying Solvers for Clique and Maximum Common (Connected) Subgraph Problems
(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:
https://lup.lub.lu.se/record/5c2383a0-f2dc-4652-89fd-acfdc5e08f79
- author
- Gocht, Stephan LU ; McBride, Ross ; McCreesh, Ciaran ; Nordström, Jakob LU ; Prosser, Patrick and Trimble, James
- organization
- publishing date
- 2020
- 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
- 1611-3349
- 0302-9743
- 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-06-27 00:02:55
@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 = {{1611-3349}}, 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}}, }