文章基本信息

标题：Generalized Distance Domination Problems and Their Complexity on Graphs of Bounded mim-width
本地全文：下载
作者：Lars Jaffke ; O-joung Kwon ; Torstein J. F. Strømme 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：115
页码：1-14
DOI：10.4230/LIPIcs.IPEC.2018.6
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We generalize the family of (sigma, rho)-problems and locally checkable vertex partition problems to their distance versions, which naturally captures well-known problems such as distance-r dominating set and distance-r independent set. We show that these distance problems are XP parameterized by the structural parameter mim-width, and hence polynomial on graph classes where mim-width is bounded and quickly computable, such as k-trapezoid graphs, Dilworth k-graphs, (circular) permutation graphs, interval graphs and their complements, convex graphs and their complements, k-polygon graphs, circular arc graphs, complements of d-degenerate graphs, and H-graphs if given an H-representation. To supplement these findings, we show that many classes of (distance) (sigma, rho)-problems are W[1]-hard parameterized by mim-width + solution size.
关键词：Graph Width Parameters; Graph Classes; Distance Domination Problems; Parameterized Complexity