A nice way to think about the “separation lemma” that is used in the treewidth approximation FPT scheme (credit to Tomas for pointint this out):

Claim. Suppose you choose any set of \(R\) red vertices. Then there should be a bag of the tree-decomposition that you can take such that there at most \(R/2\) red vertices in all the connected components left after the removal of that bag.

Proof. Direct the edges in the tree from “bag with fewer red vertices” to “bag with more red vertices” (arbitrarily break ties).

Then find a sink bag. This sink bag is the bag you want.

Remark. Something I was confused about in the tree decomposition algorithm:

Once we pick the set that we are going to separate and then turn into a bag we itterate over all partitions of that set into three parts and run min-cut between each possible tripple of ways the set could get split.

By the lemma above there has to be a good way (or else we have a proof of large treewidth). We take that good partition.

Then let’s call the partition \(S\setminus B, (S\cap (A\cap B)) \cup X, S\setminus A\).

To recurse we then recurse on \(S\setminus B, (S\cap (A\cap B)) \cup X\) and \(S\setminus A, (S\cap (A\cap B)) \cup X\). The idea is, \(B\) interfaces only with \(S\setminus B, (S\cap (A\cap B)) \cup X\), and similar for \(A\). So this is what we want.

bidimensionality

win/win framework.

Powerful theorem: large tree width implies you must have a large grid as a minor.

Theorem. Let \(G\) be a planar graph with treewidth \(t\). Then \(G\) contains an \(\Omega(t)\times \Omega(t)\) grid as a minor!

Sometimes minor is a bit annoying to work with. Relation notion: “graph achievable by edge contractions.”

Theorem. Let \(G\) be a planar graph with treewidth \(t\). Then there is a sequence of edge contractions on \(G\) that results in “\(\Gamma_t\)”, which is a grid, and then you triangulate it, and then you have one corner vertex that is connected to all the boundary vertices.

a very simple example of using treewidth

Example. 3-coloring is FPT when parameterized by treewidth. Run time is \(O(3^{k}\cdot k\cdot n)\).

Proof.

We use the “add edge bag” framework.

Our DP is as follows: For each node \(t\) in the tree decomposition and each 3-coloring \(f: X_t\to [3]\) of the bag at \(t\) let \(D[t, f]\) denote “is there an extension of \(f\) to \(f':G_t\to [3]\) that is a valid 3-coloring of \(G_t\)?”

Now we recurse stuff as follows:

  • leaf bags: let \(f: \varnothing \to [3]\) is the “empty function” (color zero vertices). This is our only option for a coloring. We say \(D[t, f] = \top\). (yes I have started using \(\bot, \top\) for T/F because latex has pretty good support for them and because \(\bot\) kinda looks like \(\perp\), which is my favorite binary relation).
  • add vertex bags: at this point the vertex is isolated, so its fine as long as the restriction of \(f\) to not color this vertex is fine
  • add edge bags: as long as you don’t add an edge between two vertices with the same color you’re chilling
  • forget vertex bags: try all the colors for the vertex that you’re forgetting. if any of them work then you’re good.
  • join bags: take the intersection of the colorings for both childs.