Given a directed graph whose arcs are coloured red and blue and integers $r$ and $b$, can we decide in polynomial time whether the digraph has a cut with at most $r$ red arcs and at most $b$ blue arcs?Related references can be found here http://lemon.cs.elte.hu/egres/open/Red-blue_cut_problemIt is known that the undirected version of the problem is in P even if there are weights on the edges. 
Can we decide Red-blue cut problem in polynomial time?
cc.complexity theory;graph theory