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.

user:	tnch
created:	October 18, 2019
karma:	4