Checking properties of matrices
The Faddeev-Leverrier algorithm seems to be a good start to answer your question, since it reduces the computation of $\alpha_k$ to matrix multiplications and traces. It runs in polynomial time (even in NC) and I guess any efficient treatment of sparse matrix operation carries to this algorithm.

Oddly enough the wikipedia page about that exists only in French and German:

https://fr.wikipedia.org/wiki/Algorithme_de_Faddeev-Leverrier

I found this article in english explaining the method:

http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1085-14.pdf