Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: On computing tree and path decompositions with metric constraints on the
  bags   We here investigate on the complexity of computing the \emph{tree-length} and
the \emph{tree-breadth} of any graph $G$, that are respectively the best
possible upper-bounds on the diameter and the radius of the bags in a tree
decomposition of $G$. \emph{Path-length} and \emph{path-breadth} are similarly
defined and studied for path decompositions. So far, it was already known that
tree-length is NP-hard to compute. We here prove it is also the case for
tree-breadth, path-length and path-breadth. Furthermore, we provide a more
detailed analysis on the complexity of computing the tree-breadth. In
particular, we show that graphs with tree-breadth one are in some sense the
hardest instances for the problem of computing the tree-breadth. We give new
properties of graphs with tree-breadth one. Then we use these properties in
order to recognize in polynomial-time all graphs with tree-breadth one that are
planar or bipartite graphs. On the way, we relate tree-breadth with the notion
of \emph{$k$-good} tree decompositions (for $k=1$), that have been introduced
in former work for routing. As a byproduct of the above relation, we prove that
deciding on the existence of a $k$-good tree decomposition is NP-complete (even
if $k=1$). All this answers open questions from the literature.

5
The categories of this paper are: gr-qc
14
The categories of this paper are: math-ph
29
The categories of this paper are: funct-an
17
The categories of this paper are: q-fin
32
The categories of this paper are: atom-ph
12
The categories of this paper are: nucl-th
33
The categories of this paper are: plasm-ph
3
The categories of this paper are: physics
0
The categories of this paper are: hep-ph
28
The categories of this paper are: alg-geom
15
The categories of this paper are: nucl-ex
35
The categories of this paper are: mtrl-th
9
The categories of this paper are: nlin
22
The categories of this paper are: chao-dyn
25
The categories of this paper are: patt-sol
30
The categories of this paper are: q-alg