Paper Info
Title
Certifying Solvers for Clique and Maximum Common (Connected) Subgraph Problems.
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.
Year
DOI
Venue
2020
10.1007/978-3-030-58475-7_20
CP
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
0
6
Name
Order
Citations
PageRank
Stephan Gocht100.34
Ross McBride200.34
Ciaran McCreesh36811.18
Jakob Nordström417721.76
Patrick Prosser564248.68
James Trimble6275.75