# Red-blue cut problem

From Egres Open

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?

## Remarks

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 ^{[1]}^{[2]} and Nagamochi et al.^{[3]}. See also the papers of Armon and Zwick ^{[4]} and Aissi et al.^{[5]}

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 ^{[6]}, but the unweighted case is open.

## References

- ↑ 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.