Informace o publikaci
Backdoors to Tractable Valued CSP
| Autoři | |
|---|---|
| Rok publikování | 2016 |
| Druh | Článek ve sborníku |
| Konference | PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING, CP 2016 |
| Fakulta / Pracoviště MU | |
| Citace | |
| Doi | http://dx.doi.org/10.1007/978-3-319-44953-1_16 |
| Obor | Informatika |
| Klíčová slova | CSP; backdoors |
| Popis | 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. |