论文标题
删除诱发匹配
Deletion to Induced Matching
论文作者
论文摘要
在删除引起的匹配问题中，我们在$ n $顶点，$ m $边缘和非负整数$ k $上获得了图形$ g $ （fpt）运行时间的算法$ o^*（1.748^{k}）$用于使用分支和还原策略和路径分解，以删除诱导匹配问题。我们还将工作扩展到问题的确切指数版本。
In the DELETION TO INDUCED MATCHING problem, we are given a graph $G$ on $n$ vertices, $m$ edges and a non-negative integer $k$ and asks whether there exists a set of vertices $S \subseteq V(G) $ such that $|S|\le k$ and the size of any connected component in $G-S$ is exactly 2. In this paper, we provide a fixed-parameter tractable (FPT) algorithm of running time $O^*(1.748^{k})$ for the DELETION TO INDUCED MATCHING problem using branch-and-reduce strategy and path decomposition. We also extend our work to the exact-exponential version of the problem.
