版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构: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[理学-基础数学]
主 题: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]).