Parametrized Complexity of Length-Bounded Cuts and Multi-cuts

Abstract

We show that the minimal length-bounded L-cut can be computed in linear time with respect to L and the tree-width of the input graph as parameters. We derive an FPT algorithm for a more general multi-commodity length bounded cut problem when parameterized by the number of terminals also.

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).

Keywords

• Length bounded cuts
• Parameterized algorithms
• W[1]-hardness