咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >Polynomial Kernels and Widenes... 收藏

Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes

多项式核和没什么地方稠密的图班的宽性质

作     者:Kreutzer, Stephan Rabinovich, Roman Siebertz, Sebastian 

作者机构:Tech Univ Berlin Inst Softwaretech & Theoret Informat Lehrstuhl Log & Semant TEL 7-3Ernst Reuter Pl 7 D-10587 Berlin Germany Humboldt Univ Johann von Neumann Haus Inst Informat Algorithm Engn Rudower Chausse 25 D-12489 Berlin Germany 

出 版 物:《ACM TRANSACTIONS ON ALGORITHMS》 (运算法则学报)

年 卷 期:2019年第15卷第2期

页      面:24-24页

核心收录:

学科分类:07[理学] 0701[理学-数学] 0812[工学-计算机科学与技术(可授工学、理学学位)] 070101[理学-基础数学] 

基  金:European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (ERC Consolidator Grant DISTRUCT) 

主  题:Graph structure theory nowhere denseness uniform quasi-wideness stability theory 

摘      要:Nowhere dense classes of graphs [21, 22] are very general classes of uniformly sparse graphs with several seemingly unrelated characterisations. From an algorithmic perspective, a characterisation of these classes in terms of uniform quasi-wideness, a concept originating in finite model theory, has proved to be particularly useful. Uniform quasi-wideness is used in many fpt-algorithms on nowhere dense classes. However, the existing constructions showing the equivalence of nowhere denseness and uniform quasi-wideness imply a non-elementary blow up in the parameter dependence of the fpt-algorithms, making them infeasible in practice. As a first main result of this article, we use tools from logic, in particular from a sub-field of model theory known as stability theory, to establish polynomial bounds for the equivalence of nowhere denseness and uniform quasi-wideness. A powerfulmethod in parameterized complexity theory is to compute a problem kernel in a pre-computation step, that is, to reduce the input instance in polynomial time to a sub-instance of size bounded in the parameter only (independently of the input graph size). Our new tools allow us to obtain for every fixed radius r is an element of N a polynomial kernel for the distance-r dominating set problem on nowhere dense classes of graphs. This result is particularly interesting, as it implies that for every class C of graphs that is closed under taking subgraphs, the distance-r dominating set problem admits a kernel on C for every value of r if, and only if, it already admits a polynomial kernel for every value of r (under the standard assumption of parameterized complexity theory that FPT not equal W[2]).

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分