Back to Search
Start Over
Backdoors to Tractable Valued CSP
- Publication Year :
- 2016
- Publisher :
- arXiv, 2016.
-
Abstract
- We extend the notion of a strong backdoor from the CSP setting to the Valued CSP setting (VCSP, for short). This provides a means for augmenting a class of tractable VCSP instances to instances that are outside the class but of small distance to the class, where the distance is measured in terms of the size of a smallest backdoor. We establish that VCSP is fixed-parameter tractable when parameterized by the size of a smallest backdoor into every tractable class of VCSP instances characterized by a (possibly infinite) tractable valued constraint language of finite arity and finite domain. We further extend this fixed-parameter tractability result to so-called "scattered classes" of VCSP instances where each connected component may belong to a different tractable class.<br />Comment: Accepted to CP 2016
Details
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....bf42e3289aafcd6ce3852e2865f0691d
- Full Text :
- https://doi.org/10.48550/arxiv.1612.05733