Tree-width is an invaluable tool for computational problems on graphs. But often one would like to compute on other kinds of objects (e.g. decorated graphs or even algebraic structures) where there is no known tree-width analogue. Here we define an abstract analogue of tree-width which provides a uniform definition of various tree-width-like invariants including graph tree-width, hypergraph tree-width, complemented tree-width and even new constructions such as the tree-width of modular quotients. We obtain this generalization by developing a general theory of categories that admit abstract analogues of both tree decompositions and tree-width; we call these pseudo-chordal completions and the triangulation functor respectively.
翻译:树宽是图中计算问题的宝贵工具。 但通常人们想在没有已知树宽模拟物的其他种类的物体(例如,标注的图形,甚至代数结构)上进行计算。 在这里,我们定义了树宽的抽象模拟物,它为各种树宽相似的异种提供了统一的定义,包括图形树宽、高图树宽、补充的树宽甚至新构造,例如模块化商数的树宽。 我们通过开发一种一般的分类理论,接受树分解物和树宽的抽象类似物。 我们分别将这些假圆形补成和三角交点称为。