Subset Feedback Vertex Set Is Fixed-Parameter Tractable
Subset Feedback Vertex Set Is Fixed-Parameter Tractable
复制标题
DOI：
10.1137/110843071
复制
发表时间：
2010-04
期刊：
影响因子：
--
通讯作者：
Marek Cygan;Marcin Pilipczuk;Michal Pilipczuk;J. O. Wojtaszczyk
中科院分区：
文献类型：
--
作者：
Marek Cygan;Marcin Pilipczuk;Michal Pilipczuk;J. O. Wojtaszczyk
经典的反馈顶点集问题要求，对于给定的无向图 G 和整数 k，找到一组最多 k 个顶点，满足图 G 中的所有环。反馈顶点集在参数化设置方面吸引了大量研究，后续的核化和固定参数算法已成为该领域的丰富思想来源。在本文中，我们考虑该问题的一个更一般和更困难的版本，称为子集反馈顶点集（简称 SUBSET-FVS），其中一个实例另外带有一组 S ⊆ V 顶点，并且我们要求一组最多 k 个顶点，该顶点命中通过 S 的所有简单循环。由于其在电路测试和遗传连锁分析中的应用，Even 等人从近似算法的角度研究了 SUBSET-FVS。 [SICOMP'00，SIDMA'00]。 SUBSET-FVS问题是否是定参可处理的问题是Kawarabayashi和Saurabh在2009年独立提出的。我们对这个问题的回答是肯定的。我们首先证明当用 |S| 参数化时，这个问题是固定参数易于处理的。接下来，我们提出一种算法，使用 2-展开引理、Menger 定理和 Gallai 定理等核化技术，将给定实例减少到 2knO(1) 个实例，S 的大小以 O(k3) 为界。这两个事实使我们能够给出一个 2O(klog k)nO(1) 时间的算法来解决子集反馈顶点集问题，证明它确实是固定参数可处理的。
The classical FEEDBACK VERTEX SET problem asks, for a given undirected graph G and an integer k, to find a set of at most k vertices that hits all the cycles in the graph G. FEEDBACK VERTEX SET has attracted a large amount of research in the parameterized setting, and subsequent kernelization and fixedparameter algorithms have been a rich source of ideas in the field. In this paper we consider a more general and difficult version of the problem, named SUBSET FEEDBACK VERTEX SET (SUBSET-FVS in short) where an instance comes additionally with a set S ⊆ V of vertices, and we ask for a set of at most k vertices that hits all simple cycles passing through S. Because of its applications in circuit testing and genetic linkage analysis SUBSET-FVS was studied from the approximation algorithms perspective by Even et al. [SICOMP'00, SIDMA'00]. The question whether the SUBSET-FVS problem is fixed-parameter tractable was posed independently by Kawarabayashi and Saurabh in 2009. We answer this question affirmatively. We begin by showing that this problem is fixed-parameter tractable when parametrized by |S|. Next we present an algorithm which reduces the given instance to 2knO(1) instances with the size of S bounded by O(k3), using kernelization techniques such as the 2-Expansion Lemma, Menger's theorem and Gallai's theorem. These two facts allow us to give a 2O(klog k)nO(1) time algorithm solving the SUBSET FEEDBACK VERTEX SET problem, proving that it is indeed fixed-parameter tractable.