We revisit the problem of deciding whether a finitely generated
subgroup H is a free factor of a given free group F. Known
algorithms solve this problem in time polynomial in the sum of the
lengths of the generators of H and exponential in the rank of
F. We show that the latter dependency can be made exponential
in the rank difference rank(F) - rank(H), which often makes a
significant change.