1
$\begingroup$

I need to prove, that the $\#k-colouring$ graph problem is $\#P-complete$. I want to construct the reduction from $\#3SAT$ problem, so $\#3SAT \leq \#k-colouring$. The reduction between the counting problems consists of two parts. The first one maps instances of the first problem to the instance of the second problem (the same as within the reduction at decision problem) and the second part has to recover the number of solutions between the relevant problems.

For counting problems, there is a special type of reductions, called parsimonious reduction, where is the number of solutions identical. I read that for all known natural NP-complete problems, there is a parsimonious reduction from $3SAT$. However, consider $ 3-colouring $ graph problem, then the solutions come in groups of 6 since you can always permute the individual colours.

Will be the reduction $\#3SAT \leq \#k-colouring$ parsimonious or not? If yes, how to construct such reduction to prove that the number of solutions is identical and if not, how is the relationship between the number of solutions within both counting problems with respect to the $k$?

Improve this question
$\endgroup$
2
  • $\begingroup$ As you explain, the number of solutions to 3-coloring is always a multiple of 6, which is not the case for 3SAT. So I'm not sure what you're aiming at. The reduction is still morally parsimonious, up to this minor issue. Also, you can break the symmetry by choosing some edge $(x,y)$ and fixing the colors of $x$ and $y$ (this results in a modified 3-coloring problem). $\endgroup$ – Yuval Filmus May 4 '20 at 15:32
  • $\begingroup$ I am not sure whether at proposed reduction will be valid, that one satisfying assignment of formula in $3SAT$ will respond to the six solutions in the $3-colouring$, or there is some another relationship between both instantiates. Alternatively, how the relationship would be at the different value $k$ in the $k-colouring$ problem. For example, at $ 4-colouring $ will be 24 solutions to the one satisfying assignment, or I thinking badly? In general, how relationship there is with respect to the $k$. $\endgroup$ – Danielle Favre May 4 '20 at 15:43

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.