We study the Directed Node Multiway Cut (DNMWC) problem: given a directed graph D = (V, A), a terminal set T ⊆ V (terminals are undeletable), and an integer k, delete at most k non-terminal vertices so that for every ordered pair of distinct terminals (s, t) ∈ T × T there is no directed path from s to t. While a line of work has shown that a simple “guess outside T, torso on T” 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—“most of the graph can be guessed away because only terminals matter in the end”—extends to the directed setting once separators are enumerated in a reachability-aware way.
We study the Directed Node Multiway Cut (DNMWC) problem: given a directed graph D = (V, A), a terminal set T ⊆ V (terminals are undeletable), and an integer k, delete at most k non-terminal vertices so that for every ordered pair of distinct terminals (s, t) ∈ T × T there is no directed path from s to t. While a line of work has shown that a simple “guess outside T, torso on T” 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—“most of the graph can be guessed away because only terminals matter in the end”—extends to the directed setting once separators are enumerated in a reachability-aware way.
