3
$\begingroup$

Here, by 3D-grid of sidelength $n$ I mean the graph $G=(V,E)$ with $V= \{1,\ldots,n\}^3$ and $E=\{( (a,b,c) ,(x,y,z) ) \mid |a-x|+|b-y|+|c-z|=1 \}$.

I known how to get the treewidth of $n*n$ grid is exactly $n$ from bramble:

  1. Firstly, we can construct a tree decomposition of $width=n$, which means $tw(n*n)\leq n$
  2. Secondly, we can construct a bramble of order n, which means $tw(n*n)\geq n-1$

a graph has a bramble of order $k$ if and only if it has treewidth at least $k − 1$

However, for a $n*n*n$ grid. We can simply get a path decomposition with pathwidth=$\Theta(n^2)$. But I don't know how to construct a bramble of order $n^2$ to confirm its lower bound.

My question: What is the treewidth of the 3D-grid (mesh or lattice) with sidelength n?

$\endgroup$
6
  • 1
    $\begingroup$ It is $\Omega(n^2)$ from a well-linked set argument but if you want a tight bound in terms of constants I do not know the right/clean answer. $\endgroup$ Jul 4, 2023 at 17:44
  • $\begingroup$ @ChandraChekuri $\Omega(n^2)$ is enough, I believe well-linked argument is right. However, I can't exactly write the proof about the size of $n^2$-linked set, how to describe there are enough paths? $\endgroup$
    – Jxb
    Jul 5, 2023 at 3:26
  • $\begingroup$ @ChandraChekuri Do you know bramble argument for $n*n*n$ grid? $\endgroup$
    – Jxb
    Jul 5, 2023 at 3:39
  • 2
    $\begingroup$ Related question (notice that treewidth <= pathwidth): cstheory.stackexchange.com/questions/4081/… $\endgroup$ Jul 5, 2023 at 14:49
  • 1
    $\begingroup$ @HermannGruber. I have gone through this answer and it can only provide an upper bound of treewidth if I understand correctly. $\endgroup$
    – Jxb
    Jul 6, 2023 at 1:31

1 Answer 1

3
$\begingroup$

It is $\Theta(n^2)$. The argument to prove the lower bound is that we can send an all-pairs concurrent flow of value $1$ and congestion $O(n^4)$, i.e., we can simultaneously send one unit of flow between every pair of vertices so that at most $O(n^4)$ units of flow go through any single vertex. This implies treewidth at least $\Omega(n^2)$, because on treewidth-$k$ graphs with $|V|$ vertices any such flow must have congestion at least $\Omega(|V|^2/k)$.

The construction to send the flow is as follows: Consider a pair of vertices represented by coordinates $(x_1,y_1,z_1)$ and $(x_2,y_2,z_2)$. We send one flow path of value one that goes with straight lines $(x_1,y_1,z_1)$->$(x_2,y_1,z_1)$->$(x_2,y_2,z_1)$->$(x_2,y_2,z_2)$.

Now, given a vertex $(x,y,z)$, for how many pairs $(x_1,y_1,z_1)$, $(x_2,y_2,z_2)$ does their flow path go through $(x,y,z)$? We observe that for a flow path between $(x_1,y_1,z_1)$ and $(x_2,y_2,z_2)$ to go through $(x,y,z)$, at least two coordinates of $(x,y,z)$ must be equal to a corresponding coordinate in either $(x_1,y_1,z_1)$ or $(x_2,y_2,z_2)$. Therefore, when given $(x,y,z)$, we have four degrees of freedom when selecting the pair $(x_1,y_1,z_1)$, $(x_2,y_2,z_2)$, so the number of such pairs is $O(n^4)$.

$\endgroup$
4
  • 2
    $\begingroup$ One can use similar routing to show that the $n^2$ vertices of the side of the grid is $c$-well-linked set for some fixed constant $c < 1$. A set $X$ is a $c$-well-linked set if for any partition of $X$ into $A$ and $B$ there are $\min(|A|,|B|)$ disjoint paths between $A$ and $B$ with congestion at most $c$. It is known that treewidth and size of well-linked sets are within a small constant of each other. $\endgroup$ Jul 6, 2023 at 15:02
  • $\begingroup$ This is a new concept for me, could you please offer some tutorials? I was even more confused after a Google search. $\endgroup$
    – Jxb
    Jul 7, 2023 at 9:20
  • 1
    $\begingroup$ Unfortunately there isn't a clean survey to point to. You can read a bit about these connections in a paper of mine with Julia Chuzhoy. arxiv.org/pdf/1305.6577.pdf (see Section 2 which describes well-linked sets and connection to treewidth). I also like Bruce Reed's survey on treewidth and tangles. cambridge.org/core/books/abs/surveys-in-combinatorics-1997/… $\endgroup$ Jul 7, 2023 at 15:09
  • $\begingroup$ @ChandraChekuri. Yeah, I can learn the connection between treewidth and well-linked sets from your paper. But I don't understand the connection of "congestion" and treewidth from Laakeri's answer. $\endgroup$
    – Jxb
    Jul 10, 2023 at 6:28

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.