Bandwidth Parameterized by Cluster Vertex Deletion Number
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Bandwidth Parameterized by Cluster Vertex Deletion Number
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
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
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2025
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
Name of the periodical
Algorithmica
ISSN
0178-4617
e-ISSN
1432-0541
Volume of the periodical
87
Issue of the periodical within the volume
8
Country of publishing house
DE - GERMANY
Number of pages
32
Pages from-to
1146-1177
UT code for WoS article
001480445900001
EID of the result in the Scopus database
2-s2.0-105004077613