D 2016

A Single-Exponential Fixed-Parameter Algorithm for Distance-Hereditary Vertex Deletion

GANIAN, Robert, Eduard EIBEN and O-joung KWON

Basic information

Original name

A Single-Exponential Fixed-Parameter Algorithm for Distance-Hereditary Vertex Deletion

Authors

GANIAN, Robert (203 Czech Republic, guarantor, belonging to the institution), Eduard EIBEN (703 Slovakia) and O-joung KWON (410 Republic of Korea)

Edition

Germany, 41st International Symposium on Mathematical Foundations of Computer Science, {MFCS} 2016, August 22-26, 2016 - Krak{\'{o}}w, Poland, p. "34:1"-"34:14", 14 pp. 2016

Publisher

Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

electronic version available online

RIV identification code

RIV/00216224:14330/16:00093948

Organization unit

Faculty of Informatics

ISBN

978-3-95977-016-3

ISSN

DOI

Keywords in English

algorithms; vertex deletion problems

Tags

Tags

International impact, Reviewed
Změněno: 27/8/2019 12:08, RNDr. Pavel Šmerk, Ph.D.

Abstract

V originále

Vertex deletion problems ask whether it is possible to delete at most k vertices from a graph so that the resulting graph belongs to a specified graph class. Over the past years, the parameterized complexity of vertex deletion to a plethora of graph classes has been systematically researched. Here we present the first single-exponential fixed-parameter algorithm for vertex deletion to distance-hereditary graphs, a well-studied graph class which is particularly important in the context of vertex deletion due to its connection to the graph parameter rank-width. We complement our result with matching asymptotic lower bounds based on the exponential time hypothesis.