<p>The problem is NP-complete by a reduction from <a href="https://en.wikipedia.org/wiki/Not-all-equal_3-satisfiability" rel="nofollow noreferrer">not-all-equal 3-satisfiability</a> (NAE3SAT):</p>
<p>Let
<span class="math-container">$$\Phi = \bigwedge_{i=1}^n (l_{i,1} \lor l_{i,2} \lor l_{i,3})$$</span>
be an instance of NAE3SAT.</p>
<p>We construct a graph with one vertex for each literal of <span class="math-container">$\Phi$</span> and one extra vertex <span class="math-container">$l_{i,4}$</span> for each clause of <span class="math-container">$\Phi$</span>.
For <span class="math-container">$i=1,\dots,n$</span> the four vertices <span class="math-container">$\{l_{i,1}, l_{i,2}, l_{i,3}, l_{i,4}\}$</span> form the subsets for the second condition.
Two vertices are connected by an edge if their corresponding literals are the negation of each other.</p>
<hr />
<p><strong>EDIT:</strong> For each variable that appears only without negations (or the other way around: always with negation) we add another vertex to the graph and connect all vertices corresponding to literals of this variable to the additional vertex.
Then, in any two coloring, all vertices corresponding to literals of this variable have the same color (i.e. same truth value).</p>
<hr />
<p>Now, there exists two coloring of this graph that satisfies the second condition if and only if the NAE3SAT instance has a solution:</p>
<ul>
<li>The two coloring corresponds to the fact that each no to literals that are negations of one another can have the same truth value.</li>
<li>The second condition is equivalent to the condition that every clause has either one or two true values.</li>
</ul>
<p>The extra vertices <span class="math-container">$l_{i,4}$</span> are only necessary to create a graph that fits the description.
So OPs problem remains NP-complete if <span class="math-container">$|V|=3n$</span> and the second condition is replaced by</p>
<p>&quot;For every vertex subset <span class="math-container">$\{1,2,3\}, \{4, 5, 6\},\dots,\{3n-2,3n-1,3n\}$</span> either one or two vertices are colored red&quot;.</p>
<p>As I have stated in the comment to the question, the problem can be solved by BFS if the graph is connected.</p>
<p>For an example, let <span class="math-container">$\Phi = (a \lor b \lor c) \land (b \lor c \lor d) \land (\bar{a} \lor \bar{b} \lor d) \land (a \lor \bar{c} \lor \bar{d})$</span> be a NAE3SAT instances with variable <span class="math-container">$a,b,c,d$</span>.
A feasible solution to this instance is <span class="math-container">$(a,b,\bar{c},d)$</span> and the corresponding two coloring is depicted below.</p>
<p><a href="https://i.sstatic.net/82CRfoBT.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/82CRfoBT.png" alt="Example" /></a></p>

CC BY-SA 4.0
2024-07-12T04:08:28.480Z
Thanks for your nice construction! I guess if there are variables that appear only without negations (or the other way around: always with negation) then I guess you just need to add an anti-clause $(a, b, c)$ -> $(\bar{a}, \bar{b}, \bar{c})$ and that will fix the problem.
Jun_Gitef17
CC BY-SA 4.0
2024-07-12T08:16:25.660Z
Yes, you are right. Alternatively one can add an auxiliary node to the graph and connect all respective variables to that node to ensure that they get the same color.
badboul
CC BY-SA 4.0
2024-07-25T05:11:37.383Z
Thank you again, badboul! As I wrote in the comments of the OP, this question stemmed from a totally physical context about classically simulating quantum systems. I finally got an NP-completeness proof for that original problem last night :) Although this 2-in-4 SAT did NOT directly kick in to the final proof, the fact that this 2in4 SAT is indeed NP-hard (ie your answer here) greatly encouraged me to explore the direction in general, which ultimately led to the proof. I think it's appropriate to acknowledge you in the final paper (it'll probably take a few months). What do you think?
Jun_Gitef17
CC BY-SA 4.0
2024-07-11T13:25:45.020Z
2024-07-12T08:22:58.993Z
2024-07-12T08:22:58.993Z
badboul
<p>I am considering the following problem:</p>
<p>Given a graph <span class="math-container">$G=(V,E)$</span> with <span class="math-container">$|V|=4n$</span> vertices, can we color the vertices in two colors (red and blue) with</p>
<ol>
<li>The usual constraint that two vertices connected by an edge must always have different colors AND</li>
<li>The additional constraint that for all of the following vertex subsets: <span class="math-container">$\{1,2,3,4\},
    \{5,6,7,8\}, \ldots, \{4n-3,4n-2,4n-1,4n\}$</span>, exactly two vertices are colored red (and thus exactly two are blue)?</li>
</ol>
<p>I think this problem has two flavors. On one hand it's obviously the &quot;bit more constrained version&quot; of 2-coloring, which makes me feel that this problem could be in <span class="math-container">$\mathsf{P}$</span> because 2-coloring is. On the other hand, the &quot;exactly two colors&quot; constraint looks like a generic 4-SAT-like relation that in the general case creates an <span class="math-container">$\mathsf{NP}$</span>-hard constraint satisfaction problem from Schaefer's dichotomy theorem.</p>
<p>Because of this intermediate nature, I feel like maybe this kind of problem is well studied even. Can anybody come up with a <span class="math-container">$\mathsf{P}$</span> or <span class="math-container">$\mathsf{NP}$</span>-hardness proof, or point to some literature concerning this kind of problem? It's quite hard to search for these weird variant problems without knowing their name...
I understand that it's a bit similar to problems that were discussed <a href="https://cstheory.stackexchange.com/questions/53555/balanced-set-coloring">here</a> and <a href="https://cstheory.stackexchange.com/questions/51980/graph-coloring-with-limit-on-number-of-times-a-color-is-used">there</a>, but I don't see an obvious reduction.</p>
<p>I am actually interested in the more general case where we group the vertices into non-overlapping subsets of size <span class="math-container">$2k$</span>, where each subsets need to have exactly <span class="math-container">$k$</span> reds. The case of <span class="math-container">$k=1$</span> is easily seen to be in <span class="math-container">$\mathsf{P}$</span>, because it is essentially 2-SAT. The problem I wrote above corresponds to the case of <span class="math-container">$k=2$</span>, which is the smallest case I cannot prove either way.</p>

CC BY-SA 4.0
2024-07-10T20:26:10.767Z
What's the motivation for this problem?  What's the context in which you encountered it, or the original source where you saw it?
D.W.
CC BY-SA 4.0
2024-07-11T04:47:54.163Z
It actually came up as I was trying to understand the complexity of a completely different problem: Negative-sign problem curing for quantum Monte Carlo methods (see eg https://www.nature.com/articles/s41467-019-09501-6 ). There could be many different set ups where you can ask similar questions as the one addressed in the paper, and in one case, it occurred to me that it could (potentially) be reduced from this 2-coloring variant. That original sign-curing <- 2-coloring reduction was a whole additional baggage and I didn't want to get into that.
Jun_Gitef17
CC BY-SA 4.0
2024-07-11T09:07:32.973Z
To test whether a graph is bipartite one can simply assign a color to a random start vertex and from there on color the remaining vertices by BFS. Then one can check whether the second condition is satisfied.

However, this only works if the graph is connected and all vertices are colored by the BFS. If iy is not connected then one can apply this procedure to each component individually.
Now it remains to check if one can flip the colorings of the components such that the second condition is satisfied. 
This seems like some form of an exact cover problem which to me sounds NP-complete.
badboul
<cc.complexity-theory><np-hardness><graph-colouring>
Complexity of 2-coloring with extra constraints
Jun_Gitef17
# Complexity of 2-coloring with extra constraints

(Asked by: username_0 on 2024-07-10)

I am considering the following problem:

Given a graph $G=(V,E)$ with $|V|=4n$ vertices, can we color the vertices in two colors (red and blue) with

1. The usual constraint that two vertices connected by an edge must always have different colors AND
2. The additional constraint that for all of the following vertex subsets: $\{1,2,3,4\},
   \{5,6,7,8\}, \ldots, \{4n-3,4n-2,4n-1,4n\}$, exactly two vertices are colored red (and thus exactly two are blue)?

I think this problem has two flavors. On one hand it's obviously the "bit more constrained version" of 2-coloring, which makes me feel that this problem could be in $\mathsf{P}$ because 2-coloring is. On the other hand, the "exactly two colors" constraint looks like a generic 4-SAT-like relation that in the general case creates an $\mathsf{NP}$-hard constraint satisfaction problem from Schaefer's dichotomy theorem.

Because of this intermediate nature, I feel like maybe this kind of problem is well studied even. Can anybody come up with a $\mathsf{P}$ or $\mathsf{NP}$-hardness proof, or point to some literature concerning this kind of problem? It's quite hard to search for these weird variant problems without knowing their name...
I understand that it's a bit similar to problems that were discussed [here](https://cstheory.stackexchange.com/questions/53555/balanced-set-coloring) and [there](https://cstheory.stackexchange.com/questions/51980/graph-coloring-with-limit-on-number-of-times-a-color-is-used), but I don't see an obvious reduction.

I am actually interested in the more general case where we group the vertices into non-overlapping subsets of size $2k$, where each subsets need to have exactly $k$ reds. The case of $k=1$ is easily seen to be in $\mathsf{P}$, because it is essentially 2-SAT. The problem I wrote above corresponds to the case of $k=2$, which is the smallest case I cannot prove either way.

**Tags:** cc.complexity-theory, np-hardness, graph-colouring

> **Comments:**
> **username_1**: What's the motivation for this problem?  What's the context in which you encountered it, or the original source where you saw it?  
> **username_0**: It actually came up as I was trying to understand the complexity of a completely different problem: Negative-sign problem curing for quantum Monte Carlo methods (see eg https://www.nature.com/articles/s41467-019-09501-6 ). There could be many different set ups where you can ask similar questions as the one addressed in the paper, and in one case, it occurred to me that it could (potentially) be reduced from this 2-coloring variant. That original sign-curing <- 2-coloring reduction was a whole additional baggage and I didn't want to get into that.  
> **username_2**: To test whether a graph is bipartite one can simply assign a color to a random start vertex and from there on color the remaining vertices by BFS. Then one can check whether the second condition is satisfied.  However, this only works if the graph is connected and all vertices are colored by the BFS. If iy is not connected then one can apply this procedure to each component individually. Now it remains to check if one can flip the colorings of the components such that the second condition is satisfied.  This seems like some form of an exact cover problem which to me sounds NP-complete.  

---

## 1 answers

### Answer by username_2 on 2024-07-11. Score: 3 | Accepted answer

The problem is NP-complete by a reduction from [not-all-equal 3-satisfiability](https://en.wikipedia.org/wiki/Not-all-equal_3-satisfiability) (NAE3SAT):

Let
$$\Phi = \bigwedge\_{i=1}^n (l\_{i,1} \lor l\_{i,2} \lor l\_{i,3})$$
be an instance of NAE3SAT.

We construct a graph with one vertex for each literal of $\Phi$ and one extra vertex $l\_{i,4}$ for each clause of $\Phi$.
For $i=1,\dots,n$ the four vertices $\{l\_{i,1}, l\_{i,2}, l\_{i,3}, l\_{i,4}\}$ form the subsets for the second condition.
Two vertices are connected by an edge if their corresponding literals are the negation of each other.

---

**EDIT:** For each variable that appears only without negations (or the other way around: always with negation) we add another vertex to the graph and connect all vertices corresponding to literals of this variable to the additional vertex.
Then, in any two coloring, all vertices corresponding to literals of this variable have the same color (i.e. same truth value).

---

Now, there exists two coloring of this graph that satisfies the second condition if and only if the NAE3SAT instance has a solution:

* The two coloring corresponds to the fact that each no to literals that are negations of one another can have the same truth value.
* The second condition is equivalent to the condition that every clause has either one or two true values.

The extra vertices $l\_{i,4}$ are only necessary to create a graph that fits the description.
So OPs problem remains NP-complete if $|V|=3n$ and the second condition is replaced by

"For every vertex subset $\{1,2,3\}, \{4, 5, 6\},\dots,\{3n-2,3n-1,3n\}$ either one or two vertices are colored red".

As I have stated in the comment to the question, the problem can be solved by BFS if the graph is connected.

For an example, let $\Phi = (a \lor b \lor c) \land (b \lor c \lor d) \land (\bar{a} \lor \bar{b} \lor d) \land (a \lor \bar{c} \lor \bar{d})$ be a NAE3SAT instances with variable $a,b,c,d$.
A feasible solution to this instance is $(a,b,\bar{c},d)$ and the corresponding two coloring is depicted below.

[![Example](https://i.sstatic.net/82CRfoBT.png)](https://i.sstatic.net/82CRfoBT.png)

> **Comments:**
> **username_0**: Thanks for your nice construction! I guess if there are variables that appear only without negations (or the other way around: always with negation) then I guess you just need to add an anti-clause $(a, b, c)$ -> $(\bar{a}, \bar{b}, \bar{c})$ and that will fix the problem.  
> **username_2**: Yes, you are right. Alternatively one can add an auxiliary node to the graph and connect all respective variables to that node to ensure that they get the same color.  
> **username_0**: Thank you again, username_2! As I wrote in the comments of the OP, this question stemmed from a totally physical context about classically simulating quantum systems. I finally got an NP-completeness proof for that original problem last night :) Although this 2-in-4 SAT did NOT directly kick in to the final proof, the fact that this 2in4 SAT is indeed NP-hard (ie your answer here) greatly encouraged me to explore the direction in general, which ultimately led to the proof. I think it's appropriate to acknowledge you in the final paper (it'll probably take a few months). What do you think?  

---

