  We introduce a new framework for reconfiguration problems, and apply it to
independent sets as the first example. Suppose that we are given an independent
set $I_0$ of a graph $G$, and an integer $l \ge 0$ which represents a lower
bound on the size of any independent set of $G$. Then, we are asked to find an
independent set of $G$ having the maximum size among independent sets that are
reachable from $I_0$ by either adding or removing a single vertex at a time
such that all intermediate independent sets are of size at least $l$. We show
that this problem is PSPACE-hard even for bounded pathwidth graphs, and remains
NP-hard for planar graphs. On the other hand, we give a linear-time algorithm
to solve the problem for chordal graphs. We also study the fixed-parameter
(in)tractability of the problem with respect to the following three parameters:
the degeneracy $d$ of an input graph, a lower bound $l$ on the size of the
independent sets, and a lower bound $s$ on the solution size. We show that the
problem is fixed-parameter intractable when only one of $d$, $l$, and $s$ is
taken as a parameter. On the other hand, we give a fixed-parameter algorithm
when parameterized by $s+d$; this result implies that the problem parameterized
only by $s$ is fixed-parameter tractable for planar graphs, and for bounded
treewidth graphs.
