Bandwidth Parameterized by Cluster Vertex Deletion Number

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F25%3A00389717" target="_blank" >RIV/68407700:21240/25:00389717 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/s00453-025-01315-x" target="_blank" >https://doi.org/10.1007/s00453-025-01315-x</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00453-025-01315-x" target="_blank" >10.1007/s00453-025-01315-x</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Bandwidth Parameterized by Cluster Vertex Deletion Number

Popis výsledku v původním jazyce

Given a graph G and an integer b, Bandwidth asks whether there exists a bijection π from V(G) to {1,...,|V(G)|} such that max{u,v}elementE(G)|π(u)-π(v)|<=b. This is a classical NP-complete problem, known to remain NP-complete even on very restricted classes of graphs, such as trees of maximum degree 3 and caterpillars of hair length 3. In the realm of parameterized complexity, these results imply that the problem remains NP-hard on graphs of bounded pathwidth, while it is additionally known to be W[1]-hard when parameterized by the tree-depth of the input graph. In contrast, the problem does become FPT when parameterized by the vertex cover number. In this paper we make progress in understanding the parameterized (in)tractability of Bandwidth. We first show that it is FPT when parameterized by the cluster vertex deletion number cvd plus the clique number ω, thus significantly strengthening the previously mentioned result for vertex cover number. On the other hand, we show that Bandwidth is W[1]-hard when parameterized only by cvd. Our results develop and generalize some of the methods of argumentation of the previous results and narrow some of the complexity gaps.

Název v anglickém jazyce

Bandwidth Parameterized by Cluster Vertex Deletion Number

Popis výsledku anglicky

Given a graph G and an integer b, Bandwidth asks whether there exists a bijection π from V(G) to {1,...,|V(G)|} such that max{u,v}elementE(G)|π(u)-π(v)|<=b. This is a classical NP-complete problem, known to remain NP-complete even on very restricted classes of graphs, such as trees of maximum degree 3 and caterpillars of hair length 3. In the realm of parameterized complexity, these results imply that the problem remains NP-hard on graphs of bounded pathwidth, while it is additionally known to be W[1]-hard when parameterized by the tree-depth of the input graph. In contrast, the problem does become FPT when parameterized by the vertex cover number. In this paper we make progress in understanding the parameterized (in)tractability of Bandwidth. We first show that it is FPT when parameterized by the cluster vertex deletion number cvd plus the clique number ω, thus significantly strengthening the previously mentioned result for vertex cover number. On the other hand, we show that Bandwidth is W[1]-hard when parameterized only by cvd. Our results develop and generalize some of the methods of argumentation of the previous results and narrow some of the complexity gaps.

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

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2025

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

Algorithmica

ISSN

0178-4617

e-ISSN

1432-0541

Svazek periodika

87

Číslo periodika v rámci svazku

8

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

32

Strana od-do

1146-1177

Kód UT WoS článku

001480445900001

EID výsledku v databázi Scopus

2-s2.0-105004077613