Logical s-t Min-Cut Problem: An Extension to the Classic s-t Min-Cut Problem
Mojtaba Valizadeh, M. H. Tadayon · Iranian Journal of Mathematical Sciences and Informatics · 2022
Let G be a weighted digraph, s and t be two vertices of G, and t is reachable from s.The logical s-t min-cut (LSTMC) problem states how t can be made unreachable from s by removal of some edges of G where (a) the sum of weights of the removed edges is minimum and (b) all outgoing edges of any vertex of G cannot be removed together.If we ignore the second constraint, called the logical removal, the LSTMC problem is transformed to the classic s-t min-cut problem.The logical removal constraint applies in situations where non-logical removal is either infeasible or undesired.Although the s-t min-cut problem is solvable in polynomial time by the max-flow min-cut theorem, this paper shows the LSTMC problem is NP-Hard, even if G is a DAG with an out-degree of two.Moreover, this paper shows that the LSTMC problem cannot be approximated within αlogn in a DAG with n vertices for some constant α.The application of the LSTMC problem is also presented in test case generation of a computer program.