What do bags of decompositions represent?

One main aim of my work on local-global decompositions is to define a graph width parameter which captures precisely when a graph has dense local structure. Width in this context is the maximum size of a bag of a certain kind of graph-decomposition. So, for notions of “local width” to succeed, bags of decompositions must interact in some way with local dense structures. But how, exactly?

Tree-decompositions and treewidth

Let’s start where decompositions started: with tree-decompositions. The treewidth of a graph $G$ is large if and only if $G$ contains some dense structure. In particular, treewidth is agnostic to where, and specifically at what scale, the dense structure appears in $G$. Consider two examples of dense structures that $G$ could contain: the clique $K_t$ and a one-hundred-subdivision of the clique $K_t$. The clique $K_t$ is clearly a local dense structure, appearing in the neighborhood of any of its vertices.

But the one-hundred-subdivision of $K_t$ could be spread out all over $G$; indeed, the one-hundred-subdivision of $K_t$ could appear in a graph $G$ that is locally treelike, and therefore locally sparse, everywhere. In other words, although $K_t$ and its one-hundred-subdivision are both “dense structures” in $G$, they have very different qualitative behavior from a local-global perspective.

This is precisely the distinction that treewidth cannot make. If $G$ contains any subdivision of a $K_t$ – regardless of whether $G$ contains $K_t$ or its one-hundred- (or ten-million- or…) subdivision – then every tree-decomposition of $G$ will contain a bag of size at least $t$ which witnesses that a dense structure “of order $t$” appears in $G$.

This brings us to a question which I did not properly reflect on until recently, despite working with tree-decompositions for a while:

Where is local structure represented in a tree-decomposition?

The right answer, I think, is that it’s not.

This answer is in conflict with how I used to think about and describe tree-decompositions: as a way of “grouping together local pieces” of a graph in the “global shape” of a tree. But thinking of bags as “grouping local pieces” is misleading, and for a while this made it difficult for me to think clearly about tree-decompositions.¹

A better heuristic might be that tree-decompositions locate signatures of dense/highly-connected structures in a graph, so that the maximum size of such a dense structure is captured by the width.² This happens because trees, being trees, cannot absorb any dense or highly-connected structure, so in a tree-decomposition, anything dense/highly-connected in the graph has to appear somehow in the bags.

But the bags are not necessarily representing anything local. Consider again the example of a one-hundred-subdivision of $K_t$. A tree-decomposition of the one-hundred-subdivision of $K_t$ contains a bag with $t$ vertices that witnesses that there is a highly connected structure of order $t$ in the graph. This is clearly not a local structure despite appearing in a bag. Bags of tree-decompositions contain signatures of connected structures in the graph regardless of their scale. In other words, treewidth is a scale-invariant measure of dense substructures.

That treewidth is scale-invariant is also illustrated by the fact that the structures dual to tree-decompositions, like brambles or $k$-blocks, are scale-invariant by definition.

From tree-decompositions to local-global decompositions

Now we can return to our original goal, which is to define a graph-decomposition that is able to distinguish the scale of the dense substructures, say, by distinguishing between a (local) $K_t$ and a (global) one-hundred-subdivision of $K_t$. This is where our notions of $r$-acyclic and $r$-locally acyclic graph-decompositions come in.

In our framework, local pieces of a graph are the radius-$r/2$ balls of the graph. The key property that both $r$-acyclic and $r$-locally acyclic graph-decompositions have is that within these graph decompositions, every $r/2$-ball is represented in a tree-decomposition.

This means that if a dense or highly-connected structure appears in an $r/2$-ball $B$, the width of the decomposition will be large, since the tree-decomposition containing $B$ will have large width. Therefore, dense/highly-connected local pieces of the graph do indeed force the width to be high.

That’s half of what we want, which is for the width to be high if and only if the local structure is dense/highly-connected. Whether the “only if” part works remains to be seen. The reason why it has a hope of being true is that in $r$-acyclic/$r$-locally acyclic graph-decompositions, the model graph does not have to be a tree, and so the model graph can absorb dense or highly-connected global structures, in theory. There’s still some philosophical dilemma to be hashed out over what it means to have complicated local vs. global structure, a dilemma illustrated particularly well by the case of grids. If this interests you, stay tuned for a post on the global structure of grids!