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]).