Graph Theory & Treewidth

treewidth and tree decomposition

Treewidth is the single invariant the volume runs on. It measures how far a graph is from being a tree — and a tree is the structure dynamic programming sweeps in linear time. These pages build the graph-theory toolkit the rest of the thesis leans on, from the formal definition of a tree decomposition to the bramble duality that lower-bounds width.

• What is treewidthTreewidth measures how close a graph is to a tree. A clear definition with intuition, examples, and why it governs algorithmic cost.
• Tree decomposition explainedA tree decomposition reshapes a graph into a tree of bags. The formal definition, the three conditions, and a worked example.
• Treewidth vs pathwidthPathwidth is treewidth restricted to a path-shaped decomposition. When they coincide, when they diverge, and why it matters.
• How to compute treewidthComputing treewidth is NP-hard, but heuristics, exact FPT algorithms, and solvers make it tractable in practice. A practical guide.
• Bounded treewidth dynamic programmingWhy hard problems become easy when treewidth is small: the bag-by-bag dynamic programming pattern that runs in linear time.
• Courcelle's theoremEvery property expressible in monadic second-order logic is decidable in linear time on bounded-treewidth graphs. What that really means.
• Brambles and tangles treewidthA bramble certifies that treewidth is large. The duality between brambles and tree decompositions, explained simply.
• Treewidth graphical models inferenceExact inference in a graphical model is exponential in the treewidth of its structure. Why junction trees are tree decompositions.