Menu
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-DC_r)\) and “Uniqueness of an Optimal \(r\)-Dominating Code” \((U-ODC_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-DC_r\) have complexity equivalent to that of U-SAT (up to polynomials); consequently, these problems are all \(NP\)-hard, and U-VC and \(U-DC_r\) belong to the class \(DP\).