The right definition of decomposition, part II

In a previous post, I discussed some reasons why I like the definition of graph-decomposition. But why do I care about graph-decompositions to begin with? In this post, I go deeper into what I hope graph-decompositions can do.

This post closely follows this talk, so check that out instead if you prefer videos! This post also covers similar content as Reinhard Diestel’s article ‘A width parameter that exhibits local-global structure’ from this Oberwolfach report.

Aiming at local-vs-global

My introduction to graph-decompositions came after I moved to Hamburg and began to think about the themes of local and global in the context of graphs.¹ Many people who work with graphs seem to develop similar intuitions about what the words “local” and “global” mean. For example, high chromatic number is often described as a property that can occur for both local and global reasons, in the following way:

• some graphs have high chromatic number only because they contain a large clique, so high chromatic number is a local phenomenon
• other graphs have high chromatic number and high girth², so high chromatic number is a global phenomenon

Using this example as a guiding intuition, let’s try to formally define local and global. One of these is far more straightforward than the other: the definition of local, which appears so often in my ideas that I’ve made a short post dedicated solely to explaining what I mean by local. In short: for a parameter $r$, the $r$-local pieces of a graph are its balls of radius $r/2$. Essentially: features are local in $G$ when they are featured in its bounded-radius subgraphs.

In any case, the definition of local is straightforward, well-defined, and aligns with our guiding example. It’s something intuitive that we can work with. But it doesn’t help us come up with a definition of global, and there doesn’t seem to be low-hanging fruit in that regard. If we wanted to simply define global as “not-local,” how would we do that? If we wanted to pick a basic, intuitive definition, what would that be? These questions are elusive: there doesn’t seem to be a natural way to nail down exactly what we mean by “global.”

Seeking “global” in decompositions

I can turn to my own previous work for inspiration as to what we might mean by “global.” In the past, I frequently used the term “globally treelike” as a heuristic for the type of graphs I studied: those with bounded treewidth. In other words, having a well-fitting (i.e. low width) tree-decomposition is commonly understood as formalizing the idea that a graph is “globally treelike.” Another way to understand what globally treelike means is that such graphs have no complex global structure. What can we do, then, to represent the global structure of graphs that do have some nontrivial global structure?

We can try to still use decompositions for this purpose by positing that certain graph-decompositions are witnesses of a graph’s global structure. Specifically, we want to be able to say that if $(H, \mathcal{V})$ is a well-fitting graph-decomposition of $G$, the graph $H$ represents the “global structure” of $G$. Under what conditions could this make sense?

We need to have at least two things:

1. A width parameter where low width corresponds to a “well-fitting” decomposition; and
2. some sensible way of saying that the graph $H$ represents the global structure of $G$.

We can reuse the notion of width from tree-decompositions: the width of a graph-decomposition $(H, \mathcal{V})$ is the maximum size of its bags; i.e. $\max_{h \in H} |V_h|$.³ This takes care of the first point. Observe that as long as $G$ has at least one edge, every graph-decomposition of $G$ has width at least two.

In fact, every graph $G$ has a graph-decomposition of width at most two. Let $H$ be the graph formed from $G$ by subdividing every edge exactly once, and name the vertex formed by subdividing edge $uv$ as $z_{uv}$. Now, set $V_h := {h}$ if $h$ is a vertex of $G$ and $V_h = {u, v}$ if $h = z_{uv}$. This yields a graph-decomposition of $G$ of width at most two.

We don’t want to consider the one-subdivision of $G$ to be a good representation of the structure of $G$, because it’s too close to $G$ itself – it displays all the information about $G$, and hides nothing. This is why we need condition 2. above: we want graph-decompositions that hide some information and display some information. More specifically, we want to find graph-decompositions that hide local information and display global information.

Why graph-decompositions don’t work…

A natural idea for how to restrict the graph-decompositions that we consider is to restrict the structure of the model graph $H$. This is, after all, what tree-decompositions do: tree-decompositions require that the model graph $H$ be a tree. Maybe if we require $H$ to be sparse, or planar, or something along those lines, we could get good decompositions?

Unfortunately, Diestel and Kuhn – who first proposed generalizing tree-decompositions to graph-decompositions – observed that this idea will not work. Suppose that $\mathcal{H}$ is a class of graphs, and let $\mathcal{H}$-decompositions denote graph-decompositions $(H, \mathcal{V})$ where $H \in \mathcal{H}$. (For example, in this notation, if $\mathcal{T}$ is the class of all trees, then $\mathcal{T}$-decompositions are precisely tree-decompositions.)

Perhaps unexpectedly, it turns out that the class of $\mathcal{H}$-decompositions is only interesting if $\mathcal{H} = \mathcal{T}$. Here’s why. Fix a graph $G$, and suppose our task is to find an $\mathcal{H}$-decomposition of $G$ of minimum width. There are two possibilities:

• The class $\mathcal{H}$ has bounded treewidth.
  If this is the case, then the minimum width of an $\mathcal{H}$-decomposition of $G$ is some constant function of the treewidth of $G$, so we might as well use tree-decompositions, which are easier to work with than arbitrary graph-decompositions.

• The class $\mathcal{H}$ has unbounded treewidth. If this is the case, then by the Grid Minor Theorem of Robertson and Seymour, $\mathcal{H}$ contains arbitrarily large grids.⁴ But every graph has a graph-decomposition of width two where $H$ is a grid. Let $V(G) = {v_1, …, v_n}$ and let $H$ be the $n \times n$-grid. Now, set $V_h := {v_i, v_j}$, where $h$ is the node of $H$ in the $i$th row and $j$th column. This gives a graph-decomposition of $G$ no matter what the structure of $G$ looks like - so we cannot say that this decomposition represents anything about the structure of $G$.

So we cannot get a meaningful notion of graph-decomposition just by restricting the structure of the model graph $H$.

… Or do they?

Let’s try to dig deeper into what a satisfying notion of “modelling global structure” might mean. At this point, we have two solid definitions to pull on: the definition of local and the definition of graph-decomposition.

One thing to notice about the definition of local is that, under the definition, short cycles are always local. Fix $r \geq 1$ and let $k \leq r$. Then, for every cycle $C_k$ and every vertex $v$ of $C_k$, it holds that $C_k \subseteq B_{C_k}(v, r/2)$. Therefore, whenever a short cycle appears in a graph $G$, the short cycle is a local feature of $G$ by definition.

Recall that we want our graph-decomposition to display global structure and hide local structure. So, what if we require the model graph $H$ to have high girth? This would guarantee that $H$ contains no short cycles.⁵ But it doesn’t work. For every integer $r \geq 1$, every graph-decomposition $(H, \mathcal{V})$ can be turned into a graph-decomposition $(H’, \mathcal{V}’)$ where $H’$ has girth greater than $r$: simply subdivide every edge $hh’$ of $H$ $r$ times, and make the bags of the new vertices equal to the bag of one of the ends. So we need to find a clever way to encode the idea that $H$ should not represent short cycles, without simply restricting the length of cycles in $H$.

We can do this in the following way. Let $G$ be a graph and $(H, \mathcal{V})$ a graph-decomposition of $G$. We say that $(H, \mathcal{V})$ is $r$-acyclic if for every set $X \subseteq V(G)$ of size at most $r$, the subgraph $\bigcup_{x \in X} H_x$ of $H$ is acyclic. (For a vertex $x$ of $G$, the set $H_x$ is defined to be $H_x := {h \in H \mid x \in V_h})$.) If $(H, \mathcal{V})$ is an $r$-acyclic graph-decomposition, then $H$ has girth greater than $r$, so $r$-acyclic does imply that the model graph has no short cycles. Indeed, it seems to imply much more than that.

Could $r$-acyclic graph-decompositions⁶ encode the “$r$-global structure” of $G$ in a meaningful way? Some of our recent results suggest that they could. For example, one concrete way that they are dual to the definition of $r$-local is the following implication:

Theorem. Let $G$ be a graph and let $(H, \mathcal{V})$ be an $r$-acyclic graph-decomposition of $G$. Then, for every vertex $v$ of $G$, the $r/2$-ball $B_G(v, r/2)$ around $v$ lives in a tree-decomposition within $(H, \mathcal{V})$. In other words, the $r$-local parts of $G$ are stored in tree-decompositions. Therefore, structure of $G$ that is reflected in any non-tree structure in $H$ is not local.

Questions, questions…

This idea is still in its very early stages, and there are lots of questions to explore. Some broad categories of questions include:

1. What are the properties of $r$-acyclic graph-decompositions?
2. Which graphs admit low-width $r$-acyclic graph-decompositions?
3. Can we use $r$-acyclic graph-decompositions to solve problems, either algorithmically or otherwise?
4. In what ways can we formalize the intuition that $r$-acyclic graph-decompositions “hide local structure” and “display global structure”?

I plan to go into more detail about some of these questions in posts coming soon, so stay tuned! And as always, please do write to me if you have any thoughts.