<p>This isn't quite what you were asking for, but one of the first papers on treewidth found this parameter by axiomatizing a lattice of parameters for graphs, among which treewidth is the top element. This is Halin's &quot;S-functions for graphs&quot; (J. Geom. 1976, <a href="https://doi.org/10.1007/BF01917434" rel="nofollow noreferrer">https://doi.org/10.1007/BF01917434</a>). Halin considers minor-monotone functions that are  zero on edgeless graphs, increase by one when adding a universal vertex, and that take the maximum value among subgraphs separated by a clique separator. These functions include the Hadwiger number (clique minor size) as the bottom element and the treewidth as top element.</p>

CC BY-SA 4.0
2022-03-14T16:57:23.190Z
Thanks for the pointer, David, this is exactly the kind of thing I was looking for.
GMB
CC BY-SA 4.0
2022-03-12T17:31:14.923Z
2022-03-12T17:31:14.923Z
David Eppstein
<p>There are many useful graph properties described as &quot;width parameters&quot; that show up in algorithm analysis (especially for FPT-type algorithms).  The most famous example is probably treewidth, but there is also pathwidth, cliquewidth, etc.</p>
<p>These properties are usually derived from divide-and-conquer algorithms for the problem at hand, and they describe the width of the optimal recursion tree.  My question is whether there is a general description of graph properties that can be considered width parameters, <em>without</em> explicit reference to a divide-and-conquer algorithm in the background.  This question might be answered by a definition along the lines of: a function <span class="math-container">$W$</span> from the set of finite graphs to <span class="math-container">$\mathbb{N}$</span> is a <em>width parameter</em> if it satisfies [some list of axioms].  These axioms might include things like <span class="math-container">$W(\emptyset)=0$</span> or that <span class="math-container">$G' \subseteq G \implies W(G') \le W(G)$</span>, but others are likely needed too.  Treewidth and friends would each correspond a different choice of <span class="math-container">$W$</span> satisfying the axioms.</p>
<p>Is there a published definition along these lines?  Or is it easy to write down such a definition once we have proper intuition about what width parameters represent?</p>

CC BY-SA 4.0
2022-02-28T23:28:14.917Z
I think the answer is no: not published and not easy to write down a general definition, but some (limited) formalisms have been explored e.g. https://arxiv.org/abs/2109.14610. I started to write an answer but found the question somewhat ambiguous. What properties would the notion of "width parameter" capture? To me the intuition is that tree-like width parameters (treewidth cliquewidth mim-width) represent generalization of dynamic programming on trees to graphs. Pathwidth and linear-versions of parameters generalize 1D dynamic programming, and depth-parameters represent branching algorithms.
Laakeri
CC BY-SA 4.0
2022-02-28T23:39:14.080Z
Also, the suggested axiom $G' \subseteq G \Rightarrow W(G') \le W(G)$ is not true for any width parameter that is more general than treewidth (cliquewidth, mim-width), and there is intuition that treewidth should be the most general width parameter that is closed under edge-deletions: graphs can be sparsified to degree-3 while approximately preserving treewidth, and in bounded-degree graphs treewidth should be the most general width parameter that allows tractability results, at least for "typical" problems.
Laakeri
CC BY-SA 4.0
2022-03-01T06:36:25.990Z
I would add that heredity of the width is a requirement that is not suitable to every problem, hence not a particularly good axiom. Some problem may be harder on subgraphs than on the graph itself, in which case, you do not want the width to be smaller on subgraphs. For example, answering conjunctive queries may be easier on the whole query than on subquery. Hence the width used to find tractable instances of this problem (hypertree widht of hypergraph) is not hereditary ($K_n$ has hypertree width $n$ but $K_n$ plus the hyper edge $[n]$ has hypertree width $1$).
holf
CC BY-SA 4.0
2022-03-01T07:57:56.023Z
To add to my comments, there is also the parameter twin-width, to which none of the mentioned intuitions apply.
Laakeri
CC BY-SA 4.0
2022-03-01T17:30:11.210Z
Thanks @Laakeri -- this discussion is really helpful.
GMB
<graph-theory><graph-algorithms><treewidth><cliquewidth>
Is there a standard axiomatization of graph width parameters?
GMB
# Is there a standard axiomatization of graph width parameters?

(Asked by: username_0 on 2022-02-28)

There are many useful graph properties described as "width parameters" that show up in algorithm analysis (especially for FPT-type algorithms). The most famous example is probably treewidth, but there is also pathwidth, cliquewidth, etc.

These properties are usually derived from divide-and-conquer algorithms for the problem at hand, and they describe the width of the optimal recursion tree. My question is whether there is a general description of graph properties that can be considered width parameters, *without* explicit reference to a divide-and-conquer algorithm in the background. This question might be answered by a definition along the lines of: a function $W$ from the set of finite graphs to $\mathbb{N}$ is a *width parameter* if it satisfies [some list of axioms]. These axioms might include things like $W(\emptyset)=0$ or that $G' \subseteq G \implies W(G') \le W(G)$, but others are likely needed too. Treewidth and friends would each correspond a different choice of $W$ satisfying the axioms.

Is there a published definition along these lines? Or is it easy to write down such a definition once we have proper intuition about what width parameters represent?

**Tags:** graph-theory, graph-algorithms, treewidth, cliquewidth
> **Comments:**
> **username_1**: I think the answer is no: not published and not easy to write down a general definition, but some (limited) formalisms have been explored e.g. https://arxiv.org/abs/2109.14610. I started to write an answer but found the question somewhat ambiguous. What properties would the notion of "width parameter" capture? To me the intuition is that tree-like width parameters (treewidth cliquewidth mim-width) represent generalization of dynamic programming on trees to graphs. Pathwidth and linear-versions of parameters generalize 1D dynamic programming, and depth-parameters represent branching algorithms.  
> **username_1**: Also, the suggested axiom $G' \subseteq G \Rightarrow W(G') \le W(G)$ is not true for any width parameter that is more general than treewidth (cliquewidth, mim-width), and there is intuition that treewidth should be the most general width parameter that is closed under edge-deletions: graphs can be sparsified to degree-3 while approximately preserving treewidth, and in bounded-degree graphs treewidth should be the most general width parameter that allows tractability results, at least for "typical" problems.  
> **username_2**: I would add that heredity of the width is a requirement that is not suitable to every problem, hence not a particularly good axiom. Some problem may be harder on subgraphs than on the graph itself, in which case, you do not want the width to be smaller on subgraphs. For example, answering conjunctive queries may be easier on the whole query than on subquery. Hence the width used to find tractable instances of this problem (hypertree widht of hypergraph) is not hereditary ($K_n$ has hypertree width $n$ but $K_n$ plus the hyper edge $[n]$ has hypertree width $1$).  
> **username_1**: To add to my comments, there is also the parameter twin-width, to which none of the mentioned intuitions apply.  
> **username_0**: Thanks @Laakeri -- this discussion is really helpful.  

---

## 1 answers

### Answer by username_3 on 2022-03-12. Score: 4

This isn't quite what you were asking for, but one of the first papers on treewidth found this parameter by axiomatizing a lattice of parameters for graphs, among which treewidth is the top element. This is Halin's "S-functions for graphs" (J. Geom. 1976, <https://doi.org/10.1007/BF01917434>). Halin considers minor-monotone functions that are zero on edgeless graphs, increase by one when adding a universal vertex, and that take the maximum value among subgraphs separated by a clique separator. These functions include the Hadwiger number (clique minor size) as the bottom element and the treewidth as top element.

> **Comments:**
> **username_0**: Thanks for the pointer, David, this is exactly the kind of thing I was looking for.  

---

