  In the recently introduced framework of solution discovery via
reconfiguration [Fellows et al., ECAI 2023], we are given an initial
configuration of $k$ tokens on a graph and the question is whether we can
transform this configuration into a feasible solution (for some problem) via a
bounded number $b$ of small modification steps. In this work, we study solution
discovery variants of polynomial-time solvable problems, namely Spanning Tree
Discovery, Shortest Path Discovery, Matching Discovery, and Vertex/Edge Cut
Discovery in the unrestricted token addition/removal model, the token jumping
model, and the token sliding model. In the unrestricted token addition/removal
model, we show that all four discovery variants remain in P. For the toking
jumping model we also prove containment in P, except for Vertex/Edge Cut
Discovery, for which we prove NP-completeness. Finally, in the token sliding
model, almost all considered problems become NP-complete, the exception being
Spanning Tree Discovery, which remains polynomial-time solvable. We then study
the parameterized complexity of the NP-complete problems and provide a full
classification of tractability with respect to the parameters solution size
(number of tokens) $k$ and transformation budget (number of steps) $b$. Along
the way, we observe strong connections between the solution discovery variants
of our base problems and their (weighted) rainbow variants as well as their
red-blue variants with cardinality constraints.
