On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem

GANIAN, Robert, Fabian KLUTE and Sebastian ORDYNIAK. On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem. In Rolf Niedermeier, Brigitte Vallee. STACS 2018. Nemecko: Dagstuhl. p. 1-14. ISBN 978-3-95977-062-0. doi:10.4230/LIPIcs.STACS.2018.33. 2018.

Basic information

• Original name: On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem
• Authors: GANIAN, Robert (203 Czech Republic, guarantor, belonging to the institution), Fabian KLUTE (276 Germany) and Sebastian ORDYNIAK (276 Germany).
• Edition: Nemecko, STACS 2018, p. 1-14, 14 pp. 2018.
• Publisher: Dagstuhl

Other information

• Original language: English
• Type of outcome: Proceedings paper
• Field of Study: 10201 Computer sciences, information science, bioinformatics
• Country of publisher: Germany
• Confidentiality degree: is not subject to a state or trade secret
• Publication form: electronic version available online
• RIV identification code: RIV/00216224:14330/18:00106812
• Organization unit: Faculty of Informatics
• ISBN: 978-3-95977-062-0
• ISSN: 1868-8969
• Doi: http://dx.doi.org/10.4230/LIPIcs.STACS.2018.33
• UT WoS: 000521090200033
• Keywords in English: bounded-degree vertex deletion; feedback vertex set; parameterized algorithms; treecut width
• Tags: core_A, firank_A
• Tags: International impact, Reviewed

Abstract

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.

Links

• MSM0021622419, plan (intention): Name: Vysoce paralelní a distribuované výpočetní systémy

Investor: Ministry of Education, Youth and Sports of the CR, Highly Parallel and Distributed Computing Systems