Three equalities connecting four variables imply all six pairwise equalities. Densification adds the implied constraints; sparsification keeps a sufficient basis. This toy example preserves exactly the assignments in which all four values agree. Research source
About this paper
An algebraic study of adding implied constraints and finding compact equivalent descriptions of CSP instances.
A densification operator generates every constraint satisfied by all solutions. Implicational systems connect this closure operation to sparsification, and the Boolean case is characterized using bounded-width constraint languages.
Citation
BibTeX
@article{takhanov2022cspdensificationsparsification,
title = {The algebraic structure of the densification and the sparsification tasks for CSPs},
author = {Takhanov, Rustem},
year = {2022},
journal = {Constraints},
eprint = {2104.05065},
archivePrefix = {arXiv},
url = {https://arxiv.org/pdf/2104.05065}
}