Adam Steif: Classification of the existence of gadget reductions between some Promise CSP’s

Abstract

A fundamental goal of computer science is to understand the complexity of computational problems. One class of problems are promise constraint satisfaction problems (\(\mathsf{PCSP}\)’s). We study \(\mathsf{PCSP}\)’s related to graph coloring, linearly ordered coloring (\(\mathsf{LO}\)-coloring) and rainbow coloring. We first dive into graph coloring \(\mathsf{PCSP}\)’s and classify the non-existence of certain gadget reductions between such problems. Next we systematically classify the existence gadget reductions between \(\mathsf{PCSP}\)’s related to graph coloring and \(\mathsf{LO}\)-coloring and between \(\mathsf{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 did however prove the existence of a reduction from \(\mathsf{PCSP}(K_l,K_k)\) to \(\mathsf{PCSP}(\mathsf{LO}^r_l, \mathsf{LO}^r_k)\) for \(k \ge l \ge 3\) and \(r \ge 4\) yielding a substantial number of new \(\mathsf{NP}\)-hardness results for \(\mathsf{PCSP}(\mathsf{LO}^r_l, \mathsf{LO}^r_k)\).