Problem with a group as complexity parameter?
Many of the best results around graph isomorphism and permutation group algorithms are parametrized by some structure of a relevant group. For example, let $\mathcal{S}_d$ denote the class of groups all of whose composition factors are isomorphic to subgroups of $S_d$. Then coset intersection for groups in $\mathcal{S}_d$ can be solved in polynomial time for constant d. This is closely related to the polynomial-time isomorphism test for bounded-degree graphs. 

I think there are also several other problems that are solvable in polynomial time when certain associated groups are in $\mathcal{S}_d$ for $d=O(1)$, but I don't have references off the top of my head.