8
$\begingroup$

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:

  1. Choose a vertex $v_a$ in $A$
  2. 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.

$\endgroup$
6
$\begingroup$

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}$.

reduction gadget

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.

$\endgroup$
  • $\begingroup$ In the third paragraph, the vertices added for each $x \in X$ go into $B$? $\endgroup$ – Luke Mathieson Apr 28 '15 at 4:04
  • $\begingroup$ +1. I have a naive question: why does each group of blue vertices contain 6 dots (instead of 5 = 3 + 1 + 1)? $\endgroup$ – hengxin Apr 28 '15 at 12:24
  • 1
    $\begingroup$ @hengxin I just wanted to draw "enough" blue vertices. As long as there are at least $b+1$ vertices everything works, but, yeah, you're right. $\endgroup$ – Pål GD Apr 28 '15 at 12:50
3
$\begingroup$

Pål GD explains that the problem is NP-hard, so the next step is to try to find reasonable algorithms for your problem.

I'll note that your problem can be reduced to MINIMUM WEIGHT CODEWORD: given a linear code, find a codeword of minimum weight. Another way to state this problem is: given a boolean matrix $M$ and a boolean vector $y$, find a non-zero boolean vector $x$ such that the Hamming weight of $Mx \oplus y$ is minimized. (All arithmetic is performed modulo 2.) MINIMUM WEIGHT CODEWORD is known to be NP-hard, but there are some algorithms for it that are faster than brute-force.

Here is the connection. If there are $n$ vertices, then any $n$-bit boolean vector can be thought of as specifying which vertices will be flipped by a particular flip-operation. Thus for each vertex $v$ we get a corresponding flip-vector $m_v$. Put these into a $n \times n$ matrix, where each row corresponds to a different flip-vector. Let $y$ be a $n$-bit boolean vector that specifies the original colors of the vertices (blue=1, red=0). Now the goal is to find a boolean vector $x$ that minimizes the Hamming weight of $Mv \oplus y$. Any such vector corresponds immediately to a set of flip-operations that minimizes the number of blue vertices in the graph.

With this background, you might be able to apply known algorithms for finding minimum-weight codewords in linear codes to your problem. The running time will still be exponential, but faster than trying all possibilities for $x$.

$\endgroup$
  • $\begingroup$ This is actually pretty funny as I ran into this while trying to solve a linear system mod 2. I was unaware that the problem was called minimum weight codeword. Thank you! $\endgroup$ – Davis Yoshida May 2 '15 at 2:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.