  Cluster algebras are a recent topic of study and have been shown to be a
useful tool to characterize structures in several knowledge fields. An
important problem is to establish whether or not a given cluster algebra is of
finite type. Using the standard definition, the problem is infeasible since it
uses mutations that can lead to an infinite process. Barot, Geiss and
Zelevinsky (2006) presented an easier way to verify if a given algebra is of
finite type, by testing that all chordless cycles of the graph related to the
algebra are cyclically oriented and that there exists a positive quasi-Cartan
companion of the skew-symmetrizable matrix related to the algebra. We develop
an algorithm that verifies these conditions and decides whether or not a
cluster algebra is of finite type in polynomial time. The second part of the
algorithm is used to prove that the more general problem to decide if a matrix
has a positive quasi-Cartan companion is in NP.
