Algorithm for minimizing the number of "inversions" in a graph Given the following graph:



With the assumptions below:


A node on the left is linked to several nodes on the right
Nodes on the right are paired together: one is black, one is white
Each pair of nodes on the right can be swapped (black becomes white and white becomes black)
A node on the left is green if linked to only white or only black; red if linked to two colors.


The idea is to minimize the amount of red nodes, by flipping some black and white nodes. What is the best algorithm to do that?

(I think this problem has something to do with some sort of cycle detection? This problem is probably well-known on some equivalent form.)

Of course it will be often impossible to make all nodes green; here node V can never be (it is linked to B0 and B1). Some cycles also make all green impossible.

Extra question — same as above, but with a weight associated to each edge. Minimize the sum (for each node) of absolutes delta between white and black (difference between the sums of weights for white and black for each left node).



Where does this problem comes from?

A transit network is composed of stops, routes and trips.


Each trip belongs to one route
Each trip has one natural direction (0 or 1, inbound/outbound)
Each trip goes through a list of stops.
The direction of all trips within a route is arbitrary; so it is possible to invert the direction of all trips of a given route (but all trips together).


If all trips passing through a stop do have the same direction (all 0 or all 1) we can compute a "natural" direction for the stop. Otherwise we cannot. The idea is to flip route trips direction to minimize the number of stops where we cannot compute this "natural" direction.

Here the nodes on the left are stops, pair of nodes on the right routes, with black/white all trips for each route direction.
You can reduce MAX-2-SAT to your problem. Therefore, your problem is NP-complete.

In MAX-2-SAT we have $n$ boolean variables $x_1, \dots, x_n$ and $m$ clauses of the form $a\vee b$ where $a$ and $b$ are $x_i$ or $\bar{x_i}$ (its complement). The goal is to assign $0$, and $1$ values to $x_i$'s such that the number of true clauses is maximized. This problem is NP-complete. For an arbitrary instance of MAX-2-SAT, we build an instance of your problems as follows. Hence, your problem is also NP-complete, i.e., kind of no chance for a polynomial-time algorithm for all cases.

We put $n+m$ pair of nodes ($x_i$ and $\bar{x_i}$ for $1\leq i\leq n$, and $y_k$ and $\bar{y_k}$ for $1\leq k\leq m$) on the right side and $3m$ node on the left (three nodes $v_{k,1}, v_{k,2}, v_{k,3}$ for $k$'th clause where $1\leq k\leq m$).
Let $(x_i\vee x_j)$ be the $k$'th clause in our instance (other cases are similar). We put three nodes $v_{k,1}, v_{k,2}, v_{k,3}$ in the left side of our graph. We then connect


$v_{k,1}$ to $x_i$ and $x_j$,
$v_{k,2}$ to $x_i$, $\bar{x_j}$, and $y_k$,
$v_{k,3}$ to $\bar{x_i}$, $x_j$, and $y_k$.


At most one of the $v_{k,1}, v_{k,2}, v_{k,3}$ can gets a green color. Moreover, this happens if and only if the clause gets a true value. Therefore, the maximum number of green nodes in the instance of your problem is equal to the solution to MAX-2-SAT.

Your bonus problem is harder than the original version and is also NP-complete.