[HN Gopher] Treewidth?
___________________________________________________________________
Treewidth?
Author : RafelMri
Score : 29 points
Date : 2025-01-12 09:10 UTC (2 days ago)
(HTM) web link (www.ams.org)
(TXT) w3m dump (www.ams.org)
| puzzledobserver wrote:
| 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 wrote:
| 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 x 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 wrote:
| 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 wrote:
| 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.
| davidanekstein wrote:
| 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 wrote:
| 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 wrote:
| I acknowledge the formal definition, but am wondering how
| the analogy for treewidth would be tweaked for carving
| width.
| tnch wrote:
| 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.
| tromp wrote:
| I think Wikipedia [1] explains it better than this article.
|
| [1] https://en.wikipedia.org/wiki/Treewidth
| JohnKemeny wrote:
| 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.)
___________________________________________________________________
(page generated 2025-01-14 23:01 UTC)