Abstract
For relational structures A, B of the same signature, the Promise Constraint Satisfaction Problem PCSP(A, B) asks whether a given input structure maps homomorphically to A or does not even map to B. We are promised that the input satisfies exactly one of these two cases.
If there exists a structure C with homomorphisms A -> C -> B, then PCSP(A, B) reduces naturally to CSP(C). To the best of our knowledge all known tractable PCSPs reduce to tractable CSPs in this way.
However Barto [Bar19] showed that some PCSPs over finite structures A, B require solving CSPs over infinite C. We show that even when such a reduction to some finite C is possible, this structure may become arbitrarily large.
For every integer n > 1 and every prime p we give A, B of size n with a single relation of arity n(p) such that PCSP(A, B) reduces via a chain of homomorphisms A -> C -> B to a tractable CSP over some C of size p but not over any smaller structure. In a second family of examples, for every prime p >= 7 we construct A, B of size p - 1 with a single ternary relation such that PCSP(A, B) reduces via A -> C -> B to a tractable CSP over some C of size p but not over any smaller structure.
In contrast we show that if A, B are graphs and PCSP(A, B) reduces to a tractable CSP(C) for some finite digraph C, then already A or B has a tractable CSP. This extends results and answers a question of [DSM(+)21].