# Parameterized complexity of length-bounded cuts and multi-cuts

arXiv: https://arxiv.org/abs/1511.02801 · HTML: https://mlsanity.com/paper/1511.02801/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Nov 2015.

## Built on by (most cited first, 1 of 1)

- [Practical Fixed-Parameter Algorithms for Defending Active Directory Style Attack Graphs](https://mlsanity.com/paper/2112.13175/) (2021)

## Abstract (arXiv)

We show that the Minimal Length-Bounded L-But problem can be computed in linear time with respect to L and the tree-width of the input graph as parameters. In this problem 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 long. 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) and that this problem does not admit polynomial kernel when parameterized by tree-width and L. We also derive an FPT algorithm for the Minimal Length-Bounded Cut problem when parameterized by the tree-depth. Thus showing an interesting paradigm for this problem and parameters tree-depth and path-width.