[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.