7
$\begingroup$

According to some slides I found on google, the treewidth of any $k \times k$ square grid graph $G$ is $tw(G) = k$. I just started researching about treewidth and tree decomposition, and for the most part it makes sense. However, I am particularly interested in the $k \times k$ square grid graph case, but have been struggling on how it is possible to make a tree decomposition of such a graph with that low of a width.

One of the problems I run into when trying to draw out decomposition trees of small square grids with groups of at most $k+1$ (to ensure a decomposition tree where the width is $k$) is that since the graph is "cyclic", one of the corner nodes shows up in two opposite ends of the tree, but not in any nodes on the path between the two. This clearly violates the coherence property of decomposition trees, which according to Wikipedia (which gives a more precise definition than most) is:

If $X_{i}$, $X_{j}$, and $X_{k}$ are nodes (in the decomposition tree), and $X_{k}$ is on the path from $X_{i}$ to $X_{j}$, then $X_{i}\cap X_{j}\subseteq X_{k}$.

For the case of the $3 \times 3$ graph, the only valid (or at least what I believe to be valid) decomposition tree I can think of contains 2 nodes: $\{\{1, 2, 3, 4, 6, 7, 8, 9\}, \{2, 4, 5, 6, 8\}\}$ where the nodes are labeled by row starting from the top left corner:

$1\space2\space3$

$4\space5\space6$

$7\space8\space9$

I did this by taking the perimeter vertices for the first tree node, and the inner vertex ($5$) along with its adjacent vertices to ensure all edges and vertices are included.

Ultimately, my question is, how can the treewidth of a square $k \times k$ square grid graph actually be equal to $k$? And if this is correct, could you present/explain a simple example of a decomposition tree that demonstrates this property?

$\endgroup$
  • $\begingroup$ Maybe they meant that the treewidth is $\Theta(k)$. This seems to be correct. $\endgroup$ – Yuval Filmus Sep 1 '16 at 6:20
  • $\begingroup$ @YuvalFilmus No, the treewidth really is $k$. $\endgroup$ – David Richerby Sep 1 '16 at 8:07
  • $\begingroup$ I've seen that it has to do with the bramble order being $k \plus 1$, but I'm looking for a concrete example of a tree decomposition that shows how this is possible. $\endgroup$ – saltthehash Sep 1 '16 at 8:09
11
$\begingroup$

The treewidth (and pathwidth) of the $k\times k$ grid is exactly $k$. (And, more generally, the treewidth and pathwidth of the $k\times\ell$ grid is exactly $\min\,\{k,\ell\}$). For the example grid

$$\begin{matrix}1&-&2&-&3\\|&&|&&|\\4&-&5&-&6\\|&&|&&|\\7&-&8&-&9\end{matrix}$$

the bags of the tree decomposition are $\{1,2,3,4\}, \{2,3,4,5\}, \{3,4,5,6\}, ..., \{6,7,8,9\}$.

Note that the bag $\{1,2,3,4\}$ already contains all edges adjacent to $1$, so we don't need to include that vertex ever again. Similarly, $\{2,3,4,5\}$ contains all of the edges adjacent to $2$ that weren't already in the first bag.

$\endgroup$
  • $\begingroup$ Wow, so... simple... I must have really been overthinking this one, looking for different kinds of patterns based on the geometry of the square. $\endgroup$ – saltthehash Sep 1 '16 at 8:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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