A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion (Q1672007): Difference between revisions

The paper targets the Distance-Hereditary Vertex Deletion (DHVD) problem. Given a graph \(G\) and an integer \(k\), the goal is to decide whether there is a vertex set \(Q\subseteq V (G)\) with \(|Q|\leq k\) such that \(G-Q\) is distance-hereditary. A graph is called distance-hereditary if for every connected induced subgraph \(H\) and every \(v, w\in V (H)\), the distance between \(v\) and \(w\) in \(H\) is the same as the distance between \(v\) and \(w\) in \(G\). Single-exponential fixed-parameter tractable (FPT) algorithms are algorithms running in time \(O(c^k\cdot n^{O(1)})\) for input size \(n\), some constant \(c\) and input parameter \(k\). The main result of this paper is a proof of the existence of a single-exponential (FPT) algorithm for the DHVD problem with running time \(O(37^k\cdot |V (G)|^7(|V (G)| + |E(G)|))\).