Recoloring bipartite graphs

Given a bipartite graph $G = (A,B,E)$ where every vertex is colored either red or blue I am trying to minimize the number of blue vertices using the following operation:

• Choose a vertex $v_a$ in $A$

• Flip the colors of $N[v_a]$, meaning that $v_a$ and every neighbor of $v_a$ will change color.

Is there a polynomial time algorithm to select a recoloring set $X \subseteq A$ that will minimize the number of blue vertices? The number of recolorings needed is not relevant.

Observe that the order of flipping does not matter, and for every vertex in $A$, you either flip it or you don't. We can think of the colors as a number which is incremented modulo 2. This yields a trivial $O(2^{|A|} \cdot n)$ algorithm.

The problem is NP-complete and is thus not likely to admit a polynomial time algorithm. Below is a proof of the NP-completeness of the problem, shown by a reduction from 1-in-3-SAT.

Let $\phi$ be an instance of 1-IN-3-SAT, where we are given a 3-CNF-SAT formula
asked to find a satisfying assignment where each clause is satisfied by exactly
one literal. Let $V(\phi)$ be the set of $n$ variables, and $C(\phi)$ be the
set of $m$ clauses.

We construct an instance $G = (A,B,E)$ with a budget of $b = n + m$ (the allowed
number of blue vertices).

For each variable $x \in V(\phi)$, construct two red vertices $v_x$ and
$v_{\overline{x}}$ in $A$ together with $b+1$ blue vertices in $B$ adjacent to
both of them. This forces exactly one of $v_x$ or $v_{\overline{x}}$ to be
flipped. We also end up with $n$ flipped "variable vertices", thus using the
first part of the budget.

Remark: $\{v_x, v_{\overline{x}} \mid x \in V(\phi)\}$ are the only vertices in
$A$.

For each clause, say $c = x \lor \overline{y} \lor z$, we create $b+1$ blue
vertices and three extra red vertices $v_{x \in c},v_{\overline{y} \in c},v_{z
\in c}$, all in $B$. Let $v_x,v_{\overline{y}},v_z$ all be fully adjacent to
the $b+1$ blue vertices and connect $v_x$ to $v_{x \in c}$, $v_y$ to
$v_{\overline{y} \in c}$, and $v_z$ to $v_{z \in c}$.

Now, since each clause gadget has $b+1$ blue vertices, we know that either one
or three literals in that clause have been flipped. Suppose that three have
been flipped for one of the clauses. But then we use at least budget $n + m +
2$.

Suppose that $\phi$ is a yes instance with a 1-in-3 assignment $\alpha: V(\phi)
\to \{\top,\bot\}$. Flip every vertex which corresponds to $\alpha$. Since
every clause is satisfied by exactly one variable, for each clause there is now
one blue vertex, and for each variable, exactly one of them is blue, hence we
have $n + m = b$ blue vertices.

StackExchange Computer Science Q#41843, answer score: 6