Talk:Treewidth

I changed (2024-07-31) the introduction

A tree decomposition of a graph G = (V, E) is a pair (X, T), where X = {X₁, ..., X_n} is a family of subsets of V, and T is a tree whose nodes are the subsets X_i, satisfying the following properties:

1. The union of all sets X_i equals V. That is, each graph vertex is associated with at least one tree node.
2. For every edge (v, w) in the graph, there is a subset X_i that contains both v and w. That is, vertices are adjacent in the graph only when the corresponding subtrees have a node in common.
3. If X_i and X_j both contain a vertex v, then all nodes X_k of the tree in the (unique) path between X_i and X_j contain v as well.

to this one

A tree decomposition of a graph G = (V, E) is a pair (X, T), where X = (X_i)_i∈T is a family of subsets of V indexed by a tree T satisfying the following properties:

1. The union of all sets X_i equals V.
2. For every edge (v, w) in the graph, there is a subset X_i that contains both v and w.
3. If X_i and X_j both contain a vertex v, then v is also in X_k for all k in the (unique) path between i and j in T. (Equivalently, for any v in V, the i such that v is in X_i is a connected subset of T.)

You (David Eppstein) reverted it, giving this reason: I don't think making this more notation-heavy and removing the English-language intuition is a helpful form of "clarification"

The reasons I made the change were:

• I found the original slightly hard to parse, and containing phrases that could be taken in more than one way. It works if you already know what a tree decomposition is, but otherwise there are unnecessary stumbling blocks. I believe the changed version is "tighter".
• The original sometimes uses the term "node" and sometimes "vertex", which I think isn't especially helpful. The reader may wonder whether the author is making a distinction or whether it is a kind of elegant variation. I realise that "node" is consistently being used for vertices of the tree, but this isn't obvious unless you know how to parse the whole definition at which point you are happy anyway. If you want to do this, then I suggest saying upfront that "node" is to be used for vertices of T.
• It's not obvious a-priori on which level the phrase "T is a tree whose nodes are the subsets X_i" operates. It could mean that each X_i is a single vertex of T, or it could (just about) mean that the vertices of T are the elements of X_i. If it's meant to appeal to the mathematically unsophisticated (as your remark about English-language intuition suggests) then I think that using a set as a vertex with no explanation is potentially confusing, and not really necessary. If it's meant to appeal to the more sophisticated, then it's also confusing because you immediately wonder "why did he use a pair (X,T) when he could have just said a tree decomposition of G is a tree, T, whose vertices are subsets of V...?. Is there meant to be some extra structure? Why use the index i in X_i at all?"
• I don't believe the English-language intuition in the original "That is, each graph vertex is associated with at least one tree node." is worth that much. It's unlikely that anyone who didn't know what a union was would seek to understand treewidth, and sometimes less clutter is better. And the word "associated" is not precise, which in a way makes things less clear rather than more clear.
• Similarly, I don't believe the English-language intuition in the original "That is, vertices are adjacent in the graph only when the corresponding subtrees have a node in common." adds much either. It presumes that the reader will guess that the phrase "the corresponding subtrees" refers to the subtrees of T consisting of X_i that contain v (or w). This may seem obvious, but I think that's from the point of view of already understanding what everything means. Who is the reader who understands "corresponding subtrees", but finds the simple phrase "For every edge (v, w) in the graph, there is a subset X_i that contains both v and w." troublesome?
• I'm not sure I understand what you mean by "notation-heavy": as far as I can see, the version I submitted relies on less hidden understanding. If you are referring to the set membership symbol, ∈, then it could be rephrased without it if you think this is an improvement.

These are all small points, by the way.—Alex Selby (talk) 19:02, 16 July 2013 (UTC)

I agree with making "node" vs "vertex" consistent. I believe that the correct way of doing this is to make sure that "node" is used only to refer to the elements of the decomposition tree, and "vertex" is used only to refer to the elements of the graph. That was my intent in writing it that way, as a way of distinguishing these two very different kinds of elements, but it is entirely possible that that distinction slipped and should be corrected, or that more explanation of this distinction would be helpful. I strongly disagree with replacing sequence notation of the form $x_{1},x_{2},\dots x_{n}$ with $(x_{i})_{[n]}$: that notation is too specialized and WP:TECHNICAL. I also strongly disagree with the removal of prose explanations such as "That is, each graph vertex is associated with at least one tree node." and "That is, vertices are adjacent in the graph only when the corresponding subtrees have a node in common." — again, see WP:TECHNICAL: we should be making our articles as accessible to non-expert readers as possible, and replacing prose by pure notation is the opposite of that. As for the phrase "a tree whose nodes are the subsets": it means exactly what it says, that there is a collection of subsets, forming the nodes of a tree. You don't believe that the nodes of a tree have to be numbers, or dimensionless points, do you? I suppose we could have said that the nodes correspond one-for-one with the subsets but I think that only makes it more confusing. I don't like your phrasing "a family of subsets of V indexed by a tree T": what does it mean to be indexed by a tree? As for why use a pair (X,T): because the family of subsets is not by itself the correct information (it doesn't describe how to connect the subsets into a tree) and because the tree as an abstract object (ignoring what its vertices are) is also not the correct information. I don't have any strong feelings about your rephrasing of the third numbered item in the definition, except that I don't see what the parentheses are for. —David Eppstein (talk) 19:15, 16 July 2013 (UTC)

You agreeing with making "node" vs "vertex" consistent is agreeing to something I didn't say, though of course consistency is desirable. I said that I believe it is confusing simply to use the two different terms, even consistently, without an explanation upfront.

You may be right about (X_i)_i∈T notation, but I still think it is more confusing to the non-expert to name the nodes of T as X_i, rather than (say) i, without an explanatory remark. Of course nodes of a tree CAN be anything, but I'm thinking from the point of view of what would make it most clear.

I agree that articles should be as accessible as possible to the non-expert (which I'd class here as someone with a passing acquaintance with mathematics). We merely have a difference of opinion as to which versions are clearer. For example, you think the prose sentences at the end of 1. and 2. improve accessibility and I don't.

Your comments about the pair (X,T) seem to be arguing against something I didn't say.

But I obviously don't feel as strongly as you about this, so I'll leave the article as it is. — Alex Selby (talk) 20:30, 16 July 2013 (UTC)

I am not naming the nodes as X_i. I am naming the sets of vertices of G X_i, and then using those sets as nodes. Naming the nodes by i instead of X_i means that the definition needs to consist of three things: a family of sets, a tree, and a correspondence between the sets and the tree nodes. (The correspondence may be implicit in the numbering of the sets as i but then there are still three things: the family of sets, a sequence by which those sets are numbered, and the tree). Using the sets themselves as nodes allows the definition to use only two objects, the family of sets and the tree. —David Eppstein (talk) 21:14, 16 July 2013 (UTC)

PS I added an explanatory sentence about the vertex-node distinction, and made some other edits. Please do say something (or try editing again) if you think it is still unclear, confusing, or incorrect. —David Eppstein (talk) 23:09, 16 July 2013 (UTC)

Thank you for your latest changes, but (sorry) I think your original version was better. E.g., the new version has now lost the enumeration {X₁, ..., X_n} which makes it visually clear that X_i is part of a collection and I think there is some doubt as to whether the correspondence is a map from V(T) to {X₁, ..., X_n} or a collection of maps (as i varies) from V(T) to X_i, and the correspondence itself is a bit cumbersome.

I think I may be able to go back to your original version and adjust it to answer my reservations, while still retaining your basic setup and notation. Would you mind if I tried that?—Alex Selby (talk) 23:38, 16 July 2013 (UTC)

Rather than do that, I'll insert it here for discussion.

 

A tree decomposition of a graph G = (V, E) is a tree, T, with nodes X₁, ..., X_n, where each X_i is a subset of V, satisfying the following properties (note that the term node is used to refer to a vertex of T to avoid confusion with vertices of G):

1. The union of all sets X_i equals V. That is, each graph vertex is contained in at least one tree node.
2. If X_i and X_j both contain a vertex v, then all nodes X_k of the tree in the (unique) path between X_i and X_j contain v as well. Equivalently, the tree nodes containing vertex v form a connected subtree of T.
3. For every edge (v, w) in the graph, there is a subset X_i that contains both v and w. That is, vertices are adjacent in the graph only when the corresponding subtrees have a node in common.

 

I'm slightly wondering whether it's worth adding one more sentence upfront defining the subtree corresponding to a vertex v. The explanatory remarks to all three of the conditions refer to this subtree in some way, and it would make it possible to go back to the original ordering of conditions (which had the aesthetically pleasing feature of going from least complicated to most complicated).—Alex Selby (talk) 00:11, 17 July 2013 (UTC)

I would remove "note that" per WP:NOTED, but other than that minor change this version looks ok to me. I agree that the ordering by complexity made more sense, and your idea of saying something earlier about the subtree would be a way to fix this; one way of doing this would be to move and rephrase the sentence about nodes forming a connected subtree in item 2, since that would become redundant. —David Eppstein (talk) 01:54, 17 July 2013 (UTC)

I've changed the definition in the article to the above version (without the "note that") since this appears to be some kind of consensus. It can probably be improved (possibly with a remark about subtree corresponding to v), but changing it might introduce other problems and it is now an improvement on what went before, in my opinion.—Alex Selby (talk) 00:33, 18 July 2013 (UTC)

I have inserted (2024-07-31) a reference where I observed that treewidth and partial k-trees are the same concept. — Preceding unsigned comment added by 2A02:8071:8284:50A0:0:0:0:1530 (talk) 05:44, 31 July 2024 (UTC)

That reference is dated 1990 but the same observation is in the abstract of Bodlaender, "Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees", SWAT 1988, and earlier in Bodlaender's technical report "Classes of graphs with bounded tree-width", 1986. So I think we should cite Bodlaender for this, not your diploma thesis. Also the corresponding equivalence between pathwidth and vertex separation number appears to first be stated in Nancy Kinnersley's 1989 dissertation. —David Eppstein (talk) 07:19, 31 July 2024 (UTC)

Ok, Hans noted it earlier. I also introduced tree separation as generalisation of vertex separation. On the other side my dissertation finished 1990 and i know only Nancys papaer from 1992. 2A02:8071:8284:50A0:0:0:0:1530 (talk) 06:39, 1 August 2024 (UTC)

If you have ProQuest access her dissertation is https://search.proquest.com/docview/303738168 —David Eppstein (talk) 07:26, 1 August 2024 (UTC)