Mim-Width I. Induced path problems
Lars Jaffke, O‐joung Kwon, Jan Arne Telle · Discrete Applied Mathematics · 2019
We initialize a series of papers deepening the understanding of algorithmic properties of the width parameter maximum induced matching width (mim-width) of graphs. In this first volume we provide the first polynomial-time algorithms on graphs of bounded mim-width for problems that are not locally checkable. In particular, we givenO(w)-time algorithms on graphs of mim-width at most w, when given a decomposition, for the following problems: Longest Induced Path, Induced Disjoint Paths and H -Induced Topological Minor for fixed H. Our results imply that the following graph classes have polynomial-time algorithms for these three problems: Interval and Bi-Interval graphs, Circular Arc, Permutation and Circular Permutation graphs, Convex graphs, k -Trapezoid, Circular k -Trapezoid, k -Polygon, Dilworth-k and Co- k -Degenerate graphs for fixed k. We contrast these positive results to the fact that problems about finding long non-induced paths remain hard on graphs of bounded mim-width: We show that Hamiltonian Cycle (and hence Hamiltonian Path) is NP-hard on graphs of linear mim-width 1; this further hints at the expressive power of the mim-width parameter.