How to efficiently check if a superoperator is Lindbladian? Superoperators are linear maps on the vector space of linear operator. The Lindbladian superoperators are the important subset that can be expressed in the form $$\mathcal{L}[\rho] = -i (H \rho - \rho H) + \sum_i L_i\rho L_i^\dagger - \frac{1}{2}(L_i^\dagger L_i \rho +  \rho L_i^\dagger L_i)$$ for some Hermitian operator $H$ with positive anti-Hermitian part, $H-H^\dagger \ge 0$, and some set of operators $\{L^{i}\}$.  Lindbladians are important in the study of open quantum systems because they generate completely positive trace-preserving maps on density matrices, $\exp(t \mathcal{L})$ for $t\ge 0$, which describe Markovian dynamics.
What is the most "checkable" criteria for determining whether a given superoperator $\mathcal{S}$ is Lindbladian?  (Obviously, exhaustively searching for $H$ and $\{L^{i}\}$ is not reasonable.)  
For concreteness, suppose our operators $\rho$ act on $N$ dimension vectors spaces, so we can organize their matrix elements into a vector of length $N^2$, making the superoperators $N^2 \times N^2$ matrices.  What algorithm can efficiently check whether a given $N^2 \times N^2$ matrix is Lindbladian?
 A: Depending on what you need this is only a (very) partial answer to the question, because it includes only necessary conditions for an operator to be Lindbladian, not sufficient ones (as far as I know).
Lindbladians have two important properties: they generate (1) trace-preserving and (2) completely positive evolution.


*

*A necessary condition for a superoperator $\mathcal{L}$ to generate a trace-preserving evolution is 
$$ \mathcal{L}^\dagger[\mathbb{1}] = 0.$$
It is easy to check since it requires only Hermitian conjugation of the matrix $\mathcal{L}$ and multiplication with the identity "vector" $\mathbb{1}$. 

*A necessary condition for $\mathcal{L}$ to generate a positive semi-group is that the real part of the eigenvalues of $\mathcal{L}$ are non-positive. This is less easy to check since one has to diagonalise an $N\times N$ matrix.
A: First, note that if we allow the Hamiltonian $H$ to have an anti-Hermitian part which is a positive semi-definite operator, $H-H^\dagger \ge 0$, then $\mathcal{L}$ still generates CP time evolution $e^{t\mathcal{L}}$; it's just not trace preserving unless $H-H^\dagger=0$.  Let's call the not-necessarily-trace-preserving class of superoperators Lindbladian, and call the trace-preserving subset completely dissipative.  (The latter name is the terminology that Lindblad originally used.)
Then with some effort one can show $\mathcal{L}$ is Lindbladian if and only if $$\qquad\qquad\qquad\qquad\mathcal{P} \mathcal{L}^{\mathrm{PT}} \mathcal{P} \ge 0,\qquad\qquad\qquad\qquad (1) $$
where $\mathcal{P} \equiv \mathcal{I} - \mathcal{I}^{\mathrm{PT}}/N = \mathcal{P}^2$ is the "superprojector" that removes an operator's trace, so that $\mathcal{P}[B] = B - (\mathrm{Tr}[B]/N)I$.  Note that $\mathcal{S} \ge 0$ means that a superoperator $\mathcal{S}$ is a positive operator (when considered as an operator on the space of operators/matrices) in the sense of being Hermitian with positive eigenvalues or, equivalently, that $\langle B, \mathcal{S}[B]\rangle \ge 0$ for all operators $B$, where $\langle B, C \rangle \equiv \mathrm{Tr}[B^\dagger C]$ is the Hilbert-Schmidt inner product on the space of operators.  This is a distinct condition from $\mathcal{S}$ being positivity preserving, i.e., $B\ge 0 \Rightarrow \mathcal{S}[B]\ge 0$, which is (confusingly) usually described as $\mathcal{S}$ being a "positive map".
An equivalent condition to Eq. (1) is $$\qquad\qquad\overline{P}_\Psi[ (\mathcal{L}\otimes \mathcal{I})(|\Psi \rangle\langle \Psi|)] \overline{P}_\Psi \ge 0,\qquad\qquad(2)$$ where $|\Psi \rangle = N^{-1} \sum_{n=1}^N|n\rangle|n\rangle$ is some maximally entangled state and $\overline{P}_\Psi=I - |\Psi \rangle\langle \Psi|$ projects onto the orthogonal subspace.  (This condition is independent of the choice of basis $\{|n\rangle\}$ and hence the choice of maximally entangled state $|\Psi \rangle$.)  Eq. (2) is also a condition about positivity of a linear operator, but in this case it's a condition on a tensor product of two ($N \times N$) density matrices rather than a condition on a single ($N^2 \times N^2$) superoperator as in Eq. (1).
Eq. (2) is the form the Lindbladian condition appears in some monographs like Wolf's "Quantum Channels and Operations: Guided Tour" [PDF] (see eq. (7.15)) and, I think, Tarasov's "Quantum Mechanics of Non-Hamiltonian and Dissipative Systems" (see Sec. 15.8 and 15.9).  I prove Eq. (1) in a self-contained and elementary way in a blog post here.
If we want to further check whether $\mathcal{L}$ is completely dissipative and hence generates trace-preserving evolution (for all $B$, $\mathrm{Tr}[e^{t\mathcal{L}}[B]] = \mathrm{Tr}[B]$ or, equivalently, $\mathrm{Tr}[ \mathcal{L}[B]]=0$), then we just need to confirm a vanishing partial-trace condition, $$0 = \sum_{p=1}^N \mathcal{L}_{(pp)(nm)},$$ using the index convention $(\mathcal{S}[B])_{nn'} 
 = \sum_{m,m'=1}^N \mathcal{S}_{(nn')(mm')}B_{mm'}$.
