Title: Polynomial-time algorithms for the Longest Induced Path and Induced Disjoint Paths problems on graphs of bounded mim-width,
Abstract: We give the first polynomial-time algorithms on graphs of bounded maximum
induced matching width (mim-width) for problems that are not locally checkable.
In particular, we give $n^{\mathcal{O}(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$.