The evolution of a complex multistate system is often interpreted as a continuous-time Markovian process. To model the relaxation dynamics of such systems, we introduce an ensemble of random sparse matrices which can be used as generators of Markovian evolution. The sparsity is controlled by a parameter φ, which is the number of nonzero elements per row and column in the generator matrix. Thus, a member of the ensemble is characterized by the Laplacian of a directed regular graph with D vertices (number of system states) and 2φD edges with randomly distributed weights. We study the effects of sparsity on the spectrum of the generator. Sparsity is shown to close the large spectral gap that is characteristic of nonsparse random generators. We show that the first moment of the eigenvalue distribution scales as ∼φ, while its variance is ∼φ. By using extreme value theory, we demonstrate how the shape of the spectral edges is determined by the tails of the corresponding weight distributions and clarify the behavior of the spectral gap as a function of D. Finally, we analyze complex spacing ratio statistics of ultrasparse generators, φ=const, and find that starting already at φ≥2, spectra of the generators exhibit universal properties typical of Ginibre's orthogonal ensemble.