Algorithm for minimizing the number of "inversions" in a graph
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.