Relationship between the parameters tree width and the maximum degree

Question

I am working on parameterized complexity and started exploring on various structural parameters. The problem I am working on is known to be W[1]-hard parameterized by treewidth of the input graph and I am wondering if there is any known relationship between treewidth and maximum degree of the input graph. Could anyone provide the information containing the relationship between all the structural parameters. TIA.

Answer 1

There are no direct relation.

• The $n$-star (vertices $\{0,\dots,n\}$ and edges $(0,i)$ for $i>0$) has maximum degree $n$ and treewidth $1$.
• The $n \times n$-grid has maximal degree $4$ and treewidth $n$.

Granted, if your maximal degree is $2$ then the graph is a union of trees and cycles and hence has treewidth at most $2$. But starting from maximal degree $3$, you may have unbounded treewidth (for example, an expander of degree $3$ or the triangle grid).

What you have however is that for every $G = (V,E)$, $tw(G) \geq \min\{deg(v)\mid v \in V\}$. Indeed, let $T$ be a tree decomposition of $G$ of width $k$. We claim that there is a vertex of degree less than $k$ in $G$. For this, consider a leaf $l$ of $T$ and let $t$ be its father. If $B(l) \subseteq B(t)$, then you can remove $l$ from $T$ and still have a tree decomposition of $G$ of width $k$. Proceed until no more leaves of the tree decomposition can be removed.

Now you necessarily have a leaf $l$ such that $B(l) \not \subseteq B(t)$ where $t$ is the father of $l$. Hence, there exists $x \in B(l)$ that is not in $B(t)$. By connectivity, $x$ does not appear any other bag of $T$. Hence, every edges of $G$ having $x$ as an endpoint is covered in $B(l)$. In other words, $x$ has at most $k$ neighbors in $G$.

Answer 2

The parameters are independent. However, combining both parameters yield some interesting more restrictive parameters, where some hard problems become FPT.

First note that Graphs of bounded path width and bounded degree have bounded cutwidth. The other direction is clearly true, since both parameters are (up to a constant factor) a lower-bound for cutwidth.

There are a couple of generalizations of cutwidth that aim to avoid the restriction implied by the linear structure of the layout. The most prominent one is tree-cut width, which is more restrictive than treewidth (and hence, more problems are FPT parameterized by this parameter), but more general than $tw+d$, and hence, bounded when both are bounded.

However, in this case you might be more interested in ede-treewidth, since this parameter is bounded if and only if both treewidth and maximum degree are bounded in each biconnected component of the graph.

On a side note, another interesting generalization of cutwidth (that is also a restriction of treewidth) is the edge-cut width.