A toy coloring problem separates the shape of an input instance from its allowed relations. Hybrid CSPs restrict both sides; the paper studies which structural restrictions can change the complexity of the resulting problem. Research source
About this paper
Characterizes when structural restrictions can make an otherwise hard constraint satisfaction problem tractable.
The hybrid setting restricts both the instance structure and the allowed constraint language. Lifted languages connect this setting to algebraic CSP methods, yielding characterizations for several families of structural restrictions.
Citation
BibTeX
@inproceedings{takhanov2015hybridcspstructuralrestrictions,
title = {Effectiveness of Structural Restrictions for Hybrid CSPs},
author = {Kolmogorov, Vladimir and Rolinek, Michal and Takhanov, Rustem},
year = {2015},
booktitle = {ISAAC 2015},
eprint = {1504.07067},
archivePrefix = {arXiv},
url = {https://arxiv.org/pdf/1504.07067}
}