Red-blue cut problem
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?
The undirected version of the problem is in P even if there are weights on the edges, using the results of Karger, Motwani and Stein  and Nagamochi et al.. See also the papers of Armon and Zwick  and Aissi et al.
Another variant can be obtained by considering only s-t cuts for given nodes s and t. In this case the problem is NP-complete for general digraphs (D. Marx), but it is in P for planar digraphs (Z. Király). For undirected graphs, the weighted case is NP-complete , but the unweighted case is open.
- D. R. Karger, C. Stein, A new approach to the minimum cut problem, Journal of the ACM 43 (1996), 601-640. DOI link.
- D. R. Karger, R. Motwani, An NC algorithm for minimum cuts, SIAM Journal on Computing 26 (1997), 255-272. DOI link.
- H. Nagamochi, K. Nishimura, T. Ibaraki, Computing all small cuts in an undirected network, SIAM Journal on Discrete Mathematics 10 (1997), 469-481. DOI link.
- A. Armon, U. Zwick, Multicriteria Global Minimum Cuts, Algorithmica 46 (2006), 15-26. DOI link
- H. Aissi, C. Bazgan, D. Vanderpooten, Complexity of the min–max (regret) versions of min cut problems, Discrete Optimization 5 (2008), 66-73. DOI link.
- C.H. Papadimitriou, M. Yannakakis, On the approximability of trade-offs and optimal access of web sources, IEEE Symposium on Foundations of Computer Science (2000), pp. 86–92. DOI link.