Some Complexity Considerations on the Uniqueness of Graph Colouring

Olivier Hudry (1, 2) , Antoine Lobstein (1, 2, 3)

1 MC2 - Mathématiques discrètes, Codage et Cryptographie
2 INFRES - Département Informatique et Réseaux
3 GALaC - Graphes, Algorithmes et Combinatoire - LISN

For some well-known NP-complete problems, linked to the satisfiability of Boolean formulas and the colourability of a graph, we study the variation which consists in asking about the uniqueness of a solution. In particular, we show that five decision problems, Unique Satisfiability (U-SAT), Unique k-Satisfiability (U-k-SAT), k ≥ 3, Unique One-in-Three Satisfiability (U-1-3-SAT), Unique k-Colouring (U-k-COL), k ≥ 3, and Unique Colouring (U-COL), have equivalent complexities, up to polynomials —when dealing with colourings, we forbid permutations of colours. As a consequence, all are NP-hard and belong to the class DP. We also consider the problems U-2-SAT, U-2-COL and Unique Optimal Colouring (U-OCOL).

Keywords: Complexity Theory; Polynomial Reduction; Uniqueness of Solution; Boolean Satisfiability; Graph Theory; Graph Colourings

Domains: Computational Complexity [cs.CC]; Discrete Mathematics [cs.DM]; Operations Research [math.OC]; Combinatorics [math.CO]

Olivier Hudry, Antoine Lobstein. Some Complexity Considerations on the Uniqueness of Graph Colouring. WSEAS Transactions on Mathematics, 2023, 22, pp.art. #54, 483-493. ⟨hal-02287571⟩