When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2020.36
URN: urn:nbn:de:0030-drops-133800
URL: https://drops.dagstuhl.de/opus/volltexte/2020/13380/
 Go to the corresponding LIPIcs Volume Portal

### Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters

 pdf-format:

### Abstract

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.

### BibTeX - Entry

```@InProceedings{bentert_et_al:LIPIcs:2020:13380,
author =	{Matthias Bentert and Klaus Heeger and Du{\v{s}}an Knop},
title =	{{Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters}},
booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
pages =	{36:1--36:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-173-3},
ISSN =	{1868-8969},
year =	{2020},
volume =	{181},
editor =	{Yixin Cao and Siu-Wing Cheng and Minming Li},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},