Open AccessReconstructing in the Constraint Satisfaction Problem
Author(s) -
Evgeny Dantsin
Publication year - 2020
Publication title -
epic series in computing
Language(s) - English
Resource type - Conference proceedings
ISSN - 2398-7340
DOI - 10.29007/1j7l
Subject(s) - conjecture , homomorphism , graph homomorphism , mathematics , combinatorics , constraint satisfaction problem , isomorphism (crystallography) , vertex (graph theory) , graph isomorphism , discrete mathematics , graph , line graph , graph power , statistics , chemistry , probabilistic logic , crystal structure , crystallography
It is a long-standing problem in graph theory to prove or disprove the \emph{reconstruction conjecture}, also known as the Kelly-Ulam conjecture. This conjecture states that every simple graph on at least three vertices is \emph{reconstructible}, which means that the isomorphism class of such a graph is uniquely determined by the isomorphism classes of its vertex-deleted subgraphs. In this talk, the notion of reconstructing is extended from graphs to instances of the constraint satisfaction problem (CSP): an instance is \emph{reconstructible} if its isomorphism class is uniquely determined by the isomorphism classes of its constraint-deleted subinstances. Questions of interest include not only questions about reconstructible CSP instances but also about CSP instances with reconstructible properties and parameters such as the existence of solutions or the number of solutions. As shown in the talk, such questions can be answered using techniques borrowed and adapted from graph reconstruction. In particular, Lov\'{a}sz's method of counting graph homomorphisms \cite{Lov72} is adapted to characterize CSP instances for which the number of solutions is reconstructible.