  The generalized coloring numbers of Kierstead and Yang (Order 2003) offer an
algorithmically-useful characterization of graph classes with bounded
expansion. In this work, we consider the hardness and approximability of these
parameters. First, we complete the work of Grohe et al. (WG 2015) by showing
that computing the weak 2-coloring number is NP-hard. Our approach further
establishes that determining if a graph has weak $r$-coloring number at most
$k$ is para-NP-hard when parameterized by $k$ for all $r \geq 2$. We adapt this
to determining if a graph has $r$-coloring number at most $k$ as well, proving
para-NP-hardness for all $r \geq 2$. Para-NP-hardness implies that no XP
algorithm (runtime $O(n^{f(k)})$) exists for testing if a generalized coloring
number is at most $k$. Moreover, there exists a constant $c$ such that it is
NP-hard to approximate the generalized coloring numbers within a factor of $c$.
To complement these results, we give an approximation algorithm for the
generalized coloring numbers, improving both the runtime and approximation
factor of the existing approach of Dvo\v{r}\'{a}k (EuJC 2013). We prove that
greedily ordering vertices with small estimated backconnectivity achieves a
$(k-1)^{r-1}$-approximation for the $r$-coloring number and an
$O(k^{r-1})$-approximation for the weak $r$-coloring number.
