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.
