Merlin's Notebook

A blog by Benjamin Merlin Bumpus

Category: dynamic programming

• Compositional algorithms §2: quotienting solution spaces

Last time we spoke a bit about dynamic programming; specifically about solving Weighted Independent Set on trees. You can read about it here. Today things will get a bit more serious. I’ll start by briefly explaining how the algorithm we sketched for trees extends to graphs of bounded tree-width and then I’ll speak about the thing that makes dynamic programming fast: namely the quotinenting of solution spaces.
This last part is work in progress; feel free to share any feedback in the comments below.

Weighted independent set: from trees to graphs of bounded tree-width.

We already saw how to solve this problem on trees in the previous post in this series. The notation I chose for that post involved structured decompositions which, in case you need a reminder, look like this (see my paper with Zoltan Kocis and Jade Master for the real definition).

I will continue to handwave the definiton of structured decompositions for now since we’ll only use them to talk about tree decompositions.
Don’t worry, I’ll try to make things as general as possible in the next post.

The algorithm I sketched last time for the Maximum Weight Independent set generalized from structured decompositions of trees to structured decompositions of arbitrary graphs. Crucially, the efficiency of the algorithm carries over too: the running time of the algorithm scales exponentially in the size of the largest bag of the decomposition, but it remains linear in the overall input size.

Notation: The maximum bag-size of a strucrtured decomposition of graphs is called the width of the decomposition. In graph theory tree-shaped decompositions are called tree decompositions and the smallest width attainable for constructing a given graph $$G$$ with decomposition which is tree-shaped is called its tree-width. It is denoted $$\mathbf{tw}(G)$$.

Our algorithm for Weighted Independent Set follows the dynamic programming leitmotif:

• solve your problem on the bags (usually by brute force)
• working bottom-up from the leaves of the tree-shaped decomposition, combine local solutions to get ever-more-global solutions until we find the overall global solution.

For such algorithms to be fast (polynomial time) on some class, we need two things to be true:

• the class has to have bounded width
• we need to quotient the combined solution spaces as we go.

To really understand this last point, let’s look at an example. As before suppose we’re solving Weighted Independent Set. And, for simplicity, suppose we’re solving it on an input grah that admits a path-shaped decomposition $$(P, d)$$ of width $$k$$ (for some $$k \in \mathbb{N}$$) as in the following example.

Estimating things very roughly, let’s say that any n-vertex graph has at most $$2^n$$ different independent sets. Then, if we were to naïvely solve the independent set problem using the decomposition above, how long would this take?

Well the last step of the compositional algorithm would take time $$2^{|d x_1 +_{d e_{1,2}} d x_2 +_{d e_{2,3}} d x_3 )|} \times 2^{|d x_4|}$$ (I’m dropping parentheses to make things readable… and because I prefer it this way anyway). This is obviously very bad since it’s pretty much exponenetial in the size of the entire input graph.

The key insight we noticed last time is that we don’t need to carry around the entire set $$I_{1,2,3}$$ of all independent sets of $$d(x_1) +_{d(e_{1,2})} d(x_2) +_{d(e_{2,3})} d(x_3).$$ We only need to remember what $$I_{1,2,3}$$ looks like locally within $$d(x_3)$$. This insight allows us to speed up the algorithm into one running in time $$\sum_{ 1 \leq i \leq 4} f(|d(x_i)|)$$ for some exponential function $$f$$ which I’m not bothering to estimate right now (from experience, I’d guess it’s probably something like $$f: |d(x_i)| \mapsto 2^{2||d(x_i) |}$$, but I haven’t checked this..).

Notice that, if each bag has size bouded above by some constant $$k$$, then the runing time of the “quotiented’ version is linear in the input’s overall size!

Another example — this time “by picture”

It’s good to have at least another example on hand. It helps build intutition. So let’s now consider the Longest Path problem.

Longest Path

• Input: a graph G and an integer k.
• Question: does G contain a simple path of length at least k?

How does one solve this problem compositionally?

Well, it’s a standard exercise in paramterized complexity textbooks; indeed it’s so common that it features as one of the first dynamic programming exercises in Flum and Grohe’s textbook.

I’ll sketch the intuitive idea pictorially. Consider the following diagram where we have a path-shaped structured decomposition consisting of three bags $$d(x_1)$$, $$d(x_2)$$ and $$d(x_3)$$ (I’m leaving out the spans so things are easier to see).

Now how can we use the decomposition to solve the Longest Path problem? As John Baez puts it, there is a general trick for gaining intuition:

as always in mathematics, if you’re trying to figure out how to get something, it’s always good to pretend you already have it and then see what it’s like [so that] you can figure out how to get it.”

Let’s do exactly that. Suppose we are given an optimum solution (a longest path) as drawn in green below.

What does this path look like locally? Well, it’s a disjoint collection of paths (as I’ve highlighted in the second bag of the decomposition below).

This suggets an algorithm:

• enumerate all collections of disjoint paths in each bag (let’s call these local solutions);
• recursively try to join local solutions into larger and larger solutions.

Unruprisingly this algorithm follows the leitmotif we already mentioned.

Now, if you’re getting the hang of how these algorithms go, then your first question should be: “how do we quotient the solution space here?” Well, consider the following diagram.

We have three partial solutions: one in $$d(x_2)$$ (drawn in black) and two in $$d(x_1)$$ (drawn in green and violet respectively). Here’s the crucial observation: despite the fact that green and violet solutions are different, they link-up to the black solution in the same way. This is important because it means that any extension of the black+green solution (by means of some solution local to $$d(x_3)$$ ) is also an extension to the black+violet solution! In other words, from the perspective of answering the Longest path problem the two solutions are almost the same: we can forget the shorter path of the pair (black+green, black+violet).

Try to keep this example in mind. It will be useful for the next section.

Quotienting solution spaces in general

Things will get slightly category-theoretic now, so apologies if you don’t yet speak category-theory (I suggest Emily Riehl‘s book if you want to learn).

Let’s model algorithmic problems $$\mathcal{F}$$ on an input graph $$X$$ as a poset-valued presehaves; i.e. as functors of the form $$\mathcal{F}: (\mathbf{Sub} X)^{op} \to \mathbf{Pos}$$.

For example we could model Independent Set on the input $$X$$ as the functor $$\mathcal{I}: (\mathbf{Sub} X) ^{op}\to \mathbf{Pos}$$ taking each open $(X' \hookrightarrow X) \in \mathbf{Sub} X$ (i.e. a subgraph of $$X$$) to the poset (ordered by inclusion) of all independent sets in $$X’$$. On arrows, $$\mathcal{I}$$ takes $$X’ \subseteq X”$$ to the restriction map $$\mathcal{I}_{X’ \subseteq X”} : \mathcal{I} X” \to \mathcal{I} X’$$ taking each independet set $$\iota \in \mathcal{I}X”$$ to its restriction $$\iota|_{X’} \in \mathcal{I}X’$$ to $$X’$$ (this works because the property of being an independent set is closed under taking subgraphs).

It will be convenient to call an independent set $$\iota’$$ an extension of $$\iota$$ if $$\iota \subseteq \iota’$$ is a morphism of a solution space poset $$\mathcal{I}(X’)$$ which contains both of these independent sets (where $$X’$$ is some subgraph of $$X$$).

We’ll need some notation. Let $$Y \subseteq Y’$$ be any two subgraphs of $$X$$; we wish to define a functor $$\mathrm{Ext}_Y^{Y’}$$ which we’ll refer to as the $$(Y, Y’)$$-extension functor. This will be a contravariant functor $$\mathrm{Ext}_Y^{Y’}: \mathcal{I}Y^{op} \to \mathbf{Sub}\mathcal{I}Y’$$ taking

• each object $$\iota \in \mathcal{I}Y$$ to the poset (ordered by inclusion) of all those $$\iota’$$ in $$\mathcal{I}Y’$$ which restrict to $$\iota$$; i.e. $$\mathrm{Ext}_Y^{Y’}: \iota \mapsto (\{\iota’ \in Y’ | \mathcal{I}_{X’ \subseteq X”}(\iota’) = \iota\}, \subseteq)$$
• and each morphism $$\iota \subseteq \iota’$$ in $$\mathcal{I}Y$$ to the restriction $$\mathrm{Ext}_Y^{Y’}: (\iota \subseteq \iota’) \mapsto \bigl( \mathrm{Ext}_Y^{Y’}( \iota’ ) \to \mathrm{Ext}_Y^{Y’}(\iota) \bigr).$$ To see that this is well-defined, notice that, since $$\iota \subseteq \iota’$$, then for all $$\iota”$$, if $$\iota” \supseteq \iota’$$, then $$\iota” \supseteq \iota$$. (In particular this implies that $$\mathrm{Ext}_Y^{Y’}(\iota’)$$ is a subposet of $$\mathrm{Ext}_Y^{Y’}(\iota)$$.

With this notation, we’re ready to write down how I think “solution space quotienting” should go.

Solution space quotienting

The first two steps are obvious: we compute the solution spaces $$\mathcal{I}(dx)$$, $$\mathcal{I}(dy)$$, $$\mathcal{I}(de)$$ and we use these to compute the joint solution space $$\mathcal{I}(dx +_{de} dy)$$ as in the following diagram. (I’m glossing over how this computation is done, but, if you’re interested, then you can check out Section 6 of our paper where we show how to do this step for a fairly large class of problems.)

Now the quotienting starts. So first of all we compute the product

It’s the poset whose objects are pairs $$(\iota_1, \iota_2)$$ of elements of the solution space $$\mathcal{I}(d_x)$$ and the projections do the obvious thing; namely $$\pi_i: (\iota_1, \iota_2) \mapsto \iota_i$$.

Then we take the equalizer of $$\mathrm{Ext}_{dx}^{dx+_{d_e}dy} \circ \pi_1$$ and $$\mathrm{Ext}_{dx}^{dx+_{d_e}dy} \circ \pi_2$$ as follows.

The poset $$E$$ has underlying set $$\{(\iota_1, \iota_2) \in \mathcal{I}(d_x) \times \mathcal{I}(d_x) | (\mathrm{Ext}_{dx}^{dx+_{d_e}dy} \circ \pi_1)(\iota_1) = (\mathrm{Ext}_{dx}^{dx+_{d_e}dy} \circ \pi_2)(\iota_2)\}$$ consisting of all those local solutions $$\iota_1 \text{ and } \iota_2$$ in $\mathcal{I}(dx)$ which can be extended in exactly the same way in $$\mathcal{I}(d_y)$$.

Compare this to Figure 1 (the one with the green, violet and black paths).

Now, to actually do the quotienting, we compute the coequalizer of $$\pi_1 \varepsilon$$ and $$\pi_2 \varepsilon$$ as follows.

What does $$P_{x,y}$$ look like? It’s what you get when you quotient $$\mathcal{I}(dx)$$ by the equivalence relation defined by $$E$$; namely the equivalence relation that deems two elements $$\iota_1$$ and $$\iota_2$$ equivalent if they can be extended by exactly the same solutions in $$\mathcal{I}(dy)$$ (i.e. if $$(\iota_1, \iota_2) \in E$$).

The final step is to use this quotient $$P_{xy}$$ of $$\mathcal{I}(dx)$$ to remove the “spurious” information from $$\mathcal{I}(dx +_{de} dy)$$: namely we compute a subposet $$\mathcal{I}_{quot}(dx +_{de} dx)$$ of $$\mathcal{I}(dx +_{de} dy)$$ consisting of all those $$\iota \in \mathcal{I}(dx +_{de} dy)$$ which yield elements in $$P_{xy}$$ when restricted to $$dx$$.

The idea is that we would then proceed with our computations (as in the naïve algorithm) but using $$\mathcal{I}_{quot}(dx +_{de} dx)$$ instead of $$\mathcal{I}(dx +_{de} dy)$$ in all future iteration of the algorithms.

So does it work?

Well, I haven’t stated the computational task yet, so the question isn’t a fair one.

Let’s try to see if we get the right kind of objects for a couple of problems.

Sheaves

Recall that I wrote earlier that we could think of our computational problems on graphs as presheaves $$\mathcal{I}: (\mathbf{Sub}G)^{op} \to \mathbf{Pos}$$. A natural question to ask is whether the quotienting procedure I described above does the right thing when $$\mathcal{I}$$ is a sheaf.

Recall that a presheaf $$\mathcal{I}: (\mathbf{Sub}G)^{op} \to \mathbf{Pos}$$ is a sheaf if it satisfies the following sheaf condition.

Sheaf condition: suppose we are given a collection of subgraphs $$(G_j)_{j \in J}$$ and a collection of sections (i.e. solutions) $$\bigl (s_j \in \mathcal{I}(G_j) \bigr )_{j \in J}$$. If they pairwise agree (i.e. $$s_j|_{G_j \cap G_k} = s_k|_{G_j \cap G_k}$$ for all $$j,k$$ with $$j \neq k$$), then there is a unique section $$s \in \mathcal{I}( \mathrm{colim}_{j \in J}(G_j) )$$ restricting to each $$s_j$$ (i.e. $$s|_{G_j} = s_j$$ for all $$j \in J$$).

So what happens if we apply our construction to $$\mathcal{I}$$ when $$\mathcal{I}$$ is a sheaf? Well we need to figure out what the equalizer looks like:

As before, it’s underlying set consists of all pairs $$(\iota_1, \iota_2) \in \mathcal{I}(d_x) \times \mathcal{I}(d_x)$$ such that $$(\mathrm{Ext}_{dx}^{dx+_{d_e}dy} \circ \pi_1)(\iota_1) = (\mathrm{Ext}_{dx}^{dx+_{d_e}dy} \circ \pi_2)(\iota_2).$$ Now, since $$\mathcal{I}$$ is a sheaf, we immediately have that $$(\iota_1, \iota_2) \in E$$ if and only if $$\iota_1|_{de} = \iota_2|_{de}$$ (i.e. they agree on the boundary and hence are extendable by the same set of solutions in $$dy$$).

This means that the coequalizer $$(P_{xy}, \rho)$$

will quotient $$\mathcal{I}(dx)$$ under the equivalence relation which stipulates that two elements $$\iota_1, \iota_2 \in \mathcal{I}(dx)$$ are equivalent whenever they look the same in $$dx \cap dy = de$$. In particular this implies that $$\mathcal{I}_{quot}(dx +_{de} dy)$$ will be isomorphic to $$\mathcal{I}(dy)$$. Thus we’ve just found that the quotinenting was able to “figure out” that solving a “sheaf problem” amounts to filtering partial solutions!

Note that, by what we’ve just observed, we have obtained linear FPT-time algorithms for any sheaf-problem parameterized by the maximum size of a bag in a tree-shaped structured decomposition on graphs.

In of itself, since we stated it only for graphs, the result above is nothing new: after all it is already known that such problems are in FPT parameterized by tree-width.

However, it is easy to see that our result should generalize to any category and sheaf-problem (provided appropriate obvious computability conditions are satisfied by the category and sheaf in question).

So what can we encode as sheaves? Well, for starters, we can encode our favourite problem so far, the Max Independent Set problem! Furthermore, we can also encode the H-coloring problem which is defined as follows.

H-coloring

Input: we’re given graphs G and H

Question: is there a homomorphism from G to H?

When your presheaf ain’t a sheaf

We’ve seen that sheaves are particularly nice problems. However, it seems unlikely to me (despite being a “sheaf-novice”) that all computational problems should yield a sheaf. Examples of presheaves which fail to yield sheaves under the subobject topology include the Max Planar Subgraph and Longest Path presheaves.

Since we already mentioned Longest Path in this post, let’s stick with it and forget about Max Planar Subgraph for now.

A natural question is to ask: does the quotienting idea I presented above yield something useful for the Longest Path presheaf?

For starters, let’s define this presheaf; I’ll call it $\mathcal{L}: (\mathbf{Sub} G)^{op} \to \mathbf{Pos}.$\$ It takes each subgraph of G to the set of all collections of disjoint paths in that subgraph (see the diagrams earlier inthis post if you want something pictorial to stare at). On arrows $$\mathcal{L}$$ takes subgraphs $$G” \subseteq G’ \subseteq G$$ of $$G$$to the obvious restriction of path-forests in $$G”$$ to path-forests in $$G’$$.

Now, if you work-out what the quotienting does, you’ll find that $$\mathcal{L}_{quot}(d{x_1} +_{de_{12}} d{x_2})$$ sees the black+green and black+violet solutions below as equivalent.

The only issue is that the chosen representative for the equivalence class containing black+green and black+violet need not be the longest one.

This seems like a relatively easy issue to fix, so I’ll leave it as future work for myself. What is more pressing is determining whether the resulting quotiented solution space is small enough for fast dynamic programming.

To that end, I’ll cheat a little and use combinatorics. How big can $$\mathcal{L}_{quot}(dx_1 +_{1,2} dx_2 +_{2,3} \dots +_{k-1,k} dx_k)$$ be? Well, let’s ask how many non-isomorphic solutions there can be in the coequalizer $$P_{1,2,\dots,k}$$. After staring at it a bit, you’ll find that $$|P_{1,2,\dots,k-1}| \leq 2^{|d_{k-1,k}| \choose 2}$$ (where $$d_{k-1,k}$$ is the base of the span from the (k-1)-th bag to the k-th bag). To see this notice that two solutions of $$\mathcal{L}(dx_1 +_{1,2} dx_2 +_{2,3} \dots +_{k-2,k-1} dx_{k-1})$$ are identified in $$P_{1,2,\dots,k-1}$$ when they contract to the same thing in $$d_{k-1,k}$$. The number of these contractions is at most $$2^{|d_{k-1,k}| \choose 2}$$ (think of it as choosing to add an edge between a pair of vertices in $$d_{k-1,k}$$ if contracting some path to the left — i.e. a path in $$P_{1,2,\dots,k-1}$$ — identifies these vertices). This is great news since it means that our quotienting once again yields an FPT-time algorithm 🙂

Until Next time

A few notes on future work (ther are undoubtedly lots of directions I’ll forget to mention).

1. In the next post I’ll try to generalize the quotienting approach I’ve sketched here and lift it from graphs to other categories.
2. There is also some work to be done on how to ensure that we choose a “best” representative of the quotiented solution space.
3. The efficiency of the algorithm for sheaves was easy to show; however, for the Longest Path example, I resorted to some simple combinatorial estimation. Although it does the jobin this instance, this appraoch does not generalize, so more thought is needed on what properties can be imposed on the presheaves that define our problems that allow us to deduce upper-bound estimates (in terms of monomorphisms of solution spaces) on the size of the quotinented solution space.
4. There are a lot of $$(-)^{op}$$-s floating around. This is entirely because $$\mathrm{Ext}$$ is contravariant. It would be nice to avoid this somehow..

If you are perplexed or have any ideas/thoughts/reflections, please let me know in the comments (or otherwise).

Ciao!

• Compositional Algorithms

I’m fascinated by compositionality, the study of how the whole can be determined by its parts.

Category theorists will tell you that this topic sits entirely within their domain… and they’re not wrong, but fundamentally I think that most of mathematics has to do with some sort of compositionality.

One particular flavor of compositionality that interests me is that found in discrete mathematics; particualrly in graph theory and algorithms. This post will be the first in a series on compositional structure in graph theory and complexity theory.

Algorithms on recursive structure

Compositionality in complexity theory usually consists of exploiting some compositional structure of the input data. Trees are the prototypical example of recursive structure and, unsurprisingly, algorithms that compute on trees are usually compositional.

The rest of this post will use the pretext of solving the Weighted Independet Set problem on trees to set the scene for what is to come in the future.

The task is to find a vertex-subset $I$ of some input vertex-weighted tree $(T, w: V(T) \to \mathbb{N})$ which has maximum weight such that that no two vertices of $I$ are adjacent in $T$.

The compositional structure of trees comes in handy: trees can be built from smaller trees by glueing along shared copies of $K_1$ (the 1-vertex complete graph; I’ll abbreviate it simply as “$1$“). In category theory this is called a pushout; I’ll adopt this notation here: pick two vertices of two trees $T_1$ and $T_2$ — by choosing homomorphisms $T_1 \hookleftarrow 1 \hookrightarrow T_2$ — then the pushout of this diagram is the tree $T_1 +_{1} T_2$ obtained by “gluing” the image of $K_1$ in $T_1$ to its image in $T_2$.

Anyway, back to the weighted independet set. How does the compositional structure of trees help us solve our problem?

Well, suppose the input is given as the gluing $T_1 +_{1} T_2$ along some “root’ vertex $r$ and suppose further that we already computed all of the independent sets in $T_1$ and $T_2$ — let’s call these $\mathcal{I}_1$ and $\mathcal{I}_2$ –, then we observe that we can compute all of the independent sets in $T$ by matching-up the independent sets of $\mathcal{I}_1$ with those of $\mathcal{I}_2$. Explicitly, given any two independent sets $\iota_1$ and $\iota_2$ in $\mathcal{I}_1$ and $\mathcal{I}_2$, they can be combined into an independent set for $T$ iff $(\iota_1 \cup \iota_2)|_{N(r) \cup \{r\}}$ is an independent set in the closed neighborhood of $r$ (the vertex we glued the two trees along).

Now, even if you perhaps find this neat, you’re probably asking yourself two questions: (1) “why are we enumerating all independent sets? doesn’t this make the algorithm very slow?” and (2) “why can’t we just keep track of the biggest independent set on each side?” .. well, I’m glad you asked!

The second question has an easy answer which you can figure out for yourself by staring at this picture:

If we only kept track of the best solution on the RHS and LHS, then we might never find the global optimum (1002 in the example above). This also provides a partial answer to the first question: we need to keep track of all solutions in the LHS and RHS simply because we prefer correct algorithms over incorrect ones.

Now the question about speed is a good one. The algorithm above is very slow. Let’s improve it!

Notice that, when we composed the partial solutions $\iota_1$ and $\iota_2$, we only needed to check that their union gave us an independent set locally (i.e. on the closed neighborhood of $r$) in order to deduce that we could compose them. This suggests that we’re carying around way too much information: we don’t need to compute all of $\mathcal{I}_1$ and $\mathcal{I}_2$; we simply need to know what the members of $\mathcal{I}_1$ and $\mathcal{I}_2$ look like locally (i.e. in $N(r) \cup \{r\}$).

We could go ahead and turn this into a fast algorithm now, but let’s wait and instead take some time to set-up some better notation.

Interlude on Structured decompositions

The tool we’ll need is called a structured decomposition, a general way of decomposing stuff into smaller constituent parts that Zoltan A. Kocsis, Jade Edenstar Master and I came up with. Roughly you should think of them as generalized graphs: rather than consisting of a set of vertices and an edge relation on this set, a structured decomposition is a collection of bags and a generalized relation on this collection. Here I’ll keep it simple, so I’ll avoid the general setting and I’ll only give the definition for graphs.

Fix the category $\mathbf{Gr}$ of graphs and graph homomorphisms. A structured decomposition of graphs (which I’ll simply refer to as a “decomposition” in this post) is any diagram in $\mathbf{Gr}$ that looks like this:

The idea is that you have some shape (a graph; in the example above it’s the tree with vertices w,x,y,z) to which you associate objects of the category $\mathbf{Gr}$; i.e. graphs. Each vertex of the shape is labeled with a graph; for example think of the graph $d(w)$ as the label of the vertex $w$. Each edge of the shape is labeled by a span (a generalized relation) of graphs: for example the edge $e$ is labeled by the span $d(w) \xleftarrow{e_w} d(e) \xrightarrow{e_x} d(x)$ consisting of two graph homomorphisms $e_w: d(e) \to d(w)$ and $e_x: d(e) \to d(x)$.

So where are we heading with these decompositions?

The point of the very informal definition I just gave, which was achieved by sweeping lots of details under the rug, is that you should think of a structured decomposition as a “recipe” for building graphs. If you come along and give me a structured decomposition $(H, d)$ of shape $H$, then I can build a graph out of this recipie: for each edge $e= xy$ of $H$, I glue the bag $d(x)$ to the bag $d(y)$ along the image of $d(e)$. In other words I take a bunch of pushouts. Here’s an example of a graph (left hand side) built as a gluing (colimit) of a tree-shaped structured decomposition (right hand side):

A faster algorithm for Weighted Independent Set

Let’s use the syntax of structured decompositions to write down a faster algorithm for Weighted Independent Set.

First of all note that any tree $T$ can be obtained as a gluing of structured decomposition whose bags are two-vertex complete graphs; here’s an example.

So here’s the algorithm (sketch).

Suppose we are given a tree-shaped decompostion $(U, d)$ of the input tree $T$. Pick any edge $(e = x_1x_2) \in E(U)$. This edge partitions $U$ into two trees $U_1$ and $U_2$ (containing $x_1$ and $x_2$ respectively) and in so doing it also partitions $T$ into two trees: $T_1 = T|_{\bigcup_{u_1 \in U_1} d(u_1)}$ and $T_2 = T|_{\bigcup_{u_2 \in U_2} d(u_2)}$.

• Let $I_1$ be the set of all pairs $(\iota_1, n_1)$ where $\iota_1$ is an independent set in $d(x_1)$ and $n_1$ is the maximum weight of an independent set in $U_1$ whose intersection with $d(x)$ is $\iota_1$. Let $I_2$ be defined similarly, but for $d(x_2)$ and $U_2$.
• Now we can compose $I_1$ and $I_2$ similarly to how we did before:
• for each $(\iota_1, n_1) \in I_1$ and $(\iota_2, n_2) \in I_2$, conclude that there is an independent set of weight $n_1 + n_2 - w(\iota_1 \cap \iota_2)$ in $T$ whenever $\iota_1 +_{d(e)} \iota_2$ is an independent set in the graph $d(x) +_{d(e)} d(y)$.

It’s not too hard to prove correctness, so I won’t do it here, but if you get stuck, have a look at any parameterized complexity book (for example Downey and Fellows Page 191).

The cool part is that this algorithm is much faster than the one I mentioned before. To see this, note that, since each bag of the decompostion always has at most two elements, the sets $I_1$ and $I_2$ have at most two elements (since there are at most two distinct independent sets on a connected graph with at most two vertices). Thus the entire algorithm requires time at most $4\mathcal{O}(|V(U)|) = 4\mathcal{O}(|V(T)|)$.

That’s cool, but where is it heading?

It might seem a bit baroque of me to whip-out structured decompositions to solve such a this simple algorithmic problem on trees. But the point is that the algorithm above generalizes to other graph classes as well; in particular it generalizes to any graph class which has bounded tree-width. I’d love to tell you more about this, but it’ll have to wait for another post.

Until next time, a puzzle..

Earlier I noted that all trees can be built out of tree-shaped structured decompositions whose bags are either $K_1$ or $K_2$. So here’s a quiz:

what graphs can be built out of tree-shaped structured decompositions whose bags are complete graphs?

Dirac found an answer in 1961, but I won’t tell you; I won’t spoil the fun.