The right definition of decomposition

Recently, much of my work has revolved around the idea of graph-decompositions. Graph-decompositions are defined by taking the definition of tree-decomposition, crossing out “tree”, and writing “graph” instead. It’s reasonable to wonder whether this is obviously the right definition of graph-decomposition. What is the essence of a decomposition, and is the definition the best way to capture it?

While talking with my colleague Paul Knappe today, I became more convinced that the definition of graph-decomposition is actually the right definition. I am pretty happy about this! In mathematics, we have a lot of freedom to define things as we wish, and I am a big fan of having principled justifications¹ for the definitions we choose in the end.

The definition of graph-decomposition

The definition of graph-decomposition is as follows (it appears in this paper). A graph-decomposition $(H, \mathcal{V})$ of a graph $G$ consists of a graph $H$ and a set $\mathcal{V}$ of vertex-subsets $V_h \subseteq V(G)$ indexed by the nodes² of $H$, called bags, satisfying the following two properties:

• $(H1)$: every vertex and every edge of $G$ are contained in some bag of $(H, \mathcal{V})$:
  • $(H1a)$: $\bigcup_{h \in H} V_h = V(G)$, and
  • $(H1b)$: for every edge $e = uv$ of $G$, there is $h \in H$ such that ${u, v} \subseteq V_h$.
• $(H2)$: the set { $h \in V(H) \mid v \in V_h$ } induces a connected subgraph of $H$ for all vertices $v$ of $G$.

The properties $(H1)$ and $(H2)$, to me, play very different roles in this definition. Property $(H1)$ identifies what we mean by the word “decomposition” in this context: we mean a mapping of the vertices of $G$ into the nodes of another graph $H$ (that also maps edges of $G$ into nodes of $H$). Any natural definition of decomposition seems like it would include property $(H1)$.³

Property $(H2)$, on the other hand, feels more mysterious. It’s the condition that gives tree-decompositions, and by extension graph-decompositions, many of their important properties. But just how natural is $(H2)$? Could we replace $(H2)$ with some other condition, and still get decompositions with nice properties?

Decompositions from first principles

To try and address that question, let’s 1) isolate the barest definition of decomposition, 2) identify some properties that we want decompositions to have, and 3) investigate which conditions in the definition of decomposition could achieve those properties.

Given graphs $G$ and $H$, a decomposition $(H, \mathcal{V})$ of $G$ modelled on $H$ consists of $H$ and a set $\mathcal{V}$ of vertex-subsets $V_h \subseteq V(G)$ satisfying ($H1$), namely, that every vertex and every edge of $G$ appears in some set $V_h$. We also assume that every set $V_h$ is non-empty (otherwise we could just delete $h$ and $V_h$). We’ll use this as our “bare-bones” definition of decomposition: every type of decomposition that we consider will start here and add conditions. For example, the definition above starts here and adds $(H2)$ as a condition.

Substructures of $G$ naturally inherit decompositions from decompositions of $G$. For every decomposition $(H, \mathcal{V})$ of $G$ and every induced subgraph $F$ of $G$, we can define the decomposition of $F$ induced by $(H, \mathcal{V})$ as, essentially, the decomposition of $F$ that we get from $(H, \mathcal{V})$ by deleting everything that’s irrelevant to $F$. More formally, the decomposition of $F$ induced by $(H, \mathcal{V})$ is the decomposition $(H’, \mathcal{V}’)$, where $H’$ is the subgraph of $H$ induced by the nodes $h$ of $H$ such that $V_h \cap V(F) \neq \emptyset$, and $\mathcal{V}’$ is obtained by setting $V_h’ := V_h \cap V(F)$ for every node $h$ of $H’$. Observe that an induced decomposition of a decomposition is still a decomposition, i.e. it satisfies $(H1)$.

If a graph-decomposition satisfies property $(H2)$, then so does every decomposition induced by this decomposition. In fact, property $(H2)$ is even preserved under subgraphs and minors, not just induced subgraphs. This has a very useful consequence for tree-decompositions: given a tree-decomposition of $G$, we can find tree-decompositions of any induced subgraph, subgraph, or minor of $G$ that have width at most the tree-decomposition of $G$.

For this reason, let’s assume that we are only interested in decompositions that are hereditary. Specifically, let’s consider a class $\mathcal{D}$ of decompositions that satisfies the following: If a decomposition $(H, \mathcal{V})$ is in $\mathcal{D}$, then so is every decomposition induced by $(H, \mathcal{V})$.

Here is where things get interesting. This is what Paul and I observed today:

Theorem 1: Let $\mathcal{D}$ be a hereditary class of decompositions. The following are equivalent.

1. Every decomposition in $\mathcal{D}$ satisfies $(H2)$.
2. Every decomposition in $\mathcal{D}$ satisfies property $(H3)$: if $G$ is connected, then $H$ is connected.
3. Every decomposition in $\mathcal{D}$ satisfies property $(H4)$: every cut of $H$ corresponds to a separation of $G$.

I think this is so cool! Property $(H2)$ is mysterious, but properties $(H3)$ and $(H4)$ are intuitive if we want the graph $H$ to “represent the structure of $G$” in some way. They both say that important properties of $G$ can be “read off” from $H$ in a straightforward way. Property $(H3)$ says that a connected graph cannot be modelled on a disconnected graph. Property $(H4)$ is more general: it says that edge cutsets in the model graph $H$ correspond to vertex separators in the graph $G$. (This corresponds to the classic theorem that edges of tree-decompositions correspond to separations in graphs, because every edge of a tree-decomposition is an edge cutset of the tree.)

The point of a decomposition is to model a graph $G$ on a (simpler) graph $H$ in such a way that (some) important information about $G$ is retained. I believe that “the structure of separations in $G$” is a very reasonable candidate for the “important information” that we want decompositions to have. Therefore, to me, Theorem 1 is a nice justification for why $(H2)$ is the “right” definition of graph-decomposition.

Proving Theorem 1

The proof of Theorem 1 is not too difficult, but let’s first be more explicit about what we mean that every cut of $H$ corresponds to a separation of $G$.

A cut of $H$ is a partition $(U, W)$ of the vertex set of $H$. The edge cutset corresponding to cut $(P, Q)$ is the set of edges $F$ of $H$ with one end in $P$ and one end in $Q$.

A separation of $G$ is a triple $(A, C, B)$ of the vertex set of $G$ such that $A, C, B$ is a partition of $V(G)$ and there is no edge with one end in $A$ and other end in $B$. The set $C$ is called the vertex separator of the separation.

Suppose that $(H, \mathcal{V})$ is a decomposition of $G$. Let $(U, W)$ be a cut of $H$ with edge cutset $F$. Then, we say that $(U, W)$ corresponds to the following triple $(A, C, B)$ of $G$:

• $C := \bigcup_{hh’ \in F} V_h \cap V_{h’}$,
• $A := (\bigcup_{h \in U} V_h) \setminus C$,
• $B := (\bigcup_{h \in W} V_h) \setminus C$.

Now, we can make property $(H4)$ more precise: for every cut of $H$, the triple of $G$ corresponding to the cut is a separation in $G$.

With this definition in hand, we can briefly sketch the proof of Theorem 1.

Proof sketch of Theorem 1:

• 2 implies 1: by applying $(H3)$ to the single-vertex subgraphs of $G$.

• 3 implies 2: via a proof by contradiction: suppose that $H$ is disconnected. Then, we can choose a cut $(U, W)$ of $H$ such that $U$ and $W$ are both non-empty but the edge cutset $F$ for $(U, W)$ is empty. Now we can apply property $(H4)$ to the cut $(U, W)$ and conclude that the corresponding triple $(A, C, B)$ is a separation of $G$. Since $F$ is empty, it follows that $C$ is empty, but since $U$ and $W$ are both non-empty, it follows that $A$ and $B$ are also both non-empty. This implies that $G$ is disconnected, a contradiction.

• 1 implies 3: follows from the following observation. Let $(U, W)$ be a cut of $H$ with edge cutset $F$, and let $(A, C, B)$ be the triple of $G$ corresponding to $(U, W)$. Suppose that for some vertex $v$ of $G$, there is $u \in U$ and $w \in W$ such that $v \in V_u \cap V_w$. Then, property $(H2)$ implies that there is an edge $hh’ \in F$ such that $v \in V_h \cap V_{h’}$, so $v$ is in $C$. Informally: every vertex of $G$ which “crosses the cut” in $H$ appears in the separator of $G$. (See Lemma 3.4 here for more details.)

These three implications together show that 1, 2, and 3 are equivalent.

Is $(H1b)$ self-evident?

As a concluding thought, I’ll return to the question from footnote 3 earlier. I started from the assumption that $(H1)$ is the “barest-bones” definition of decomposition that we should consider. But I think it’s fair to question the assumption that $(H1b)$ is obviously a feature of a reasonable definition of decomposition. For example, neither the proof that 2 implies 1 nor the proof that 3 implies 2 requires property $(H1b)$ – though the proof that 1 implies 3 does. What if we drop the condition $(H1b)$ and require only $(H1a)$?

The decomposition defined via $(H1a)$ and $(H2)$ was mentioned in Section 3.1 of this paper by Carmesin and Kurkofka as a mixed-tree-decomposition. They remark that edges of mixed-tree-decompositions correspond to what they call mixed separations, which are essentially any pair $(A, B)$ of vertex-subsets of $G$ such that $A \cup B = V(G)$. But the picture here is trickier, because $(H2)$ is not necessary for edges of a mixed-tree-decomposition to correspond to mixed separations.

Another reason to like $(H1b)$ is that it enables condition $(H2)$ to be inherited under edge contraction, so condition $(H2)$ can be inherited by minors. But here we could instead consider a slight weakening of $(H1b)$:

$(H1b’)$: for every edge $uv$ of $G$, there is an edge $hh’$ of $H$ such that ${u, v} \subseteq V_h \cup V_{h’}$.

In $(H1b’)$, we require that edges of the graph are represented by vertices or edges of the decomposition. This seems pretty reasonable to me, at least on the face of it. $(H1b’)$ is sufficient to allow decompositions to be inherited under minors, and more generally to guarantee that connected subgraphs of $G$ live in connected subgraphs of $H$. Indeed, if we want a decomposition $(H, \mathcal{V})$ of $G$ satisfying only $(H1a)$ and $(H2)$ (but not necessarily $(H1b)$) to also satisfy the property that connected subgraphs of $G$ live in connected subgraphs of $H$, then $(H1b’)$ is necessary (by considering the connected subgraphs of $G$ corresponding to its edges).

Replacing $(H1b)$ with $(H1b’)$ does break the property $(H4)$, though, even when $H$ is a tree. One could play around with ways to fix this. Mixed separations are one possibility. So is adding both ends of an edge of $G$ that crosses the cut of $H$ to the vertex-separator $C$ when we define how cuts of $H$ correspond to triples of $G$. I haven’t thought about this, but it’s possible that someone else has.

(Small update: after more discussion, Paul and I are not convinced that relaxing $(H1b)$ to $(H1b’)$ can meaningfully improve decompositions. For instance, can the minimum width of a tree-decomposition of $G$ where $(H1b)$ is replaced by $(H1b’)$ have meaningfully lower width than the treewidth of $G$? I don’t know, but probably guess not. If $(H1b’)$ doesn’t meaningfully improve over $(H1b)$, that’s even more evidence, in my opinion, that we’ve found the “right” definition of decomposition.)

That’s all I have to say about this for now. Thanks for reading!

And special thanks to Paul Knappe for the conversations that led to this post and for comments on the post that improved the writing.