Directed Multicut with linearly ordered terminals

Abstract

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,\dots ,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.

12 pages, 1 figure