The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzażewski Conjecture
Résumé
In this paper we are interested in the fine-grained complexity of deciding whether there is an homomorphism from an input graph G to a fixed graph H (the H-Coloring problem). The starting point is that these problems can be viewed as constraint satisfaction problems (Csp s), and that (partial) polymorphisms of binary relations are of paramount importance in the study of complexity classes of such Csp s.
Thus, we first investigate the expressivity of binary symmetric relations E_H and their corresponding (partial) polymorphisms pPol(E_H). For irreflexive graphs we observe that there is no pair of graphs H and H' such that pPol(E_H) \subseteq \pPol(E_{H'}), unless E_{H'}=\emptyset or H =H'. More generally we show the existence of an n-ary relation R whose partial polymorphisms strictly subsume those of H and such that Csp(R) is NP-complete if and only if H contains an odd cycle of length at most n.
Motivated by this we also describe the sets of total polymorphisms of nontrivial cliques, odd cycles, as well as certain cores, and we give an algebraic characterization of projective cores.
As a by-product, we settle the Okrasa and Rz\c ażewski conjecture for all graphs of at most 7 vertices.
Origine : Fichiers produits par l'(les) auteur(s)
