Length-bounded cuts: Proper interval graphs and structural parameters

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F22%3A00357390" target="_blank" >RIV/68407700:21240/22:00357390 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1016/j.jcss.2021.12.002" target="_blank" >https://doi.org/10.1016/j.jcss.2021.12.002</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.jcss.2021.12.002" target="_blank" >10.1016/j.jcss.2021.12.002</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Length-bounded cuts: Proper interval graphs and structural parameters

Popis výsledku v původním jazyce

We study the LENGTH-BOUNDED CUT problem for special graph classes and 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 at most β edges such that each s-t-path of length at most λ in G contains some edge in F. Bazgan et al. [20] conjectured that LENGTH-BOUNDED CUT admits a polynomial-time algorithm if the input graph 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 for LENGTH-BOUNDED CUT parameterized by pathwidth by showing 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.

Název v anglickém jazyce

Length-bounded cuts: Proper interval graphs and structural parameters

Popis výsledku anglicky

We study the LENGTH-BOUNDED CUT problem for special graph classes and 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 at most β edges such that each s-t-path of length at most λ in G contains some edge in F. Bazgan et al. [20] conjectured that LENGTH-BOUNDED CUT admits a polynomial-time algorithm if the input graph 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 for LENGTH-BOUNDED CUT parameterized by pathwidth by showing 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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Výzkumné centrum informatiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2022

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Journal of Computer and System Sciences

ISSN

0022-0000

e-ISSN

1090-2724

Svazek periodika

126

Číslo periodika v rámci svazku

June

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

23

Strana od-do

21-43

Kód UT WoS článku

000793819400001

EID výsledku v databázi Scopus

2-s2.0-85122311438