Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F20%3A00345585" target="_blank" >RIV/68407700:21240/20:00345585 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.4230/LIPIcs.ISAAC.2020.36" target="_blank" >https://doi.org/10.4230/LIPIcs.ISAAC.2020.36</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.ISAAC.2020.36" target="_blank" >10.4230/LIPIcs.ISAAC.2020.36</a>
Alternative languages
Result language
angličtina
Original language name
Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Research Center for Informatics</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2020
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
31st International Symposium on Algorithms and Computation (ISAAC 2020)
ISBN
978-3-95977-173-3
ISSN
—
e-ISSN
1868-8969
Number of pages
14
Pages from-to
"36:1"-"36:14"
Publisher name
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Place of publication
Dagstuhl
Event location
Hong Kong
Event date
Dec 14, 2020
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—