  In the last decade, algorithmic frameworks based on a structural graph
parameter called mim-width have been developed to solve generally NP-hard
problems. However, it is known that the frameworks cannot be applied to the
Clique problem, and the complexity status of many problems of finding dense
induced subgraphs remains open when parameterized by mim-width. In this paper,
we investigate the complexity of the problem of finding a maximum induced
subgraph that satisfies prescribed properties from a given graph with small
mim-width. We first give a meta-theorem implying that various induced subgraph
problems are NP-hard for bounded mim-width graphs. Moreover, we show that some
problems, including Clique and Induced Cluster Subgraph, remain NP-hard even
for graphs with (linear) mim-width at most 2. In contrast to the
intractability, we provide an algorithm that, given a graph and its branch
decomposition with mim-width at most 1, solves Induced Cluster Subgraph in
polynomial time. We emphasize that our algorithmic technique is applicable to
other problems such as Induced Polar Subgraph and Induced Split Subgraph. Since
a branch decomposition with mim-width at most 1 can be constructed in
polynomial time for block graphs, interval graphs, permutation graphs,
cographs, distance-hereditary graphs, convex graphs, and their complement
graphs, our positive results reveal the polynomial-time solvability of various
problems for these graph classes.
