Summary: 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 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 \((\sigma, \rho)\) problems are \(\text{W}[1]\)-hard parameterized by mim-width + solution size.
We show that powers of graphs of tree-width \(w - 1\) 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.
For Parts I and II see [L. Jaffke et al., Discrete Appl. Math. 278, 153–168 (2020; Zbl 1437.05223); Algorithmica 82, No. 1, 118–145 (2020; Zbl 1442.05158)].