Skip to Main content Skip to Navigation
Journal articles

Some Complexity Considerations on the Uniqueness of Solutions for Satisfiability and Colouring Problems

Abstract : 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).
Complete list of metadatas

https://hal.telecom-paris.fr/hal-02287571
Contributor : Telecomparis Hal <>
Submitted on : Friday, September 13, 2019 - 5:06:12 PM
Last modification on : Wednesday, June 24, 2020 - 4:19:54 PM

Identifiers

  • HAL Id : hal-02287571, version 1

Citation

Olivier Hudry, Antoine Lobstein. Some Complexity Considerations on the Uniqueness of Solutions for Satisfiability and Colouring Problems. soumis pour publication, 2019. ⟨hal-02287571⟩

Share

Metrics

Record views

51