Mim-Width III. Graph Powers and Generalized Distance Domination Problems
- Title
- Mim-Width III. Graph Powers and Generalized Distance Domination Problems
- Author
- 권오정
- Keywords
- Graph width parameters; Graph classes; Distance domination problems; Parameterized complexity; Graph powers; Leaf powers
- Issue Date
- 2019-12
- Publisher
- ELSEVIER SCIENCE BV
- Citation
- THEORETICAL COMPUTER SCIENCE, v. 796, page. 216-236
- Abstract
- We generalize the family of 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 in XP parameterized 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 -hard parameterized by mim-width + solution size.
We show that powers of graphs of tree-width or path-width w and powers of graphs of clique-width w have 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 Power graphs which are of importance in the field of phylogenetic studies have mim-width at most 1.
- URI
- https://www.sciencedirect.com/science/article/pii/S0304397519305560?via%3Dihubhttps://repository.hanyang.ac.kr/handle/20.500.11754/177000
- ISSN
- 0304-3975; 1879-2294
- DOI
- 10.1016/j.tcs.2019.09.012
- Appears in Collections:
- COLLEGE OF NATURAL SCIENCES[S](자연과학대학) > MATHEMATICS(수학과) > Articles
- Files in This Item:
- Mim-Width III. Graph Powers and Generalized Distance Domination Problems.pdfDownload
- Export
- RIS (EndNote)
- XLS (Excel)
- XML