  Given a graph $G$, the maximal induced subgraphs problem asks to enumerate
all maximal induced subgraphs of $G$ that belong to a certain hereditary graph
class. While its optimization version, known as the minimum vertex deletion
problem in literature, has been intensively studied, enumeration algorithms are
known for a few simple graph classes, e.g., independent sets, cliques, and
forests, until very recently [Conte and Uno, STOC 2019]. There is also a
connected variation of this problem, where one is concerned with only those
induced subgraphs that are connected. We introduce two new approaches, which
enable us to develop algorithms that solve both variations for a number of
important graph classes. A general technique that has been proved very powerful
in enumeration algorithms is to build a solution map, i.e., a multiple digraph
on all the solutions of the problem, and the key of this approach is to make
the solution map strongly connected, so that a simple traversal of the solution
map solves the problem. We introduce retaliation-free paths to certificate
strong connectedness of the solution map we build. Generalizing the idea of
Cohen, Kimelfeld, and Sagiv [JCSS 2008], we introduce the $t$-restricted
version, $t$ being a positive integer, of the maximal (connected) induced
subgraphs problem, and show that it is equivalent to the original problem in
terms of solvability in incremental polynomial time. Moreover, we give
reductions between the two variations, so that it suffices to solve one of the
variations for each class we study. Our work also leads to direct and simpler
proofs of several important known results.
