Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
复制标题
DOI：
10.1145/2797140
复制
发表时间：
2012-07
期刊：
影响因子：
--
通讯作者：
Eun Jung Kim;Alexander Langer;C. Paul;F. Reidl;P. Rossmanith;Ignasi Sau;S. Sikdar
中科院分区：
文献类型：
--
作者：
Eun Jung Kim;Alexander Langer;C. Paul;F. Reidl;P. Rossmanith;Ignasi Sau;S. Sikdar
我们提出了一个线性时间算法来计算图G的分解方案，该图G具有一个集合X <$V（G），称为树宽调制器，使得G-X的树宽由一个常数限制。我们的分解，称为突起分解，是获得以下两个主要结果的基石。我们的第一个结果是，任何参数化图问题（参数为k），有一个有限的整数指数，使得是的实例有一个树宽调制器的大小为O（k）承认一个线性核的类H-拓扑-minor-free图，对任何固定的图H。该结果部分扩展了之前关于有界亏格图和无H-小调图上线性核存在性的元定理。设F是至少包含一个平面图的固定有限图族。给定一个n-顶点图G和一个非负整数k，Planar-F-Deletion询问G是否有一个集合X <$V（G）使得|X| G − X对每个H ε F都是H-子式自由的。作为我们的第二个应用，我们提出了解决Planar-F-Deletion的第一个单指数算法。也就是说，我们的算法运行时间为2 O（k）· n2，这是关于k的渐近最优。到目前为止，单指数算法仅适用于F族的特殊情况。
We present a linear-time algorithm to compute a decomposition scheme for graphs G that have a set X⊆V(G), called a treewidth-modulator, such that the treewidth of G − X is bounded by a constant. Our decomposition, called a protrusion decomposition, is the cornerstone in obtaining the following two main results. Our first result is that any parameterized graph problem (with parameter k) that has a finite integer index and such that Yes-instances have a treewidth-modulator of size O(k) admits a linear kernel on the class of H-topological-minor-free graphs, for any fixed graph H. This result partially extends previous meta-theorems on the existence of linear kernels on graphs of bounded genus and H-minor-free graphs. Let F be a fixed finite family of graphs containing at least one planar graph. Given an n-vertex graph G and a non-negative integer k, Planar-F-Deletion asks whether G has a set X⊆V(G) such that |X| ⩽ k and G − X is H-minor-free for every H ε F. As our second application, we present the first single-exponential algorithm to solve Planar-F-Deletion. Namely, our algorithm runs in time 2O(k) · n2, which is asymptotically optimal with respect to k. So far, single-exponential algorithms were only known for special cases of the family F.