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

Abstract

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\ge 1,$ “Uniqueness of an $r$-Dominating Code with bounded size” $(U-D{C}_r)$ and “Uniqueness of an Optimal $r$-Dominating Code” $(U-OD{C}_r$. 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-ODC, We prove that U-VC and $U-D{C}_r$ have complexity equivalent to that of U-SAT (up to polynomials); consequently, these problems are all $NP$-hard, and U-VC and $U-D{C}_r$ belong to the class $DP$.