On the Complexity of Coloring Reflexive \(h\)-ary Relations with Given Permutation Group

The following problem, known as the Strong Coloring Problem for the group \(G\) (SCP\(_G\)) is investigated for various permutation groups \(G\). Let \(G\) be a subgroup of \(S_h\), the symmetric group on \(\{0, \ldots, h-1\}\). An instance of SCP\(_G\) is an \(h\)-ary areflexive relation \(\rho\) whose group of symmetry is \(G\) and the question is “does \(\rho\) have a strong \(h\)-coloring”? Let \(m \geq 3\) and \(D_m\) be the Dihedral group of order \(m\). We show that SCP\(_{D_m}\) is polynomial for \(m = 4\), and NP-complete otherwise. We also show that the Strong Coloring Problem for the wreath product of \(H\) and \(K\) is in \( {P}\) whenever both SCP\(_H\) and SCP\(_K\) are in \( {P}\). This, together with the algorithm for \(D_4\) yields an infinite new class of polynomially solvable cases of SCP\(_G\).