We consider the problem of recognizing graphs containing an f-factor (for any constant f) over the class of partial k-tree complements. We also consider a variation of this problem that only recognizes graphs containing a connected f-factor: this variation generalizes the Hamiltonian circuit problem. We show that these problems have O(n) algorithms for partial k-tree complements (on n vertices); we assume that the Θ(n2) edges of such a graph are specified by representing the O(n) edges of its complement. As a preliminary result of independent interest, we demonstrate a logical language in which, if a graph property can be expressed over the class of partial k-tree complements, then those graphs that satisfy the property can be recognized in O(n) time.