Standard
Subgraph Isomorphism Meets Cutting Planes : Solving With Certified Solutions. / Gocht, Stephan; McCreesh, Ciaran; Nordström, Jakob.
Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI '20). International Joint Conferences on Artificial Intelligence, 2020. p. 1134-1140.
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
Gocht, S, McCreesh, C
& Nordström, J 2020,
Subgraph Isomorphism Meets Cutting Planes: Solving With Certified Solutions. in
Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI '20). International Joint Conferences on Artificial Intelligence, pp. 1134-1140, 29th International Joint Conference on Artificial Intelligence (IJCAI-20), Yokohama / Virtuel, Japan,
07/01/2021.
https://doi.org/10.24963/ijcai.2020/158APA
Gocht, S., McCreesh, C.
, & Nordström, J. (2020).
Subgraph Isomorphism Meets Cutting Planes: Solving With Certified Solutions. In
Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI '20) (pp. 1134-1140). International Joint Conferences on Artificial Intelligence.
https://doi.org/10.24963/ijcai.2020/158Vancouver
Gocht S, McCreesh C
, Nordström J.
Subgraph Isomorphism Meets Cutting Planes: Solving With Certified Solutions. In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI '20). International Joint Conferences on Artificial Intelligence. 2020. p. 1134-1140
https://doi.org/10.24963/ijcai.2020/158Author
Gocht, Stephan ; McCreesh, Ciaran ; Nordström, Jakob. / Subgraph Isomorphism Meets Cutting Planes : Solving With Certified Solutions. Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI '20). International Joint Conferences on Artificial Intelligence, 2020. pp. 1134-1140
Bibtex
@inproceedings{8ceb380665e84f0484d7c852cf2ca548,
title = "Subgraph Isomorphism Meets Cutting Planes: Solving With Certified Solutions",
abstract = "Modern subgraph isomorphism solvers carry out sophisticated reasoning using graph invariants such as degree sequences and path counts. We show that all of this reasoning can be justified compactly using the cutting planes proofs studied in complexity theory. This allows us to extend a state of the art subgraph isomorphism enumeration solver with proof logging support, so that the solutions it outputs may be audited and verified for correctness and completeness by a simple third party tool which knows nothing about graph theory.",
author = "Stephan Gocht and Ciaran McCreesh and Jakob Nordstr{\"o}m",
year = "2020",
month = jul,
day = "1",
doi = "10.24963/ijcai.2020/158",
language = "English",
pages = "1134--1140",
booktitle = "Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI '20)",
publisher = "International Joint Conferences on Artificial Intelligence",
note = "29th International Joint Conference on Artificial Intelligence (IJCAI-20) ; Conference date: 07-01-2021 Through 15-01-2021",
}
RIS
TY - GEN
T1 - Subgraph Isomorphism Meets Cutting Planes
T2 - 29th International Joint Conference on Artificial Intelligence (IJCAI-20)
AU - Gocht, Stephan
AU - McCreesh, Ciaran
AU - Nordström, Jakob
PY - 2020/7/1
Y1 - 2020/7/1
N2 - Modern subgraph isomorphism solvers carry out sophisticated reasoning using graph invariants such as degree sequences and path counts. We show that all of this reasoning can be justified compactly using the cutting planes proofs studied in complexity theory. This allows us to extend a state of the art subgraph isomorphism enumeration solver with proof logging support, so that the solutions it outputs may be audited and verified for correctness and completeness by a simple third party tool which knows nothing about graph theory.
AB - Modern subgraph isomorphism solvers carry out sophisticated reasoning using graph invariants such as degree sequences and path counts. We show that all of this reasoning can be justified compactly using the cutting planes proofs studied in complexity theory. This allows us to extend a state of the art subgraph isomorphism enumeration solver with proof logging support, so that the solutions it outputs may be audited and verified for correctness and completeness by a simple third party tool which knows nothing about graph theory.
U2 - 10.24963/ijcai.2020/158
DO - 10.24963/ijcai.2020/158
M3 - Article in proceedings
SP - 1134
EP - 1140
BT - Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI '20)
PB - International Joint Conferences on Artificial Intelligence
Y2 - 7 January 2021 through 15 January 2021
ER -
