The Stokes multipliers in the matrix models are invariants in the string-theory moduli space and related to the D-instanton chemical potentials. They not only represent non-perturbative information but also play an important role in connecting various perturbative string theories in the moduli space. They are a key concept to the non-perturbative completion of string theory and also expected to imply some remnant of strong coupling dynamics in M theory. In this paper, we investigate the non-perturbative completion problem consisting of two constraints on the Stokes multipliers. As the first constraint, Stokes phenomena which realize the multi-cut geometry are studied in the Zk symmetric critical points of the multi-cut two-matrix models. Sequence of solutions to the constraints are obtained in general k-cut critical points. A discrete set of solutions and a continuum set of solutions are explicitly shown, and they can be classified by several constrained configurations of the Young diagram. As the second constraint, we discuss non-perturbative stability of backgrounds in terms of the Riemann–Hilbert problem. In particular, our procedure in the 2-cut (1,2) case (pure-supergravity case) completely fixes the D-instanton chemical potentials and results in the Hastings–McLeod solution to the Painlevé II equation. It is also stressed that the Riemann–Hilbert approach realizes an off-shell background independent formulation of non-critical string theory.