On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F18%3A00106812" target="_blank" >RIV/00216224:14330/18:00106812 - isvavai.cz</a>

Result on the web

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

DOI - Digital Object Identifier

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

Result language

angličtina

Original language name

On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem

Original language description

We study the parameterized complexity of the Bounded-Degree Vertex Deletion problem (BDD), where the aim is to find a maximum induced subgraph whose maximum degree is below a given degree bound. Our focus lies on parameters that measure the structural properties of the input instance. We first show that the problem is W[1]-hard parameterized by a wide range of fairly restrictive structural parameters such as the feedback vertex set number, pathwidth, treedepth, and even the size of a minimum vertex deletion set into graphs of pathwidth and treedepth at most three. We thereby resolve the main open question stated in Betzler, Bredereck, Niedermeier and Uhlmann (2012) concerning the complexity of BDD parameterized by the feedback vertex set number. On the positive side, we obtain fixed-parameter algorithms for the problem with respect to the decompositional parameter treecut width and a novel problem-specific parameter called the core fracture number.

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

S - Specificky vyzkum na vysokych skolach

Publication year

2018

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

STACS 2018

ISBN

9783959770620

ISSN

1868-8969

e-ISSN

—

Number of pages

14

Pages from-to

1-14

Publisher name

Dagstuhl

Place of publication

Nemecko

Event location

Francie

Event date

Mar 28, 2018

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

000521090200033