10
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 7
    $\begingroup$ sciencedirect.com/science/article/pii/S030439750400115X $\endgroup$
    – Austin Buchanan
    Commented Apr 27, 2014 at 5:58
  • 1
    $\begingroup$ Thank you, the linked paper provides an interesting answer. $\endgroup$
    – Andras Farago
    Commented Apr 27, 2014 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$
    – Turbo
    Commented May 26, 2019 at 23:23
  • $\begingroup$ @AustinBuchanan: Post as an answer? $\endgroup$
    – Joshua Grochow
    Commented Apr 21, 2021 at 17:46

1 Answer 1

Reset to default
3
$\begingroup$

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...

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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