结构化分解：结构与算法组合性|图论|拓扑|新论文|算法|组合性|结构化分解

结构化分解：结构与算法组合性

Structured Decompositions: Structural and Algorithmic

Compositionality.

https://arxiv.org/pdf/2207.06091

摘要：

我们引入了结构化分解，这是一种范畴论结构，它同时推广了来自图论（包括树宽、分层树宽、余树宽、图分解宽度、树独立数、超图树宽和H-树宽）、几何群论（特别是Bass-Serre理论）以及动力系统（例如混合动力系统）中的概念。我们定义了sd-函子，它提供了一种组合性的方式来分析和关联不同的结构复杂性度量，并建立了对象的分解与完备化之间的一般对偶性。

1 引言

组合性（Compositionality）可以被理解为一种视角，即整体的语义、结构或功能应由其组成部分给出 [Sza22]。这一原则长期以来塑造了数学和计算机科学的思维，事实上，像递归和分治算法这样的基本工具本身就依赖于组合推理。

最近，大量的研究工作集中在组合系统的系统数学研究及其在更广泛科学领域中的出现 [Fon16; Pol17; Cic19; Cou20; Mas21]。得益于这些努力，我们现在可以理解如何从较小的组成部分构建图、Petri网 [BM20]、化学反应网络 [BP17]、存量流量图（stock and flow diagrams）[Bae+23] 或流行病学模型 [Lib+22]。理想情况下，我们需要通用的算法，这些算法考虑其输入的范畴和组合结构，并能通用地适用于所有这些实例。这种通用级别的组合算法尚不存在。本文基于丰富且成熟的图计算理论，为其发展提供了一个起点。

参数化复杂性（parameterized complexity）领域提供了一些成熟的技术，用于构建组合算法，这些算法非常适合那些表现出特定组合结构的特定组合对象。相关对象的类通常通过所谓的“宽度度量”（width measures）来识别：这些是源于结构和算法图论的数值量，大致可以被认为是衡量组合复杂度的。其中最著名的是树宽（treewidth），它大致衡量了一个图的全局连通性与树的连通性有多大差异。本文的重点是发展那些源自余极限（colimits）的宽度度量的一般理论。

我们的文章延续了 [Bum21] 和 [BK23] 的工作，即研究树宽的范畴论推广。我们通过引入结构化分解范畴（structured decomposition categories，为了方便，我们也称之为 sd-范畴，参见定义 2.5.1）来实现这一点。这些是配备了给定图表族的范畴 C C，这些图表的所有余极限都存在于 C C 中。

所讨论的图表，我们称之为结构化分解（structured decompositions），总是属于特定类型，大致可以理解为将数据附加到组合对象上的函子化（functorial）方式。因此，本文探讨了哪些组合不变量可以表示为余极限：在结构化分解范畴中，如果一个对象作为结构化分解的余极限出现，则被视为被分解了。我们为 sd-范畴配备了与结构化分解图表良好交互的额外结构，从而得到了宽度范畴（width categories，参见定义 2.5.15）。

稍微具体一点说，结构化分解是某个固定范畴中特殊种类的图表。以下是这些图表样子的一个通用示例。

此外，我们概念的例子也出现在组合设置之外。当实例化在群（groups）的范畴中时，结构化分解与“群图”（graphs of groups）重合，这是一个发展于 20 世纪 70 年代并对 Bass-Serre 理论至关重要的概念 [Ser70; Ser02; Bas93; Hig76]。当处理流形（manifolds）和混合动力系统（hybrid dynamical systems）时，结构化分解在 Ames 的博士论文 [Ame06] 中以“混合对象”（hybrid objects）的名义独立出现。我们在第 3 节（Section 3）中处理这些概念。同样的形式化出现在组合学、几何群论和混合系统中，这一事实支持了对基于余极限构建的结构化分解和宽度度量的一般理论的需求：这正是目前的贡献。

人们不应期望所有的组合分解方法都作为余极限出现。余极限具有强烈的拓扑色彩，并且存在一些组合分解方法，如团宽分解树（clique-width decomposition trees）[CER93; Cou96] 和秩分解（rank decompositions）[OS06]，它们不显示这种拓扑类型的组合性。例如，团宽分解树是通过文法定义的，该文法允许通过在它们之间添加边将两个图连接在一起：尚不清楚这样的操作如何能自然地描述为余极限。第 4 节（Section 4）讨论了捕捉这些方法的研究问题以及其他开放性问题。附录（第 A 节）详细处理了几种不同的图和超图范畴的性质。

1.1 相关工作

图论近期的努力试图通过两种不同的方式来推广树分解（tree decompositions）。第一种考虑更一般的分解“形状”（shapes），例如循环分解和平面分解；Carmesin 关于图分解的工作 [Car22a; Die+22] 是最好的例证。第二种方法是使用树形分解，但允许更复杂的“袋”（bags）；例子包括 H H-树宽（ H H-treewidth）[JKW21] 和分层树宽（layered treewidth）[Sha15; DMW17]。我们的结构化分解（structured decompositions）概念桥接并统一了这两种方法，有望在范畴论和组合学思想的交叉点上开辟令人兴奋的新研究途径。

Blume 等人 [Blu+11] 已经注意到树宽——具体而言——可以通过取推出（pushouts）来编码的想法。那些作者将图 H H 的余跨度分解（cospan decomposition）定义为一连串连通的余跨度（cospans），其余极限是 H H。这个概念在概念上可能比结构化分解更简单（事实上它是我们要念的一个实例化，或者说是特例），但它仅部署在图和树宽的具体案例中。相比之下，正如我们已经提到的，我们的重点是发展一个能一次性封装许多概念的一般理论。此外，像我们这样做将组合分解视为图表（diagrams）的一个好处是，人们可以谈论分解之间的态射以及各种宽度概念之间的函子关系。

更广泛地说，关于图表推理（diagrammatic reasoning）这一主题，值得注意的是，尽管数学家自范畴论诞生之初 [EM45] 就考虑过图表范畴（在定义 2.4.1 的意义上），除了一些例子 [Koc67; Gui73; Gui74; GV77] 外，对其研究的兴趣随时间推移而减弱，但最近又有所回升 [PT20; PT22; Pat+23]。结构化分解作为特定种类的图表，组装成了图表范畴的一个子范畴。这进一步证明了，独立于组合学的考量，对可以通过余极限构建的那类对象进行系统研究的合理性。

最后，我们要指出，结构化分解与无向连线图（undirected wiring diagrams）[Spi13] 有显著的相似性。后者为一种构造提供了操作式（operadic）视角，这种构造与我们所称的 FinSet 值结构化分解非常相似。虽然这超出了本文的范围，但研究这两个概念之间的联系是一个有前景的进一步研究方向。

1.2 符号

2 结构化分解范畴

在本节中，我们首先定义结构化分解（structured decompositions），这是我们在本文中用于研究文献中各种宽度概念的主要范畴论工具。在此之后，我们定义本文的核心概念：sd-范畴（sd-categories）、 Γ Γ-宽（ Γ Γ-width）和 sd-函子（sd-functors）。随后，我们将回顾图论中树宽（treewidth）的经典概念。

2.1 图的范畴

图的概念在文献中各不相同，具体取决于上下文和应用。在下文中，我们考虑 nLab [nLa24] 所指的简单图（simple graphs），即没有环（loops）且同一对顶点之间没有重边（multiple edges）的图。关于不同图范畴的讨论，请参见附录 A。

2.5 宽度范畴

在之前的工作中，前两位作者引入了带脊范畴（spined categories）的形式体系 [BK23]，以便对图论文献中的几种宽度概念（包括树宽、余树宽和超图树宽）给出统一的论述。人们可以将下文的定义视为对这一形式体系的推进，其方法是推广脊范畴（spine category），并要求实际的余极限（colimits）而非代理推出（proxy pushouts）。这使我们能够涵盖文献中更多种类的例子。

注记 2.5.19. 观察到带脊 sd-范畴的定义（定义 2.5.2）强制每个对象具有有限大小。这实际上并非出于数学上的必要性，而纯粹是一种风格上的选择。读者可以验证，通过考虑以序数索引的滤过（ordinal-indexed filtrations）作为脊，并修改宽度的定义（定义 2.5.7）使其简单地等于最大袋（bag）的大小（即去掉减一），人们可以获得一种带脊 sd-范畴的理论，该理论不对分解的袋施加任何有限性条件。这些考量虽然与无限图的树宽相关，但在本文中将不再进一步探讨。

2.6 弦完备化 (Chordal Completions)

现在，让我们以引理 2.8.12 为动机，为宽度范畴引入一种竞争的宽度概念。

尽管这超出了本文的范围，但定理 2.6.7 与结构化分解的算法应用特别相关。为了说明这一点，我们将简要回顾为什么在处理图及其树分解时，弦完备化（chordal completions）是有用的。在算法应用 [FG06; Cyg+15; CE12; Gro17] 中，人们不仅想知道给定的图或结构是否具有有界的树宽（treewidth），而且更感兴趣的是那些给定输入图 G G 后，能够计算出 G G的一个小宽度分解的算法。最著名的此类算法归功于 Bodlaender 和 Kloks [BK96]（简化的阐述见 Althaus 和 Ziegler [AZ21]），该算法建立在 Perković 和 Reed 的早期算法 [PR00] 之上。该算法是一个以树宽为参数的 FPT（固定参数可处理）时间算法，它判定给定的图是否具有至多为 k k 的树宽（如果存在，则输出这样的分解）。然而，由于实现起来相当复杂，在实践中通常更倾向于使用近似或启发式方法。对于这些方法，人们通常依赖于寻找图的弦完备化。这些方法通常建立在 Bouchitté 和 Todinca 的精确算法 [BT01; KBJ19] 之上，通过施加各种顶点排序方案来计算弦完备化 [TY84; RTL76; CM69; Ber+04]。

2.7 sd-函子

我们现在定义 sd-范畴之间的函子。这远非例行公事，确定正确的概念需要相当谨慎：我们使用 sd-范畴中的数据来定义允许的结构化分解，但我们不仅需要函子保留这些数据，还需要它们在适当的意义上将分解映射为分解。

d-函子最常见的应用场景源于以下需求：放松对分解的结构约束（即扩大允许的结构图集合），或者通过增加更多允许的界来细化宽度度量。

2.8 树分解

这项工作的动机来自于图论中树宽（treewidth）的概念。为了定义树宽，我们首先需要树分解的概念。

2.9 优美树分解

路径宽、树宽及相关图参数的主要算法应用是通过在相关的分解上进行动态规划来实现的。尽管树宽的经典刻画使用的是任意树分解，但通过将关注点限制在更特定的分解结构上，算法往往更容易描述。例如，树上的动态规划受益于将算法限制在二叉树上：即由度数至多为 3 的顶点构成的树。我们的形式体系使我们能够证明一个一般性结果，即普通树分解和二叉树分解导出的宽度概念是相同的。

定义 2.9.1. 令