Treewidth

Treewidth¹⁵ is a metric that can be used to measure the complexity of a graph and is based on the notion that many hard problems are actually extremely easy to solve on trees. Treewidth essentially says something about how close a graph is to being a tree. The notion of treewidth is extremely relevant to CPQs as CPQs have a treewidth of 2, this means that fixed parameter tractable (FTP) algorithms that have a runtime exponential in the treewidth can be viable solutions to problems involving CPQs.

However, one problem with treewidth is that it goes by many different names, the following list attempts to give an exhaustive overview of definitions used to refer to treewidth (or definitions later discovered to be equivalent to treewidth). It is worth noting that in order to make the treewidth of a tree 1, some definitions subtract 1 from the computed complexity value (e.g. a minimum width tree decomposition of a tree has bags of size 2, but the treewidth is 1).

The minimum width of a tree decomposition⁶. This is the size of the largest bag in the a tree decomposition with minimum bag size minus one.
The minimum clique number of a chordal supergraph⁶. Or alternatively⁴, if $G$ has treewidth at most $k$ then $G$ is a subgraph of a chordal graph with maximum clique size $k + 1$.
The minimum cost of an elimination order⁶.
The minimum $k$ for which a graph is a partial $k$-tree⁶. Or alternatively⁴, if $G$ has treewidth at most $k$ then $G$ is a partial $k$-tree.
By extension, a partial $k$-tree has treewidth $k$.
The minimum number of cops needed to catch a visible robber on a graph (minus one)⁶. This is based on the notion of havens where if a graph has a maximum order haven of order $k + 1$ then it has treewidth $k$.
In a family of connected subgraphs that all touch each other (vertex or edge shared). The maximum order of a bramble minus one, where the order of a bramble is the smallest hitting set that hits all the family subgraphs⁷.
The dimension of a graph by Bertelè and Brioschi^1,5 (not to be confused with the dimension of a graph as defined by Erdős, Harary and Tutte²). If the treewidth of $G$ is at most $k$ then the treewdith of $G$ is at most $k$⁴.
As defined in Halin’s study of S-functions^3,5.
If $G$ has treewidth at most $k$ then $G$ is $k$-decomposable⁴.
If $G$ has treewidth at most $k$ then $G$ has no screen of thickness at least $k + 2$⁴.
If $G$ has treewidth at most $k$ then $k + 1$ cops can search $G$ in the Seymour-Thomas search game⁴.
If $G$ has treewidth at most $k$ then $k + 1$ cops can monotonely search $G$ in the Seymour-Thomas search game⁴.
If $G$ has treewidth at most $k$ then the number of searchers, needed to search $G$ in the fugitive search game with an inert fugitive is at most $k + 1$⁴.
If $G$ has treewidth at most $k$ then the number of searchers, needed to monotonically search $G$ in the fugitive search game with an inert fugitive is at most $k + 1$⁴.

For a lot of useful properties of graphs of bounded treewidth (and similar notions) the survey paper by H. L. Bodlaender is a good start⁴.

Treewidth

References: