5
$\begingroup$

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?

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

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the pointer, David, this is exactly the kind of thing I was looking for. $\endgroup$
    – GMB
    Mar 14, 2022 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.