Classification of the existence of gadget reductions between some Promise CSP's

Sammanfattning

A fundamental goal of computer science is to understand the complexity of computational problems. One class of problems are promise constraint satisfaction problems (PCSP's). We study PCSP's related to graph coloring, linearly ordered coloring (LO-coloring) and rainbow coloring. We first dive into graph coloring PCSP's and classify the non-existence of certain gadget reductions between such problems. Next we systematically classify the existence gadget reductions between PCSP's related to graph coloring and LO-coloring and between PCSP's related to graph coloring and rainbow coloring that could yield new complexity results. For the most part these gadget reductions are shown to be non-existent. We do however prove the existence of a reduction from PCSP($\K_l,\K_k$) to PCSP($\LO_l^r,\LO_k^r$) for $k\geq l\geq 3$ and $r\geq 4$ yielding a substantial number of new NP-hardness results for PCSP($\LO_l^r,\LO_k^r$).