Bandwidth Parameterized by Cluster Vertex Deletion Number

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F23%3A00370210" target="_blank" >RIV/68407700:21240/23:00370210 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.4230/LIPIcs.IPEC.2023.21" target="_blank" >https://doi.org/10.4230/LIPIcs.IPEC.2023.21</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.IPEC.2023.21" target="_blank" >10.4230/LIPIcs.IPEC.2023.21</a>

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} element E(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 treedepth of the input graph. In contrast, the problem does become FPT when parameterized by the vertex cover number of the input graph. In this paper, we make progress towards 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 ω of the input graph, thus generalizing the previously mentioned result for vertex cover. On the other hand, we show that Bandwidth is W[1]-hard when parameterized only by cvd. Our results generalize some of the previous results and narrow some of the complexity gaps.

Czech name

—

Czech description

—

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)

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2023

Confidentiality

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

Article name in the collection

Proceedings of the 18th International Symposium on Parameterized and Exact Computation

ISBN

978-3-95977-305-8

ISSN

1868-8969

e-ISSN

—

Number of pages

15

Pages from-to

"21:1"-"21:15"

Publisher name

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Place of publication

Dagstuhl

Event location

Amsterdam

Event date

Sep 6, 2023

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—