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.
No takes yet. Share an insight, caveat, or question.
Asimi et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: