  Reconfiguration problems require finding a step-by-step transformation
between a pair of feasible solutions for a particular problem. The primary
concern in Theoretical Computer Science has been revealing their computational
complexity for classical problems.
  This paper presents an initial study on reconfiguration problems derived from
a submodular function, which has more of a flavor of Data Mining. Our
submodular reconfiguration problems request to find a solution sequence
connecting two input solutions such that each solution has an objective value
above a threshold in a submodular function $f: 2^{[n]} \to \mathbb{R}_+$ and is
obtained from the previous one by applying a simple transformation rule. We
formulate three reconfiguration problems: Monotone Submodular Reconfiguration
(MSReco), which applies to influence maximization, and two versions of
Unconstrained Submodular Reconfiguration (USReco), which apply to determinantal
point processes. Our contributions are summarized as follows:
  1. We prove that MSReco and USReco are both $\mathsf{PSPACE}$-complete.
  2. We design a $\frac{1}{2}$-approximation algorithm for MSReco and a
$\frac{1}{n}$-approximation algorithm for (one version of) USReco.
  3. We devise inapproximability results that approximating the optimum value
of MSReco within a $(1-\frac{1+\epsilon}{n^2})$-factor is
$\mathsf{PSPACE}$-hard, and we cannot find a
$(\frac{5}{6}+\epsilon)$-approximation for USReco.
  4. We conduct numerical study on the reconfiguration version of influence
maximization and determinantal point processes using real-world social network
and movie rating data.
