Talks and Poster Presentations (with Proceedings-Entry):
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.
English 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.
Electronic version of the publication:
http://publik.tuwien.ac.at/files/publik_254611.pdf
Created from the Publication Database of the Vienna University of Technology.