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-paristech.fr/hal-02287571
Contributor : Telecomparis Hal <>
Submitted on : Friday, September 13, 2019 - 5:06:12 PM
Last modification on : Thursday, October 17, 2019 - 12:37:00 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, 2017. ⟨hal-02287571⟩

Share

Metrics

Record views

9