[Back]

R. Ganian, M. S. Ramanujan, S. Szeider:
"Backdoors to Tractable Valued CSP";
Talk: International Conference on Principles and Practice of Constraint Programming (CP), Toulouse, Frankreich; 2016-09-05 - 2016-09-09; in: "Principles and Practice of Constraint Programming (Proceedings of 22nd CP)", LNCS, 9898 (2016), ISBN: 978-3-319-44952-4; 233 - 250.

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.

http://publik.tuwien.ac.at/files/publik_254611.pdf