  We show that the problem of whether a query is equivalent to a query of
tree-width $k$ is decidable, for the class of Unions of Conjunctive Regular
Path Queries with two-way navigation (UC2RPQs). A previous result by Barcel\'o,
Romero, and Vardi [SIAM Journal on Computing, 2016] has shown decidability for
the case $k=1$, and here we extend this result showing that decidability in
fact holds for any arbitrary $k\geq 1$. The algorithm is in 2ExpSpace, but for
the restricted but practically relevant case where all regular expressions of
the query are of the form $a^*$ or $(a_1 + \dotsb + a_n)$ we show that the
complexity of the problem drops to $\Pi^P_2$.
  We also investigate the related problem of approximating a UC2RPQ by queries
of small tree-width. We exhibit an algorithm which, for any fixed number $k$,
builds the maximal under-approximation of tree-width $k$ of a UC2RPQ. The
maximal under-approximation of tree-width $k$ of a query $q$ is a query $q'$ of
tree-width $k$ which is contained in $q$ in a maximal and unique way, that is,
such that for every query $q''$ of tree-width $k$, if $q''$ is contained in $q$
then $q''$ is also contained in $q'$.
  Our approach is shown to be robust, in the sense that it allows also to test
equivalence with queries of a given path-width, it also covers the previously
known result for $k=1$, and it allows to test for equivalence of whether a
(one-way) UCRPQ is equivalent to a UCRPQ of a given tree-width (or path-width).
