{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T21:10:48Z","timestamp":1771967448540,"version":"3.50.1"},"reference-count":0,"publisher":"TechForum Publishing Group","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Bull. Comput. Data Sci."],"published-print":{"date-parts":[[2023,12,30]]},"abstract":"<jats:p>We study the Directed Node Multiway Cut (DNMWC) problem: given a directed graph D\u2004=\u2004(V,\u2006A), a terminal set T\u2004\u2286\u2004V (terminals are undeletable), and an integer k, delete at most k non-terminal vertices so that for every ordered pair of distinct terminals (s,\u2006t)\u2004\u2208\u2004T\u2005\u00d7\u2005T there is no directed path from s to t. While a line of work has shown that a simple \u201cguess outside T, torso on T\u201d strategy can be used to obtain exact algorithms with running time O*(cn) for a range of undirected terminal-set problems, the directed node multiway cut has remained an explicit obstacle: the same framework appears to top out at O*(2n) once terminals cannot be deleted and reachability becomes asymmetric. In this paper we show that this barrier can in fact be broken. We present an exact, deterministic algorithm for DNMWC running in time O*(1.999n) and polynomial space. Our approach keeps the overall three-phase recipe of Chitnis et al. [1] (guess the non-terminals, build a torso on T, solve a smaller subproblem) but replaces the naive guessing by a directed separator enumeration in which only vertices that participate in many terminal-to-terminal reachability patterns are ever guessed. This is made possible by combining: (i) a canonical choice of terminal reachability profiles, (ii) an upper bound on the number of important directed separators per profile, and (iii) a refined measure-and-conquer analysis that weights guessed vertices by how many terminal pairs they separate. Since the subproblem on the torso is small and structured, it can be solved by a direct exponential-time dynamic program over T. Our result answers a question left open by the torso-based framework for terminal-set vertex deletion: it shows that directed multiway separation is not inherently stuck at 2n, and that the same structural insight\u2014\u201cmost of the graph can be guessed away because only terminals matter in the end\u201d\u2014extends to the directed setting once separators are enumerated in a reachability-aware way.<\/jats:p>","DOI":"10.71448\/bcds2343-3","type":"journal-article","created":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T20:38:56Z","timestamp":1771965536000},"page":"23-35","source":"Crossref","is-referenced-by-count":0,"title":["Breaking the  2n  Barrier for Directed Node Multiway Cut via Terminal-Torso Decomposition"],"prefix":"10.71448","volume":"4","author":[{"name":"Diyala University, College of Veterinary Medicine, Diyala, Iraq","sequence":"first","affiliation":[]},{"given":"Abdulbasit","family":"ALazzawi","sequence":"first","affiliation":[]},{"given":"Bahbibi","family":"Rahmatullah","sequence":"additional","affiliation":[]},{"name":"Universiti Pendidikan Sultan Idris, Tanjung Malim, Perak, Malaysia","sequence":"additional","affiliation":[]}],"member":"52394","published-online":{"date-parts":[[2023,12,30]]},"container-title":["Bulletin of Computer and Data Sciences"],"original-title":[],"deposited":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T20:38:57Z","timestamp":1771965537000},"score":1,"resource":{"primary":{"URL":"https:\/\/bcds.ch\/breaking-the-2n-barrier-for-directed-node-multiway-cut-via-terminal-torso-decomposition\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,30]]},"references-count":0,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2023,12,30]]},"published-print":{"date-parts":[[2023,12,30]]}},"URL":"https:\/\/doi.org\/10.71448\/bcds2343-3","relation":{},"ISSN":["3072-2926"],"issn-type":[{"value":"3072-2926","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,30]]}}}