結構化分解：結構與算法組合性

結構化分解：結構與算法組合性

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）。這使我們能夠涵蓋文獻中更多種類的例子。

在之前的工作中，前兩位作者引入了帶脊范疇（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. 令表示二叉樹（binary trees）類，即頂點度數至多為 3 的樹。

。。。。。。。。

原文鏈接：https://arxiv.org/pdf/2207.06091