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

Stephan Gocht, Ross McBride, Ciaran McCreesh, Jakob Nordström, Patrick Prosser, James Trimble

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceedingForskningPeer review

3 Citeringar (SciVal)

Sammanfattning

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.
Originalspråkengelska
Titel på gästpublikationPrinciples and Practice of Constraint Programming - 26th International Conference, CP 2020, Proceedings
RedaktörerHelmut Simonis
FörlagSpringer
Sidor338-357
Antal sidor20
ISBN (tryckt)9783030584740
DOI
StatusPublished - 2020
Evenemang26th International Conference on Principles and Practice of Constraint Programming, CP 2020 - Louvain-la-Neuve, Belgien
Varaktighet: 2020 sep 72020 sep 11

Publikationsserier

NamnLecture Notes in Computer Science
FörlagSpringer
Volym12333
ISSN (tryckt)0302-9743
ISSN (elektroniskt)1611-3349

Konferens

Konferens26th International Conference on Principles and Practice of Constraint Programming, CP 2020
Land/TerritoriumBelgien
OrtLouvain-la-Neuve
Period2020/09/072020/09/11

Ämnesklassifikation (UKÄ)

  • Datavetenskap (datalogi)

Citera det här