  We prove $\textsf{NP-hardness}$ results for determining whether quivers are
mutation equivalent to quivers with given properties. Specifically, determining
whether a quiver is mutation-equivalent to a quiver with exactly $k$ arrows
between any two of its vertices is $\textsf{NP-hard}$. Also, determining
whether a quiver is mutation equivalent to a quiver with no edges between
frozen vertices is $\textsf{strongly NP-hard}$. Finally, we present a
characterization of mutation classes of quivers with two mutable vertices.
