2026-07-24T05:41:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13380 2024-03-06T10:51:50Z ddc:004 open_access

Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters Bentert, Matthias Heeger, Klaus Knop, Dušan Edge-disjoint paths pathwidth feedback vertex number 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 F of edges of size at most β such that every s-t-path of length at most λ in G contains some edge in F. Bazgan et al. [Networks, 2019] 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 providing a dynamic-programming based polynomial-time algorithm. Moreover, we strengthen the W[1]-hardness result of Dvořák and Knop [Algorithmica, 2018] for Length-Bounded Cut parameterized by pathwidth. Our reduction is shorter, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Matthias Bentert and Klaus Heeger and Dušan Knop 2020 Is Part Of LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2020.36 urn:nbn:de:0030-drops-133800 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.36 eng https://creativecommons.org/licenses/by/3.0/legalcode