[puzzledobserver]

I am a computer scientist working in programming languages (so with no particular expertise in combinatorics).

In my experience, treewidth is one of those ideas at the outer limits of my ability to understand.

I have spent several hours staring at the idea on several different occasions, and at the end of each of these sessions, I come away with a vague sense of why it is important and why the definition is natural, only for its complexity to completely overwhelm me the next time I encounter the concept.

[JohnKemeny]

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.

[gsf_emergency]

This is the JG Kemeny?

Thank you for your service!

https://www.jstor.org/stable/20026529?seq=1

https://math.dartmouth.edu/~doyle/docs/finite/cover/cover.ht...

https://en.wikipedia.org/wiki/Kemeny%E2%80%93Young_method

[quuxplusone]

Presumably not the JG Kemeny who died in 1992 (the Kemeny of Kemeny–Young, Kemeny & Kurtz, etc).

https://en.wikipedia.org/wiki/John_G._Kemeny

TIL that Kurtz died, aged 96, just this past November.

[gsf_emergency]

TIL3!!

>Einstein told him that he should first make his mark on the world, for then people would listen to him

Bad Einstein :(

Ahhh major phew & thnxses for not getting deevoted for that one!!

(Smh how did I miss the en.wiki?? Maybe it's that I'm not a programmer xD)

[davidanekstein]

This sounds a lot like the description of carving width [1], and I was wondering if you could help me understand how the analogy differs between them?

[1] https://link.springer.com/content/pdf/10.1007/BF01215352.pdf

[tnch]

From wikipedia https://en.wikipedia.org/wiki/Carving_width#Related_paramete...: “[…], it can be shown that for any graph, the carving width is greater than or equal to half the branch width, and is less than or equal to the degree times the branchwidth. Because treewidth and branchwidth are always within constant factors of each other, similar bounds can be used to relate carving width to treewidth.”

[davidanekstein]

I acknowledge the formal definition, but am wondering how the analogy for treewidth would be tweaked for carving width.

[pkhuong]

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.

[tnch]

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.