Mim-width III. Graph powers and generalized distance domination problems

Cited 0 time in webofscience Cited 0 time in scopus
17 Viewed 3 Downloaded
Title
Mim-width III. Graph powers and generalized distance domination problems
Author(s)
Lars Jaffke; O-joung Kwon; Torstein J.F.Strømmea; Jan ArneTellea
Publication Date
2019-12
Journal
THEORETICAL COMPUTER SCIENCE, v.796, no., pp.216 - 236
Publisher
ELSEVIER SCIENCE BV
Abstract
We generalize the family of (σ, ρ)problems and locally checkable vertex partition problems to their distance versions, which naturally captures well-known problems such asDistance-rDominating SetandDistance-rIndependent Set. We show that these distance problems are inXPparameterized by the structural parameter mim-width, and hence polynomial-time solvable 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. We obtain these results by showing that taking any power of a graph never increases its mim-width by more than a factor of two. To supplement these findings, we show that many classes of (σ, ρ)problems are W[1]-hard parameterized by mim-width+ solution size. We show that powers of graphs of tree-width w −1or path-width wand powers of graphs of clique-width whave mim-width at most w. These results provide new classes of bounded mim-width. We prove a slight strengthening of the first statement which implies that, surprisingly,Leaf Powergraphs which are of importance in the field of phylogenetic studies have mim-width at most 1. © 2019 Elsevier B.V. All rights reserved.
URI
https://pr.ibs.re.kr/handle/8788114/6695
ISSN
0304-3975
Appears in Collections:
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > Discrete Mathematics Group(이산 수학 그룹) > Journal Papers (저널논문)
Files in This Item:
Mim-Width III Graph powers and generalized distance domination problems.pdfDownload

qrcode

  • facebook

    twitter

  • Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
해당 아이템을 이메일로 공유하기 원하시면 인증을 거치시기 바랍니다.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse