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 FPT time with respect to L and the tree-width of the input graph G as parameters and with linear dependence of vertical bar V(G)vertical bar (i.e., in time f (L, tw(G))vertical bar V(G)vertical bar 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 W[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.
展开▼
