<p>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 (<a href="http://dx.doi.org/10.1145/2528400" rel="noreferrer">Bulatov JACM'13</a>), later  simplified by Dyer and Richerby (<a href="https://doi.org/10.1137/100811258" rel="noreferrer">Dyer and Richerby SICOMP'13</a>). 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. </p>

<p>If I remember correctly, the required result (the necessity of a Mal'tserv polymorphism for tractability of #CSP) is probably established already in <a href="https://doi.org/10.1016/j.ic.2006.09.005" rel="noreferrer">Bulatov and Dalmau IC'07</a> but you may find the other two papers also useful.</p>

CC BY-SA 4.0
2019-09-03T13:53:29.813Z
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).
M.Monet
CC BY-SA 4.0
2019-09-05T14:02:07.140Z
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.
Standa Zivny
CC BY-SA 4.0
2019-08-29T08:23:24.223Z
2019-08-29T08:23:24.223Z
Standa Zivny
<p>Given a graph <span class="math-container">$G=(V,E)$</span>, what I call an <em>improper <span class="math-container">$3$</span>-coloring of <span class="math-container">$G$</span></em> is simply a function <span class="math-container">$c:V \to \{1,2,3\}$</span>. I say that <span class="math-container">$c$</span> is <span class="math-container">$1$</span>-<span class="math-container">$2$</span>-avoiding when
there do not exist two adjacent nodes <span class="math-container">$u,v$</span> with <span class="math-container">$c(u)=1$</span> and <span class="math-container">$c(v)=2$</span>. I am interested in the problem that takes as input a graph and counts the number of <span class="math-container">$1$</span>-<span class="math-container">$2$</span>-avoiding improper <span class="math-container">$3$</span>-colorings of <span class="math-container">$G$</span>. Or equivalently, this is the number of pairs of disjoint node subsets <span class="math-container">$(S,S')$</span> that are not adjacent (in the sense that <span class="math-container">$E \cap (S\times S') = \emptyset$</span>).</p>

<p><strong>Question:</strong> has this problem already been studied? It is obviously in the complexity class <a href="https://en.wikipedia.org/wiki/%E2%99%AFP" rel="nofollow noreferrer">#P</a>, but is it also #P-hard?</p>

<reference-request><counting-complexity>
Counting avoiding improper 3-colorings
M.Monet
# Counting avoiding improper 3-colorings

(Asked by: username_0 on 2019-08-23)

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](https://en.wikipedia.org/wiki/%E2%99%AFP), but is it also #P-hard?

**Tags:** reference-request, counting-complexity


---

## 1 answers

### Answer by username_1 on 2019-08-29. Score: 8 | Accepted answer

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](http://dx.doi.org/10.1145/2528400)), later simplified by Dyer and Richerby ([Dyer and Richerby SICOMP'13](https://doi.org/10.1137/100811258)). 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](https://doi.org/10.1016/j.ic.2006.09.005) but you may find the other two papers also useful.

> **Comments:**
> **username_0**: 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).  
> **username_1**: 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.  

---

