On the complexity of coloring areflexive \(h\)-ary relations with given permutation group (Q2715944)

Let \(G\) be a group of permutations of \(\{0,1,\ldots ,h-1\}\) and let \(\rho \) be an areflexive \(h\)-ary relation on a set \(A\). We call \(G\) the symmetry group of \(\rho \) if \(\rho =\rho ^{(\pi)}\) for every \(\pi \in G\) and \(\rho \cap \rho ^{(\pi)}=\emptyset \) for every \(\pi \not \in G\), where \(\rho ^{(\pi)}=\{(x_{\pi (0)},x_{\pi (1)},\ldots ,x_{\pi (h-1)}): (x_0,x_1,\ldots ,x_{h-1})\in \rho \}\). In such a case the model of \(\rho \) is the \(h\)-ary relation \(M_{\rho}=\{(\pi (0),\pi (1),\ldots ,\pi (h-1)):\pi \in G\}\) on \(\{0,1,\ldots ,h-1\}\). A strong \(h\)-coloring of \(\rho \) is a relational homomorphism \(\phi :\rho \rightarrow M_{\rho}\) (i.e., a mapping \(\phi :A\rightarrow \{0,1,\ldots ,h-1\}\) such that \((\phi (x_0),\ldots ,\phi (x_{h-1}))\in M_{\rho}\) for every \((x_0,\ldots ,x_{h-1})\in \rho \)). NEWLINENEWLINENEWLINEThe paper is devoted to the study of the computational complexity of the problem ``Given an \(h\)-ary areflexive relation \(\rho \) whose symmetry group is \(G\), does \(\rho \) have a strong \(h\)-coloring?'' with input \(\rho \) and parameter \(G\). It is shown that for \(G=D_m\), the dihedral group of order \(m\geq 3\), the problem is polynomially solvable for \(m=4\) and NP-complete otherwise. It is also shown that if the strong coloring problem is polynomial for groups \(H\) and \(K\), then so it is for the wreath product of \(H\) and \(K\). This, together with the algorithm for \(D_4\) yields an infinite new class of polynomially solvable strong coloring problems.