检索结果-内蒙古大学图书馆

Linear Kernels and single-exponential algorithms via Protrusion Decompositions 1

40th International Colloquium on Automata, Languages and Programming (ICALP)

作者： Kim, Eun Jung Langer, Alexander Paul, Christophe Reidl, Felix Rossmanith, Peter Sau, Ignasi Sikdar, Somnath CNRS LAMSADE Paris France Rhein Westfal TH Aachen Dept Comp Sci Theoret Comp Sci Aachen Germany CNRS LIRMM Montpellier France

ISBN: (数字)9783642392061

ISBN: (纸本)9783642392061

We present a linear-time algorithm to compute a decomposition scheme for graphs G that have a set X subset of C 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 finite integer index and such that positive 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, PLANART-DELETION asks whether G has a set X subset of V (G) such that vertical bar X vertical bar <= k and G-X is H-minor-free for every H is an element of F. As our second application, we present the first single-exponential algorithm to solve PLANAR-F-DELETION. Namely, our algorithm runs in time 2(O(k))center dot n(2), which is asymptotically optimal with respect to k. So far, single-exponential algorithms were only known for special cases of the family F.

关键词： parameterized complexity linear kernels algorithmic meta-theorems sparse graphs single-exponential algorithms graph minors

来源：评论

学校读者我要写书评

暂无评论

The role of planarity in connectivity problems parameterized by treewidth

引用

THEORETICAL COMPUTER SCIENCE 2015年第C期570卷 1-14页

作者： Baste, Julien Sau, Ignasi LIRMM AlGCo Project Team Montpellier France ENS Cachan Cachan France

For some years it was believed that for "connectivity" problems such as HAMILTONIAN CYCLE, algorithms running in time 2(0(tw)).n(0(1)) - called single-exponential - existed only on planar and other topologically constrained graph classes, where tw stands for the treewidth of the n-vertex input graph. This was recently disproved by Cygan et al. [3, FOCS 2011], Bodlaender et al. [1, ICALP 2013], and Fomin et al. [11, SODA 2014], who provided single-exponential algorithms on general graphs for most connectivity problems that were known to be solvable in single-exponential time on topologically constrained graphs. In this article we further investigate the role of planarity in connectivity problems parameterized by treewidth, and convey that several problems can indeed be distinguished according to their behavior on planar graphs. Known results from the literature imply that there exist problems, like CYCLE PACKING, that cannot be solved in time 2(0(tw log tw)).n(0(1)) on general graphs but that can be solved in time 2(0(tw)).n(0(1)) when restricted to planar graphs. Our main contribution is to show that there exist natural problems that can be solved in time 2(0(tw log tw)).n(0(1)) on general graphs but that cannot be solved in time 2(0(tw log tw)).n(0(1)) even when restricted to planar graphs. Furthermore, we prove that PLANAR CYCLE PACKING and PLANAR DISJOINT PATHS cannot be solved in time 2(0(tw)).n(0(1)). The mentioned negative results hold unless the ETH fails. We feel that our results constitute a first step in a subject that can be further exploited. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Parameterized complexity Treewidth Connectivity problems single-exponential algorithms Planar graphs Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

The Role of Planarity in Connectivity Problems Parameterized by Treewidth 1

引用

9th International Symposium on Parameterized and Exact Computation (IPEC)

作者： Baste, Julien Sau, Ignasi CNRS LIRMM AlGCo Project Team Montpellier France

ISBN: (数字)9783319135243

ISBN: (纸本)9783319135243;9783319135236

For some years it was believed that for "connectivity" problems such as HAMILTONIAN CYCLE, algorithms running in time 2(O(tw)).n(O(1)) -called single-exponential-existed only on planar and other sparse graph classes, where tw stands for the treewidth of the n-vertex input graph. This was recently disproved by Cygan et al. [FOCS 2011], Bodlaender et al. [ICALP 2013], and Fomin et al. [SODA 2014], who provided single-exponential algorithms on general graphs for most connectivity problems that were known to be solvable in single-exponential time on sparse graphs. In this article we further investigate the role of planarity in connectivity problems parameterized by treewidth, and convey that several problems can indeed be distinguished according to their behavior on planar graphs. Known results from the literature imply that there exist problems, like CYCLE PACKING, that cannot be solved in time 2(o(tw log tw)).n(O(1)) on general graphs but that can be solved in time 2(O(tw)).n(O(1)) when restricted to planar graphs. Our main contribution is to show that there exist natural problems that can be solved in time 2(O(twlog tw)).n(O(1)) on general graphs but that cannot be solved in time 2(o(twlog tw)).n(O(1)) even when restricted to planar graphs. Furthermore, we prove that PLANAR CYCLE PACKING and PLANAR DISJOINT PATHS cannot be solved in time 2(o(tw)).n(O(1)). The mentioned negative results hold unless the ETH fails. We feel that our results constitute a first step in a subject that can be further exploited.

关键词： Parameterized complexity Treewidth Connectivity problems single-exponential algorithms Planar graphs Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：