Treewidth? (opens in new tab)

The cops-and-robbers definition of Treewidth is quite intuitive.

You have an undirected graph with a robber moving infinitely fast along the edges of the graph.

You have k cops, each driving their own very slow helicopter that can land on any vertex you want (but it takes some time). The cops can communicate and they know at any time where the robber is.

Given a graph, how many cops do you need to catch the robber, i.e., trap the robber on an edge?

In a tree: 2

On a cycle: 3

In an n × m grid graph: you need min(n, m) + 1.

---

In the game where the cops don't know where the robber is, the "width measure" is called pathwidth.

I've been summarising treewidth as the minimal number of variables you have to carry from one stage to the next(s) to solve with dynamic programming.

You're on your own for fractional hypertreewidth though.

A graph is fundamental notion in computer science because it allows us to model numerous interesting real life problems. Trees are special kind of graphs that are structurally very simple thus many interesting problems are very easy to solve. Some graphs are not trees but are similar to trees and thus on such graphs we can leverage the tree-like similarity and solve interesting problems much more easily and efficiently. Treewidth formally captures the following idea: measure how much a graph is similar to a tree. The notion allows us to formally analyze and quantify complexity of the algorithms that make use of tree-like similarity. There is analogical notion for path-like graphs, called pathwidth. The treewidth is much more interesting in practice but the definition of pathwidth (https://en.wikipedia.org/wiki/Pathwidth) is probably a bit easier to understand so you might look into that first.

The idea in both cases is to decompose a graph into not necessarily disjunctive bags (sets) of neighboring vertices with additional bagging rules which ensure that the decomposition itself is a tree or path, respectively, when interpreting the bags as nodes.

More formally, a tree decomposition t of a graph G is labelling nodes of t by bags of vertices of G such that 1. every edge of G is contained in a bag of t, 2. for every vertex in G, the set of nodes in t whose bags contain v is connected via the child relation.

Here is a nice example: https://upload.wikimedia.org/wikipedia/commons/thumb/9/99/Tr...

For a given graph one can construct many tree decompositions but it is harder get ones with smaller bags but the smaller the bags the more similar to a tree the graph is. We say that a graph has treewidth n if there is a tree decomposition in which each bag has size at most n+1. In particular, a tree has treewidth 1 because we can always construct a tree decomposition with bags of size at most 2.

There are different equivalent characterizations of the notion, one of them is the cops-and-robbers definition, which already appeared in a comment earlier https://news.ycombinator.com/item?id=42695879 and was introduced in https://thomas.math.gatech.edu/PAP/search.pdf. To give an idea why the treewidth can be defined by it observe the following. Playing on a tree you do not need too many cops to capture the robber as you can block the fast robber by putting cops on two neighboring vertices and move toward the robber. So for general graphs you can block the robber by filling two bags of a tree decomposition and move toward the robber.

That's interesting, since both articles are written by the same author (David Eppstein). (Who is maintaining a huge amount of TCS articles on Wikipedia.)