Cheap and Secure Web Hosting Provider : See Now

[Solved]: Recoloring bipartite graphs

, ,
Problem Detail:

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.

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.

Question Source : http://cs.stackexchange.com/questions/41843

3.2K people like this