Directed Multicut with linearly ordered terminals
This solves a specific network security problem, providing an efficient algorithm for a linear case of Directed Multicut.
The paper tackles the Directed Multicut problem with linearly ordered terminals, showing it is fixed-parameter tractable with a cutset size parameter, resulting in an algorithm running in O(4^p p n^4) time.
Motivated by an application in network security, we investigate the following "linear" case of Directed Mutlicut. Let $G$ be a directed graph which includes some distinguished vertices $t_1, \ldots, t_k$. What is the size of the smallest edge cut which eliminates all paths from $t_i$ to $t_j$ for all $i < j$? We show that this problem is fixed-parameter tractable when parametrized in the cutset size $p$ via an algorithm running in $O(4^p p n^4)$ time.