Earlier quoted context omitted.
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…
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
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.”