Abstrakt
We study the Minimum Length-Bounded Cut problem where the task is to find a set of edges of a graph such that after removal of this set, the shortest path between two prescribed vertices is at least L+1 long. We show the problem can be computed in 𝖥𝖯𝖳 time with respect to L and the tree-width of the input graph G as parameters and with linear dependence of |V(G)| (i.e., in time f(L,tw(𝐺))|𝑉(��)| for a computable function f).
We derive an FPT algorithm for a more general multi-commodity length-bounded cut problem when additionally parameterized by the number of terminals. For the former problem we show a 𝖶[1] -hardness result when the parameterization is done by the path-width only (instead of the tree-width) and that this problem does not admit polynomial kernel when parameterized by path-width and L.
We also derive an FPT algorithm for the Minimum Length-Bounded Cut problem when parameterized by the tree-depth, thus showing an interesting behavior for this problem and parameters tree-depth and path-width.