Length-bounded cuts: proper interval graphs and structural parameters (Q2119399)

The paper studies a variant of the \textsc{Edge Cut} problem called the \textsc{Length-Bounded Cut} problem, which is the cut problem related to the variant of the \textsc{Edge Disjoint Paths} problem. The task of the \textsc{Length-Bounded Cut} problem is to find a set \(F\) of at most \(\beta\) edges such that each \(s\)-\(t\)-path of length at most \(\lambda\) in \(G\) contains some edge in \(F\), i.e., there is no \(s\)-\(t\)-path of length at most \(\lambda\) in \(G-F\). The \textsc{Length-Bounded Cut} problem is polynomially solvable for \(\lambda=|V|\) as it reduces to \textsc{Edge Cut} and also for \(\lambda\le 3\), while it is NP-hard for the remaining values \(\lambda\ge 4\). This paper studies \textsc{Length-Bounded Cut} for special graph classes and confirms a conjecture of \textit{C. Bazgan} et al. [Networks 73, No. 1, 23--37 (2019; Zbl 1407.90090)] that it can be solved in polynomial time on proper interval graphs. The authors give a dynamic-programming-based algorithm for the problem with running time \(O(n^2\cdot m)\). Regarding parameterized complexity, the authors show that the \textsc{Length-Bounded Cut} problem is W[1]-hard for the feedback vertex number and for the combined parameter pathwidth and maximum degree of the input graph \(G\). The above results imply that, assuming the Exponential Time Hypothesis, there is no \(f(k)\cdot n^{o(k)}\)-time algorithm for \textsc{Length-Bounded Cut}, where \(k\) is the pathwidth of the input graph.