A Parameterized Algorithm for Testing whether the Limit of a Diagram is Empty

Ernst Althaus, Benjamin Merlin Bumpus, James Fairbanks · 2026

Read A Parameterized Algorithm for Testing whether the Limit of a Diagram is Empty by Ernst Althaus, Benjamin Merlin Bumpus, James Fairbanks (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-24240.txt.

Introduction

Althaus and four co-authors give a parameterized algorithm testing whether a diagram's limit is empty. A limit of a diagram in a complete category reads as equations over its objects, with each object a variable and each morphism a constraint. With an initial object present, the question is whether any solution exists, equivalently whether the limit is initial. The authors build a fast parameterized-complexity algorithm for finite diagrams in finitely complete presheaf categories. It handles structured co-decompositions from the Grothendieck construction of a simple graph.

Catalog record

CREATORErnst Althaus, Benjamin Merlin Bumpus, James Fairbanks
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE58422
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.24240

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Parameterized Algorithm for Testing whether the Limit of a Diagram is Empty Thanks: CUNY CityTech Thanks: NIST Ernst Althaus, Benjamin Merlin Bumpus, James Fairbanks Abstract A limit of a (small) diagram d : 𝒥 → ℰ d:\mathscr{J}\to\mathscr{E} in a complete category ℰ \mathscr{E} can be thought of as specifying a set of equations involving the objects of ℰ \mathscr{E} . To motivate this intuitively, one can think of each object d ⁡ ( j ) d(j) as a “variable” and each morphism in 𝒥 \mathscr{J} as a “constraint” connecting these variables. If ℰ \mathscr{E} has an initial object, a natural question arises: does our set of equations have any solution at all? Equivalently, we can ask: is the limit of d d initial? In this paper we consider the computational problem that, given finite diagram d d in a finitely complete category ℰ \mathscr{E} , asks whether its limit is empty. We construct a fast algorithm (in the sense of parameterized complexity theory) that solves this problem when ℰ \mathscr{E} is of the form 𝐅𝐢𝐧𝐒𝐞𝐭 𝒞 \mathbf{FinSet}^{\mathscr{C}} for a finite category 𝒞 \mathscr{C} and d d is a structured co-decomposition, i.e. a diagram arising from the opposite of the Grothendieck construction of a simple graph. 1 Introduction In this paper we seek a fast (parameterized) algorithm for the following computational problem. \textsc{InLim}(\mathscr{J},\mathscr{E} ) Input: A finite diagram d:\mathscr{J}\to\mathscr{E} in a finitely complete category \mathscr{E} Question: Is the limit of d an initial object, i.e. \lim d\cong\varnothing Such computational problems have recently gained prominence with the rise of applied category theory, particularly in the use of computations involving \mathscr{C} -sets and categorical database theory [ 14 , 13 , 10 , 2 ] and in topological data analysis [ 9 ] . While the field of categorical algorithmics – the use of category theory to obtain fast algorithms – is still in its infancy, it is already apparent that fast algorithms are needed for computations modeled on categories. Many computational problems can be formulated as functors \mathscr{E}^{\text{op}}\to\mathbf{FinSet} , where \mathscr{E} is a category of structures one is interested in. For example, when \mathscr{E} is the category of loop graphs and K^{n} denotes the unlooped complete graph on n vertices, the functor \mathscr{E}(-,K^{n}):\mathscr{E}^{\text{op}}\to\mathbf{FinSet} assigns to every loop graph G its set of n -colorings. If this set is nonempty, then G is n -colorable. Similarly, querying a database can be modeled via mappings of database instances [ 16 ] . Prior work [ 4 ] studies the notion of a structured decomposition, which is a diagram of the form d:\mathop{\raisebox{0.86108pt}{$\smallint\!\!$}}G\to\mathscr{E} , where \mathop{\raisebox{0.86108pt}{$\smallint\!\!$}}G is the Grothendieck construction associated to a finite simple graph G (Definition 3.2 ). Such diagrams arise naturally when looking to decompose a structure like a graph or database into smaller pieces. Hence the pipeline for computational problems we have in mind is as follows: Given some discrete structure X in a category \mathscr{E} , such as a graph or database, along with a computational problem P:\mathscr{E}^{\text{op}}\to\mathbf{FinSet} , we wish to solve P on input X by checking if the set P(X) has any elements. When X is large, computing P(X) by brute force can be prohibitively expensive. Instead, we break X up into pieces using a structured decomposition d:\mathop{\raisebox{0.86108pt}{$\smallint\!\!$}}G\to\mathscr{E} , with X\cong\text{colim}\,d . If P preserves \mathop{\raisebox{0.86108pt}{$\smallint\!\!$}}G -shaped colimits, then composing P with d gives what we call a structured co-decomposition (P\circ d):\mathop{\raisebox{0.86108pt}{$\smallint\!\!$}}G^{\text{op}}\to\mathbf{FinSet} . Then checking if P(X)\cong\varnothing is equivalent to checking if \lim(P\circ d)\cong\varnothing . By reformulating computational problems in this way, we can use the method of “divide and conquer” by checking if (P\circ d)(x)\cong\varnothing for each vertex x\in G , and then combining the results. This results in a significantly faster algorithm than would usually be obtainable. Furthermore, this is an extremely general construction. For example, it applies to any computational problem P which is co-representable. More formally, here we will understand a “fast algorithm” to mean fixed parameter tractable , which in our context roughly means that the running time depends boundedly (potentially exponentially) on an appropriately defined size of the objects in the diagram, but only linearly on the number of objects in the domain of d . As an example, if the objects are sets of size at most k , the running time may be exponential in k but linear in the number of objects. The main result of our paper is the following theorem which guarantees the existence of an FPT-time algorithm for a special case of \textsc{InLim}(\mathscr{J},\mathscr{E}) . Theorem 4.9 . Given a structured co-decomposition d:\mathop{\raisebox{0.86108pt}{$\smallint\!\!$}}G^{\text{op}}\to\mathbf{FinSet} , let S be a feedback vertex set of G of size k , let w=\max_{x\in V(G)}|d(x)| and let n=|V(G)| . Then there is an algorithm that correctly decides \textsc{InLim}(\mathop{\raisebox{0.86108pt}{$\smallint\!\!$}}G^{\text{op}},\mathbf{FinSet}) in time \mathscr{O}(w^{k}\cdot w^{2}\cdot n). To appreciate our main result, consider first how one might naïvely solve \textsc{InLim}(\mathscr{J},\mathscr{E}) . If |\text{Obj}(\mathscr{J})|=n and w=\max_{j\in\mathscr{J}}|d(j)| , then as we work out later in (Paragraph 2.3 ), computing such a limit in the classical way via an equalizer of products is prohibitively expensive when \mathscr{J} has many objects and morphisms, as it runs in time \mathscr{O}(w^{n}|\text{Mor}(\mathscr{J})|). In contrast, when the feedback vertex number of G is small, our algorithm (Theorem 4.9 ) vastly outperforms the naïve approach. The most striking case occurs when G is a tree since, in this case, the above result yields an algorithm that runs in time \mathscr{O}(w^{2}\cdot n) . To appreciate the speedup, suppose |V(G)|=100 and w=5 , then the naïve algorithm runs in roughly 8\cdot 10^{69} steps, while ours requires only 2500 steps. Finally, the proof of Theorem 4.9 immediately extends to the case where \mathscr{E}=\mathbf{FinSet}^{\mathscr{C}} , this is stated as Corollary 4.12 . In subsequent papers, we will apply these results to develop fast dynamic programming algorithms for generalized CSPs (constraint satisfaction problems) and their categorical duals, co-CSPs. Notation Let us set some notation • we let \varnothing,* denote the initial and terminal object in an arbitrary category, • we use boldface \mathbf{C} for named categories and script font \mathscr{C} for unnamed categories. The finite ordinals are denoted \mathbf{1},\mathbf{2},\mathbf{3},\dots , etc. • we assume algorithms only output Yes or No . For incorrect inputs, we assume our algorithms output No rather than say Reject . 2 The Initial Limit Problem 2.1 . As a warm-up, let us begin our investigation of the InLim problem in the simplest case, namely when \mathscr{J} is finite and discrete and \mathscr{E}=\mathbf{FinSet} . This computational problem is denoted \textsc{InLim}(\mathscr{J},\mathbf{FinSet}) . 2.2 Lemma . Given an instance d:\mathscr{J}\to\mathbf{FinSet} of \textsc{InLim}(\mathscr{J},\mathbf{FinSet}) , there is an algorithm such that • if \mathscr{J} is not discrete, outputs No , and • if \mathscr{J} is discrete, outputs a correct solution to InLim in time \mathscr{O}(|\text{Obj}(\mathscr{J})|). Proof. If \mathscr{J} is a discrete category, then \lim d\cong\prodop\displaylimits_{j\in\mathscr{J}}d(j) . For products of sets, it is immediate that the product \prodop\displaylimits_{j\in\mathscr{J}}d(j) is empty if and only if d(j)\cong\varnothing for some j\in\mathscr{J} . Consider the following algorithm 1. In constant time 1 1 1 We assume that \mathscr{J} is stored as a quiver, namely two dictionaries storing functions s,t:E\to V where identity arrows are not stored explicitly. Hence it suffices to check if the set of non-identity morphisms is empty, and this can

Read the complete text