# Complexity of 2-coloring with extra constraints

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 and there, 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.

• 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.
Commented Jul 10 at 20:26
• 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 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. Commented Jul 11 at 4:47
• 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. Commented Jul 11 at 9:07

The problem is NP-complete by a reduction from 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.

• 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. Commented Jul 12 at 4:08
• 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. Commented Jul 12 at 8:16
• 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? Commented Jul 25 at 5:11