
























In the presented paper we study the Length-Bounded Cut problem for special graph classes as well as from a parameterized-complexity viewpoint. Here, we are given a graph $G$, two vertices $s$ and $t$, and positive integers $β$ and $λ$. The task is to find a set of edges $F$ of size at most $β$ such that every $s$-$t$-path of length at most $λ$ in $G$ contains some edge in $F$. Bazgan et al. conjectured that Length-Bounded Cut admits a polynomial-time algorithm if the input graph $G$ is a~proper interval graph. We confirm this conjecture by showing a dynamic-programming based polynomial-time algorithm. We strengthen the W[1]-hardness result of Dvořák and Knop. Our reduction is shorter, seems simpler to describe, and the target of the reduction has stronger structural properties. Consequently, we give W[1]-hardness for the combined parameter pathwidth and maximum degree of the input graph. Finally, we prove that Length-Bounded Cut is W[1]-hard for the feedback vertex number. Both our hardness results complement known XP algorithms.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。