Volume 17, Issue 2 (9-2022)                   IJMSI 2022, 17(2): 253-271 | Back to browse issues page

XML Print

Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:

Valizadeh M, Tadayon M H. Logical s-t Min-Cut Problem: An Extension to the Classic s-t Min-Cut Problem. IJMSI 2022; 17 (2) :253-271
URL: http://ijmsi.ir/article-1-1481-en.html
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 $alpha log n$ in a DAG with $n$ vertices for some constant $alpha$. The application of the LSTMC problem is also presented intest case generation of a computer program.
Type of Study: Research paper | Subject: General

Add your comments about this article : Your username or Email:

Rights and permissions
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

© 2023 CC BY-NC 4.0 | Iranian Journal of Mathematical Sciences and Informatics

Designed & Developed by : Yektaweb