patternMinor
Relationship between the parameters tree width and the maximum degree
Viewed 0 times
degreethemaximumbetweenwidthandparameterstreerelationship
Problem
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.
TIA.
Solution
There are no direct relation.
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$.
- 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$.
Context
StackExchange Computer Science Q#154953, answer score: 6
Revisions (0)
No revisions yet.