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 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.
| Original language | English |
|---|---|
| Pages (from-to) | 217-240 |
| Number of pages | 24 |
| Journal | Journal of Combinatorial Mathematics and Combinatorial Computing |
| Volume | 110 |
| Publication status | Published - 1 Aug 2019 |
| Externally published | Yes |
Keywords
- Boolean Satisfiability Problems
- Complexity Theory
- Decision Problems
- Dominating Codes
- Domination
- Graph Theory
- JVP-Hardness
- Polynomial Reduction
- Uniqueness of (Optimal) Solution
- Vertex Covers