Testing whether the Grundy number of a given graph is at least , for a fixed constant , can be performed in polynomial time, by searching for all possible -atoms that might be subgraphs of the given graph. However, this algorithm is not fixed-parameter tractable, because the exponent in its running time depends on . When is an input variable rather than a parameter, the problem is NP-complete. The Grundy number is at most one plus the maximum degree of the graph, and it remains NP-complete to test whether it equals one plus the maximum degree. There exists a constant such that it is NP-hard under randomized reductions to approximate the Grundy number to within an approximation ratio better than .