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

作者：

Highlights：

• We present the first single-exponential fixed-parameter algorithm for vertex deletion to distance-hereditary graphs parameterized by the solution size.

• We complement our result with matching asymptotic lower bounds based on the ETH.

摘要

•We present the first single-exponential fixed-parameter algorithm for vertex deletion to distance-hereditary graphs parameterized by the solution size.•We complement our result with matching asymptotic lower bounds based on the ETH.

论文关键词：Distance-hereditary graphs,Fixed-parameter algorithms,Rank-width

论文评审过程：Received 10 January 2017, Revised 22 February 2018, Accepted 29 May 2018, Available online 28 June 2018, Version of Record 13 August 2018.

论文官网地址：https://doi.org/10.1016/j.jcss.2018.05.005