Complexity of 2-coloring with extra constraints

Question

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.

Answer 1

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.