Charles Explorer logo
🇬🇧

SMALL PROMISE CSPS THAT REDUCE TO LARGE CSPS

Publication at Faculty of Mathematics and Physics |
2022

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].