3
$\begingroup$

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.

$\endgroup$

2 Answers 2

6
$\begingroup$

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$.

$\endgroup$
4
  • 1
    $\begingroup$ Even better, the $n \times n$ wall has maximum degree three and treewidth $\Omega(n)$. $\endgroup$
    – Pål GD
    Oct 26, 2022 at 20:39
  • 1
    $\begingroup$ Indeed, this is a fun one! $\endgroup$
    – holf
    Oct 26, 2022 at 20:50
  • $\begingroup$ @PålGD: "Wall" = like a grid but with lines only in one dimension? $\endgroup$
    – einpoklum
    Oct 30, 2022 at 8:29
  • $\begingroup$ No, it actually looks like a brick wall. Draw a brick wall and you'll see what I mean. You'll also note that the degree is 2 on the corners and three everywhere else. $\endgroup$
    – Pål GD
    Oct 30, 2022 at 9:10
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.