# Is there a standard axiomatization of graph width parameters?

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?

• 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. 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. Feb 28 at 23:28
• 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. Feb 28 at 23:39
• 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
Mar 1 at 6:36
• To add to my comments, there is also the parameter twin-width, to which none of the mentioned intuitions apply. Mar 1 at 7:57
• Thanks @Laakeri -- this discussion is really helpful.
– GMB
Mar 1 at 17:30