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$ – T.... May 26 '19 at 23:23

Your Answer

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

Browse other questions tagged or ask your own question.