Skew-symmetrizable matrices play an essential role in the classification of cluster algebras. We prove that the problem of assigning a positive definite quasi-Cartan companion to a skew-symmetrizable matrix is in polynomial class P. We also present an algorithm to determine the finite type Δ ∈ {𝔸 n ; 𝔻 n ; 𝔹 n ; ℂ n ; 𝔼 6 ; 𝔼 7 ; 𝔼 8 ; 𝔽 4 ; 𝔾 2 } of a cluster algebra associated to the mutation-equivalence class of a connected skew-symmetrizable matrix B, if it has one.

Inflations algorithm is a procedure that appears implicitly in Ovsienko’s classical proof for the classification of positive definite integral quadratic forms. The best known upper asymptotic bound for its time complexity is an exponential one. In this paper we show that this bound can be tightened to O ( n 6 ) for the naive implementation. Also, we propose a new approach to show how to decide whether an admissible quasi-Cartan matrix is positive definite and compute the Dynkin type in just O ( n 3 ) operations taking an integer matrix as input.