A single-exponential fixed-parameter algorithm for
distance-hereditary vertex deletion

J 2018

A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion

EIBEN, Eduard, Robert GANIAN and O-joung KWON

Basic information

Original name

A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion

Authors

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

Edition

Journal of Computer and System Sciences, Academic Press, 2018, 0022-0000

Other information

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

United States of America

Confidentiality degree

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

Impact factor

Impact factor: 1.129

RIV identification code

RIV/00216224:14330/18:00106818

Organization unit

Faculty of Informatics

DOI

http://dx.doi.org/10.1016/j.jcss.2018.05.005

UT WoS

000441371400009

Keywords in English

parameterized complexity; distance hereditary graphs

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 tractable 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. As an application of our algorithm, we show that a vertex deletion set to distance-hereditary graphs can be used as a parameter which allows single-exponential fixed-parameter tractable algorithms for classical NP-hard problems.

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

Citovat

EIBEN, Eduard, Robert GANIAN and O-joung KWON. A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion. Journal of Computer and System Sciences. Academic Press, 2018, vol. 97, No 1, p. 121-146. ISSN 0022-0000. Available from: https://dx.doi.org/10.1016/j.jcss.2018.05.005.

@article{1523837,
   author = {Eiben, Eduard and Ganian, Robert and Kwon, Oandjoung},
   article_number = {1},
   doi = {http://dx.doi.org/10.1016/j.jcss.2018.05.005},
   keywords = {parameterized complexity; distance hereditary graphs},
   language = {eng},
   issn = {0022-0000},
   journal = {Journal of Computer and System Sciences},
   title = {A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion},
   volume = {97},
   year = {2018}
}

TY  - JOUR
ID  - 1523837
AU  - Eiben, Eduard - Ganian, Robert - Kwon, O-joung
PY  - 2018
TI  - A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
JF  - Journal of Computer and System Sciences
VL  - 97
IS  - 1
SP  - 121-146
EP  - 121-146
PB  - Academic Press
SN  - 00220000
KW  - parameterized complexity
KW  - distance hereditary graphs
N2  - 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 tractable 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. As an application of our algorithm, we show that a vertex deletion set to distance-hereditary graphs can be used as a parameter which allows single-exponential fixed-parameter tractable algorithms for classical NP-hard problems.
ER  -

EIBEN, Eduard, Robert GANIAN and O-joung KWON. A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion. \textit{Journal of Computer and System Sciences}. Academic Press, 2018, vol.~97, No~1, p.~121-146. ISSN~0022-0000. Available from: https://dx.doi.org/10.1016/j.jcss.2018.05.005.

Detailed Information on Publication Record