How fast can we decide whether a given DFA is minimal?
This might not be exactly the sort of answer you are looking for, but since you asked about decision problems, I thought you might be interested in the complexity of the problem. It is $\mathsf{NL}$-complete. 

Now, what does it mean for a DFA to be minimal? There are two properties:


Every state is reachable: $\forall q \in Q \; \exists w \in \Sigma^*$ such that we can reach $q$ from the start state $s$ by following $w$; in symbols: $s \rightarrow_w q$.
Every pair of states is distinguishable: $\forall q,r \in Q$ with $q \neq r$  $\exists w \in \Sigma^*$ such that $q \rightarrow_w s$ and $r \rightarrow_w t$ and $|\{s,t\} \cap F| = 1$ (only one of $s,t$ is an accept state).


Notice that the $x \rightarrow_w y$ can be computed in log-space (i.e. $\mathsf{L}$; just track your current position as you follow $w$ one letter at a time). Further, there is only a finite number of alternations between $\forall$ and $\exists$ so as a consequence of the Immerman-Szelepcsenyi theorem, we have that the problem is in $\mathsf{NL}$.

The easiest way to see that it is hard for $\mathsf{NL}$ is to notice that property 1 solves $s$-$t$ directed unreachability, which is the prototypical hard problem. But even if you consider only reachable DFAs, the problem is still hard (i.e. property 2 is $\mathsf{NL}$-hard) and you can find a relatively straightforward proof in Lemma 2.2 of Cho &amp; Huynh (1992).

Of course, I used non-determinism, so it is a bit of a cough-out in the way it differs from Hopcroft's algorithm. But we know that $\mathsf{NL} \subseteq \mathsf{L}^2$, so you can use those constructions to get yourself a more space-efficient algorithm than Hopcroft (which by its very nature has to keep track of $n$ many partitions).