MVLSC Home · Issue Contents · Forthcoming Papers
The Complexity of Promise Constraint Satisfaction Problem Seen from the Other Side
Kristina Asimi, Libor Barto and Victor Dalmau
We introduce the framework of the left-hand side restricted promise constraint satisfaction problem, which includes problems like approximating clique number of a graph.We study the parameterized complexity of problems in this class and provide some initial results. The main technical contribution is a sufficient condition for W[1]-hardness which, in particular, covers left-hand side restricted bounded arity CSPs.
Keywords: Constraint satisfaction problem, promise constraint satisfaction problem, computational complexity, parameterized complexity, approximating clique, homomorphisms