The Complexity of Promise Constraint Satisfaction Problem Seen from the Other Side

Autor:	Asimi, Kristina, Barto, Libor, Dalmau, Victor
Rok vydání:	2024
Předmět:	Computer Science - Computational Complexity
Druh dokumentu:	Working Paper
Popis:	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.
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2402.06821 Zobrazit plný text záznamu View this record from Arxiv