  Let G be an undirected simple graph having n vertices and let f be a function
defined to be f:V(G) -> {0,..., n-1}. An f-factor of G is a spanning subgraph H
such that degree of a vertex v in H is f(v) for every vertex v in V(G). The
subgraph H is called a connected f-factor if, in addition, H is connected. A
classical result of Tutte(1954) is the polynomial time algorithm to check
whether a given graph has a specified f-factor. However, checking for the
presence of a connected f-factor is easily seen to generalize HAMILTONIAN CYCLE
and hence is NP-complete. In fact, the CONNECTED f-FACTOR problem remains
NP-complete even when we restrict f(v) to be at least n^e for each vertex v and
0<e<1; on the other side of the spectrum of nontrivial lower bounds on f, the
problem is known to be polynomial time solvable when f(v) is at least n/3 for
every vertex v. In this paper, we extend this line of work and obtain new
complexity results based on restrictions on the function f. In particular, we
show that when f(v) is restricted to be at least n/(log n)^c , the problem can
be solved in quasi-polynomial time in general and in randomized polynomial time
if c<=1. Furthermore, we show that when c>1, the problem is NP-intermediate.
