The Complexity of Promise Constraint Satisfaction Problem Seen from the Other Side
<|reference_start|>The Complexity of Promise Constraint Satisfaction Problem Seen from the Other Side: 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.<|reference_end|>
@article{asimi2024the,
    title={The Complexity of Promise Constraint Satisfaction Problem Seen from the
  Other Side},
    author={Kristina Asimi, Libor Barto, Victor Dalmau},
    journal={arXiv preprint arXiv:2402.06821},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.06821},
    primaryClass={cs.CC}
}