论文标题
仙人掌顶点缺失的改进的确定性参数化算法
An Improved Deterministic Parameterized Algorithm for Cactus Vertex Deletion
论文作者
论文摘要
仙人掌是一个连接的图，不包含$ k_4 -e $作为未成年人。给定图形$ g =（v，e）$和整数$ k \ ge 0 $，仙人掌顶点删除（也称为钻石命中套件）是确定$ g $ g $最多有$ k $的顶点$ k $的问题。此问题的当前最佳确定性参数化算法归因于Bonnet等。 [wg 2016]，及时运行$ 26^kn^{o（1）} $，其中$ n $是$ g $的顶点。在本文中，我们为仙人掌顶点删除设计了一种确定性算法，该算法的时间为$ 17.64^kn^{o（1）} $。作为我们算法的直接应用，我们给出了$ 17.64^kn^{o（1）} $ - 时间算法，即使循环横向。这种改进背后的想法是通过略有详尽的实例进行衡量和征服分析。
A cactus is a connected graph that does not contain $K_4 - e$ as a minor. Given a graph $G = (V, E)$ and integer $k \ge 0$, Cactus Vertex Deletion (also known as Diamond Hitting Set) is the problem of deciding whether $G$ has a vertex set of size at most $k$ whose removal leaves a forest of cacti. The current best deterministic parameterized algorithm for this problem was due to Bonnet et al. [WG 2016], which runs in time $26^kn^{O(1)}$, where $n$ is the number of vertices of $G$. In this paper, we design a deterministic algorithm for Cactus Vertex Deletion, which runs in time $17.64^kn^{O(1)}$. As a straightforward application of our algorithm, we give a $17.64^kn^{O(1)}$-time algorithm for Even Cycle Transversal. The idea behind this improvement is to apply the measure and conquer analysis with a slightly elaborate measure of instances.
