Given a graph $G=(V,E)$, what I call an improper $3$-coloring of $G$ is simply a function $c:V \to \{1,2,3\}$. I say that $c$ is $1$-$2$-avoiding when there do not exist two adjacent nodes $u,v$ with $c(u)=1$ and $c(v)=2$. I am interested in the problem that takes as input a graph and counts the number of $1$-$2$-avoiding improper $3$-colorings of $G$. Or equivalently, this is the number of pairs of disjoint node subsets $(S,S')$ that are not adjacent (in the sense that $E \cap (S\times S') = \emptyset$).

Question: has this problem already been studied? It is obviously in the complexity class #P, but is it also #P-hard?


1 Answer 1


I don't know whether this problem has been studied but I think its #P-hardness should follow directly from the #CSP dichotomy established by Bulatov (Bulatov JACM'13), later simplified by Dyer and Richerby (Dyer and Richerby SICOMP'13). In particular, your problem is equivalent to a CSP with a constraint language on the domain D := {1,2,3} with a single binary relation R in the language defined by R := D^2 \ {(1,2),(2,1)}; i.e., all tuples but (1,2) and (2,1) are allowed. A necessary (but not sufficient) condition for tractability is admitting a Mal'tsev polymorphism, which is a ternary operation f:D^3 -> D satisfying, for all a,b in D, f(a,b,b)=f(b,b,a)=a and preserving membership in R. If you take tuples (1,3), (3,3), and (3,2), they all belong to R but any Mal'tsev polymorphism would have to return (1,2) as 1=f(1,3,3) and 2=f(3,3,2) [applying f on the columns if viewing the tuples as rows of a 3x2 matrix]. However, (1,2) is not in R, which is a contradiction.

If I remember correctly, the required result (the necessity of a Mal'tserv polymorphism for tractability of #CSP) is probably established already in Bulatov and Dalmau IC'07 but you may find the other two papers also useful.

  • 1
    $\begingroup$ Indeed, thanks! In the end I managed to show hardness of the problem that I wanted (which is a variant of that one). I mark your answer as accepted, as it is true that one should be able to answer my question by reading these dichotomy papers (although I guess that you'd have to spend some time to determine if that particular constraint is tractable or #P-hard). $\endgroup$
    – M.Monet
    Sep 3, 2019 at 13:53
  • 1
    $\begingroup$ Hopefully you find my simple reasoning how to derive the result from the dichotomy theorem useful for future problems. These dichotomy theorems are incredibly powerful but indeed it's not always easy to derive consequence without reading the paper(s) in detail. $\endgroup$ Sep 5, 2019 at 14:02

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.