  Let $k$ be an positive integer. For any two integers $i$ and $j$ in
$\{0,1,\dots,k-1\}$, let $|i-j|_k=\min\{|i-j|,k-|i-j|\}$ be the circular
distance between $i$ and $j$. Let $t$ be a nonnegative integer. Suppose $f$ is
a mapping from $V(G)$ to $\{0,1,\dots,k-1\}$. If adjacent vertices receive
different integers, and for each vertex $u$ of $G$, the number of neighbors $v$
of $u$ with $|f(u)-f(v)|_k=1$ is at most $t$, then $f$ is called a $t$-relaxed
2-distant circular $k$-coloring, or simply a $(\frac{k}{2},t)^*$-coloring of
$G$. If $G$ has a $(\frac{k}{2},t)^*$-coloring, then $G$ is called
$(\frac{k}{2},t)^*$-colorable. In this paper, we prove that, for any two fixed
integers $k$ and $t$ with $k\geq2$ and $t\geq1$, deciding whether $G$ is
$(\frac{k}{2},t)^*$-colorable is NP-complete expect the case $k=2$ and the case
$k=3$ and $t\leq3$, which are polynomially solvable. For any outerplanar graph
$G$, e show that all outerplanar graphs are $(\frac{5}{2},4)^*$-colorable, we
prove that there is no fixed positive integer $t$ such that all outerplanar
graphs are $(\frac{4}{2},t)^*$-colorable.
