The Isolation lemma of Mulmuley, Vazirani, and Vazirani can be used to show that certain $\mathsf{NP}$-complete problems can be reduced via randomized polytime reductions to the unique solution version of the problem. This hints that the promise of a unique solution is not likely to make the problem significantly easier.

A specific example for such a reduction in the Mulmuley, Vazirani, and Vazirani paper (pdf) is that CLIQUE can be reduced to UNIQUE CLIQUE via randomized polynomial time reductions. In this sense, UNIQUE CLIQUE is (almost) as hard as CLIQUE.

Is there anything similar known about the UNIQUE $k$-COLORABILITY of graphs?

It is worth noting that the promise of unique colorability seems to involve more structural consequences than the uniqueness of the maximum clique.

  • 7
    $\begingroup$ sciencedirect.com/science/article/pii/S030439750400115X $\endgroup$ – Austin Buchanan Apr 27 '14 at 5:58
  • 1
    $\begingroup$ Thank you, the linked paper provides an interesting answer. $\endgroup$ – Andras Farago Apr 27 '14 at 15:51
  • $\begingroup$ @AndrasFarago From the reference so $PLAN-3-COL$ problems are essentially to distinguish $3$ colorability from $4$ colorability since we have a parsimonious reduction? $\endgroup$ – 1.. May 26 '19 at 23:23
  • $\begingroup$ @AustinBuchanan: Post as an answer? $\endgroup$ – Joshua Grochow Apr 21 at 17:46

This paper by Régis Barbanchon might be of interest. From the abstract:

We prove that the Satisfiability (resp. planar Satisfiability) problem is parsimoniously P-time reducible to the 3-Colorability (resp. Planar 3-Colorability) problem, that means that the exact number of solutions is preserved by the reduction, provided that 3-colorings are counted modulo their six trivial color permutations. In particular, the uniqueness of solutions is preserved, which implies that Unique 3-Colorability is exactly as hard as Unique Satisfiability in the general case as well as in the planar case...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.