Complexity of Unique (Optimal) Solutions in Graphs: Vertex Cover and Domination

We study the complexity of four decision problems dealing with the uniqueness of a solution in a graph: âœUniqueness of a Vertex Cover with bounded sizeâ?(U-VC) and âœUniqueness of an Optimal Vertex Coverâ? (U-OVC), and for any fixed integer r 1, âœUniqueness of an r-Dominating Code with bounded sizeâ? (U-DCr) and âœUniqueness of an Optimal r-Dominating Codeâ? (U-ODCr). In particular, we give a polynomial reduction from âœUnique Satisfiability of a Boolean formulaâ? (U-SAT) to U-OVC, and from U-SAT to U-ODCr. We prove that U-VC and U-DCr have complexity equivalent to that of U-SAT (up to polynomials); consequently, these problems are all MP-hard, and U-VC and U-DCr belong to the class DP.