Going Beyond Twin-Width? CSPs with Unbounded Domain and Few Variables

Jonsson, Peter; Lagerkvist, Victor; de Vlas, Jorke M.; Wahlström, Magnus

doi:10.4230/LIPIcs.ICALP.2026.120

Going Beyond Twin-Width? CSPs with Unbounded Domain and Few Variables

Peter Jonsson

Linköping University, Sweden Victor Lagerkvist

Linköping University, Sweden Jorke M. de Vlas

Linköping University, Sweden Magnus Wahlström

Royal Holloway, University of London, Egham, UK

Abstract

We study connections between parameterized complexity, universal algebra, and structural graph parameters. Our starting point is the constraint satisfaction problem over instances with few variables but unbounded domain size (udCSP). Surprisingly, many upper and lower bounds in parameterized complexity can be expressed as solving such udCSPs. Prominent examples include the FPT algorithms for Boolean MinCSP [45], Directed Multicut with three cut requests [40], and the canonical W[1]-hardness construction Paired Min Cut [51]. We represent constraints over unbounded domains by a set of unary maps $\mathcal{M}$ into a finite base language $\Gamma$ , situating $\textsc{udCSP}(\Gamma,\mathcal{M})$ in the algebraic terra incognita between finite and infinite domains. We present a novel algebraic theory that explains the parameterized complexity of problems such as Paired Min Cut, $\ell$ -Chain Sat, and Coupled Min Cut, and unifies disparate FPT algorithms through the lens of twin-width. In particular, we simplify key steps in existing algorithms, e.g., for Boolean MinCSP, via a clean reduction to udCSP. We specifically concentrate on $\textsc{udCSP}(\Gamma,\mathcal{M})$ restricted to monotone maps $\mathrm{Mo}$ , where we identify the crucial connector polymorphism: its presence implies FPT for binary relations (via dynamic programming based on twin-width), while its absence entails W[1]-hardness. Extending this to higher-arity relations is related to the notoriously difficult task of finding a generalisation of twin-width to non-binary structures. As a step in this direction, inspired by our algebraic framework, we introduce a new structural parameter, projected grid-rank, and show that it coincides with the connector property, and agrees with twin-width for binary structures. More strongly, we show that for structures of bounded arity and bounded projected grid-rank, all binary projections have bounded twin-width. This width measure may thus be of independent interest for any problem currently hinging on generalizations of twin-width.

Keywords and phrases:

Constraint satisfaction problems, parameterized complexity, twin-width, universal algebra

Category:

Track A: Algorithms, Complexity and Games

Funding:

Peter Jonsson: Partially supported by the Swedish Research Council (VR) under grant 2021-04371.

Victor Lagerkvist: Partially supported by the Swedish Research Council (VR) under grant 2025-04487.

Jorke M. de Vlas: Partially supported by the Swedish Research Council (VR) under grant 2021-04371.

Copyright and License:

2012 ACM Subject Classification:

Mathematics of computing

\rightarrow

Discrete mathematics ; Theory of computation

\rightarrow

Complexity theory and logic ; Theory of computation

\rightarrow

Constraint and logic programming

Related Version:

Full Version: https://arxiv.org/abs/2508.16389

Acknowledgements:

We thank the anonymous reviewers for several helpful comments.

DOI:

10.4230/LIPIcs.ICALP.2026.120

Event:

53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 High-level Background

We study connections between parameterized complexity, universal algebra, and structural width parameters, with the aim of, for instance, simplifying FPT algorithms and understanding width notions suitable for non-binary structures. There are two main sources of inspiration for our work.

(1) Constraint satisfaction problems (CSP).

This is the problem of deciding whether a set of constraints over a set of variables $V$ with domain $D$ admits a solution. Typically, the constraints are constructed from a finite set of relations $\Gamma$ , known as a constraint language. Complexity-theoretic aspects of CSPs have attracted a great deal of attention: the CSP framework is sufficiently general to encompass many important computational phenomena while still having enough structure that can be exploited to gain deep insights into said phenomena. In particular, the algebraic approach has been very successful [4, 14]. It is rooted in universal algebra and the main tool is functions $f:D^{m}\rightarrow D$ that preserve relations with domain $D$ . These functions can be viewed as high-dimensional symmetries of solution sets: roughly speaking, absence of symmetries implies computational hardness while presence of symmetries implies tractability.

(2) The twin-width parameter.

The graph parameter twin-width was defined by Bonnet, Kim, Thomassé, and Watrigant [13] as a generalization of an invariant for classes of permutations by Guillemot and Marx [36]. Twin-width has been studied intensively in the context of many structural and algorithmic questions, such as FPT model checking [13], graph enumeration [10], graph coloring [11], and structural properties of matrices and ordered graphs [12]. This parameter is not restricted to graphs and it has been generalized to arbitrary binary structures with finite domains. Extending twin-width to structures of arbitrary arity encounters severe difficulties since twin-width is, on a very basic level, intrinsically a property of binary structures. Identifying a useful width notion for non-binary structures that generalizes twin-width, beyond transductions of binary structures, is considered extremely challenging, or possibly even impossible.

The common denominator for parameterized complexity, CSPs, algebra, and twin-width turns out to be a variation of the CSP where the variable domain is of unbounded size and is part of the instance, and the parameter is the number of variables. This allows us to study various problems from a brand new perspective. In particular, it gives us the ability to unify both upper and lower bound results in parameterized complexity within the twin-width framework. From the other side, we can identify candidates for twin-width generalizations that work for non-binary structures and understand the algorithmic complications of proving corresponding FPT results. Algebraically, it differs from previous work in that we need to preserve the number of variables, which is completely orthogonal to the types of gadget reductions usually considered in universal algebra. Traditionally, two types of restrictions are considered when working with CSPs: structural restrictions (e.g., based on width parameters) and constraint language restrictions. These two restrictions are individually well understood, e.g., the CSP dichotomy theorem [17, 58] gives a precise boundary between tractability and NP-hardness. However, there are few general results on combining structural parameters and constraint language restrictions, and the traditional algebraic approach seems ill equipped to study such questions.

The rest of this paper is structured as follows. We explain the connections between CSPs and parameterized complexity in greater detail in Section 2. In Section 3 we formally introduce the udCSP problem, and we continue by summarizing the main results of the paper in Section 4. The results underlying our algebraic approach can be found in Section 4.1 and the results concerning complexity and generalizations of twin-width in Section 4.2. Some applications and related research is discussed in Section 5. Finally, we summarize the paper and point out some future research directions in Section 6.

The full version of the paper can be accessed at https://arxiv.org/abs/2508.16389.

2 CSPs and Parameterized Complexity

In classical complexity investigations into CSPs, the most typical setting is to consider a restricted variant of the CSP problem where a finite set of relations (a constraint language) is used to determine the allowed constraints (CSP $(\Gamma)$ ). There is a rich toolbox for analysing the complexity of such problems: on the relational side there are many closure operators on relations which imitate different forms of gadget reductions: primitive positive definability (pp-definability) gives simple gadget reductions based on replacing constraints by something equivalent, and on a higher level one obtains primitive positive constructions (pp-constructions). In terms of gadget metaphors, this corresponds to NP-hardness reductions “between problem domains”, e.g., a problem over some domain $D$ can be reduced into a problem over a domain $D^{\prime}$ by mapping variables over $D$ to tuples of variables over $D^{\prime}$ . For example, the classical reduction from $k$ -coloring to $3$ -SAT can be formulated as a pp-construction of the $k$ -clique from the Boolean language where each relation is the set of models of a 3-clause. These notions can also be witnessed by algebraic counterparts and the resulting theory often goes under the name the algebraic approach [3]. The basic object corresponding to pp-definability is then that of a polymorphism which describes permissible ways to combine solutions, and to obtain an analogoue of pp-constructions one considers polymorphisms definable by restricted forms of identities (strong Maltsev conditions). Via this approach the classical complexity of CSP $(\Gamma)$ has been fully classified: it is tractable if and only if $\Gamma$ does not have a polymorphism satisfying a non-trivial height 1 identity [17, 58].

In a direction that is quite orthogonal to the classical investigations, in parameterized complexity one encounters problems that are definable as CSPs where the number of variables is a parameter, say $k$ , and the domain is some input-defined size $n$ ; refer to these as $k$ -variable, unbounded-domain CSPs (udCSP). Certainly, parameterizing by the number of variables has been considered earlier in the literature. For a classical example, integer programming is known to be FPT with respect to the number of variables [47], a fact which has seen some FPT applications (see, e.g., [34]). In a less formal way (i.e., not directly corresponding to a CSP), one can also view the classical method of colour coding [1] as reducing a problem of finding a $k$ -vertex subgraph $H$ in a given graph $G$ to a problem of assigning target “values” (vertices in $G$ ) to $k$ “variables” (vertices from $H$ ) in a way such that the edge adjacencies are preserved. This applies to the hardness side as well, where the classical W[1]-hard problem Multicoloured $k$ -Clique is frequently treated as a $k$ -variable 2-CSP with input-defined domain size $n$ . Machine learning in fixed dimension – here, dimension refers to the number of input neurons – is also directly related to finite-variable problems and its computational and parameterized complexity is an active area of research [21, 29, 30, 43]. Yet another example comes from [15] who study the parameterized complexity of Steiner Multicut and introduce the problem NAE-Integer-3-SAT as a handy source of hardness (it has subsequently been used in several works: for instance, in studies of the Metric Dimension [32] problem, machine learning, [33] and game theory [52]). Their W[1]-hardness proof is a reduction from Multicoloured $k$ -Clique and, not surprisingly, NAE-Integer-3-SAT can be viewed as an instance of the udCSP problem (see Example 6).

However, more recently, this phenomenon has started occurring in a more systematic manner, especially in graph separation problems and the study of MinCSPs. This is primarily due to the breakthrough tool of flow augmentation [44], through which graph separation problems can be reduced to instances where the solution is an $s t$ -min cut in an augmented graph. Via Menger’s theorem, the set of $s t$ -min cuts in a graph can in turn be encoded as the set of solutions to a $k$ -variable CSP: Given an $s t$ -max flow $\mathcal{P}=\{P_{1},\ldots,P_{k}\}$ in a graph $G$ , there is a CSP with a variable $x_{i}$ for each path $P_{i}\in\mathcal{P}$ , where the value of $x_{i}$ encodes where $P_{i}$ will be cut, and binary constraints between the variables can enforce that a satisfying assignment corresponds to an $s t$ -min cut in $G$ (see Section 5). Effectively, this reduces the search space from $\{0,1\}^{n}$ (all $s t$ -cuts) to $[n]^{k}$ (solutions to the CSP). This perspective turns out to be very fruitful. For example, the long-standing open problem $\ell$ -Chain SAT [23] was solved in [44] directly by this method, and for a more complex application, the FPT algorithm for Directed Multicut with three cut requests [40] was solved by a combination of methods, including flow augmentation to reduce to a $k$ -variable CSP, and the use of twin-width together with structural arguments to show that the resulting CSP can be solved in FPT time.

An even more direct connection is for MinCSP. For a constraint language $\Gamma$ , the problem MinCSP $(\Gamma)$ asks, given a CSP with constraints from $\Gamma$ and an integer $k$ , whether there is an assignment that satisfies all but at most $k$ constraint in the instance. By varying the constraint language $\Gamma$ , one gets a rich variety of constraint optimization problems, where we in particular are interested in knowing for which languages $\Gamma$ the problem MinCSP $(\Gamma)$ is FPT parameterized by $k$ . For Boolean languages, [45] provides a dichotomy of MinCSP $(\Gamma)$ as being FPT or W[1]-hard, and here, both the upper and lower bounds go via $k$ -variable udCSPs. For the upper bound, the most interesting case is for bijunctive languages $\Gamma$ , where every relation in $\Gamma$ is defined by a 2-CNF formula. The FPT algorithm for tractable languages of this type has three steps: (1) a standard reduction to a graph cut problem; (2) heavy use of flow-augmentation to reduce to an instance where the solution is an $s t$ -min cut with side constraints; and (3) a complex branching algorithm to solve such a min-cut instance. Step (3) can be seen as a udCSP; in fact, we argue that the results of this paper lead to a simplified, less ad-hoc solution to this step. The lower bounds are primarily reductions from Paired Min Cut [51]¹¹1Marx and Razgon formulate this problem in logical terms. A more common graph-theoretic formulation can be found in [45, Lemma 5.7]., which is precisely a simple, W[1]-hard udCSP problem. Similar outlines can be given for many other parameterized MinCSPs – frequently, what decides tractability is whether a problem can encode a W[1]-hard $k$ -variable udCSP such as Paired Min Cut [25, 26, 54, 55].

In this paper we wish to make this perspective explicit and precise, and we seek to develop the machinery to analyse the parameterized complexity of problems with few variables but with unbounded domain size. To be able to study this problem in a systematic way we follow the classic approach and first fix a finite constraint language $\Gamma$ (over some fixed finite domain). Such restrictions are necessary since the problem is otherwise trivially W[1]-hard. However, since the domain is variable and part of the input, constraints cannot merely be given as constraints over $\Gamma$ , and to circumvent this we consider constraints of the form $R(m_{1}(x_{1}),\ldots,m_{r}(x_{r}))$ where $x_{1},\ldots,x_{r}$ are variables (at most $k$ many) and $m_{1},\ldots,m_{r}$ are maps from the input domain $\{0,1,\ldots,n-1\}$ to the domain of $R$ . Thus, even if the base language $\Gamma$ is fixed we can still make use of unbounded domains by using maps to the base domain. We let $\textsc{udCSP}(\Gamma)$ denote this generalization of CSP and are then primarily interested in analyzing the parameterized complexity when the the number of variables is used as parameter.

The driving force behind our approach is now what we can learn about $k$ -variable problems when studied in the unifying and very general $\textsc{udCSP}(\Gamma)$ framework. Thus, is it possible to obtain interesting FPT/W[1] dichotomies or is the number of variables as a parameter inherently too frail? As we will see, this question can be greatly simplified by universal algebra, and by studying restricted problems in this setting we unravel new connections between CSPs, algebra, and various structural parameters.

3 Problem Statement

In this section we formally introduce the unbounded domain CSP problem. Our setup is different from conventional CSPs as we do not have one global domain $D$ that is shared by all relations and instances. Instead, each instance has an input-defined domain, and we use unary maps to translate from this domain to the domains of the relations. Furthermore, in order to properly facilitate the creation of new relations with arbitrary domain sizes, we do not want to be restricted by a global domain shared by all relations. This motivates the following definitions, where we redefine the notions of relation, constraint language, and formula to allow different domains for each instance and relation, together with the generalization that an atom now may contain literals of the form $f(x)$ where $f$ is a map and $x$ a variable.

We begin with some terminology for more arbitrary domains and the unary maps between these domains. For $d\geq 1$ we let $\mathtt{D}_{d}=\{0,1,\ldots,d-1\}$ .

Definition 1.

We make the following definitions.

$\blacksquare$

A domain set $\mathcal{D}$ is a set of finite domains. The domain set $\mathtt{D}_{\mathbb{N}}$ is the set of all numerical domains $\mathtt{D}_{d}$ for $d\in\mathbb{N}$ .
$\blacksquare$

Let $\mathcal{D}$ and $\mathcal{E}$ be domain sets. A map family $\mathcal{M}$ from $\mathcal{D}$ to $\mathcal{E}$ , often written as $\mathcal{M}:\mathcal{D}\to\mathcal{E}$ , is a collection of sets of maps which, for each pair $(D,E)\in\mathcal{D}\times\mathcal{E}$ , contains exactly one set of maps $\mathcal{M}^{D}_{E}\subseteq E^{D}$ . We define standard set operations on map families by applying them set-wise.
$\blacksquare$

Let $\mathcal{D}$ , $\mathcal{E}$ and $\mathcal{F}$ be domain sets and $\mathcal{M}:\mathcal{D}\to\mathcal{E}$ , $\mathcal{N}:\mathcal{E}\to\mathcal{F}$ map families. We define the composition $\mathcal{N}\circ\mathcal{M}$ as the map family from $\mathcal{D}$ to $\mathcal{F}$ with $(\mathcal{N}\circ\mathcal{M})^{D}_{F}=\bigcup_{E\in\mathcal{E}}\{n\circ m\mid n% \in\mathcal{N}^{E}_{F},m\in\mathcal{M}^{D}_{E}\}$ , where $(n\circ m)(x)=n(m(x))$ .
$\blacksquare$

Let $\mathcal{D}$ be a domain set and $\mathcal{M}:\mathcal{D}\to\mathcal{D}$ a map family. We say that $\mathcal{M}$ is composition closed if $\mathcal{M}\circ\mathcal{M}\subseteq\mathcal{M}$ .

We now define functionally guarded versions of relations, constraints, and formulas.

Definition 2.

We redefine the following notions from conventional CSPs. Throughout, the letters $D$ and $\mathcal{D}$ represent “big” instance domains while $E$ and $\mathcal{E}$ represent “small” relational domains.

$\blacksquare$

A relation of arity $r$ is a tuple $(E,R,r)$ consisting of a finite domain $E$ and a set $R\subseteq E^{r}$ . Contrary to the conventional definition, the domain is explicitly specified for each relation since constraints on the relation need to be aware of the domain in question. We interchangeably use set notation $(x_{1},\ldots,x_{r})\in R$ and predicate notation $R(x_{1},\ldots,x_{r})$ .
$\blacksquare$

A constraint language is a tuple $(\mathcal{E},\Gamma)$ consisting of a domain set $\mathcal{E}$ and a finite set of relations $\Gamma$ with each relation $(E,R,r)$ satisfying $E\in\mathcal{E}$ . Contrary to the conventional definition, $\Gamma$ has a set of possible domains instead of a single fixed domain and is assumed to be finite by default.
$\blacksquare$

A functionally guarded constraint language (fg-constraint language) is a tuple $(\mathcal{D},\mathcal{E},\Gamma,\mathcal{M})$ consisting of two domain sets $\mathcal{D}$ and $\mathcal{E}$ , a constraint language $\Gamma$ over $\mathcal{E}$ and a map family $\mathcal{M}$ from $\mathcal{D}$ to $\mathcal{E}$ .
$\blacksquare$

A formula in some fg-constraint language $(\mathcal{D},\mathcal{E},\Gamma,\mathcal{M})$ is a tuple $(D,\phi)$ consisting of a finite domain $D\in\mathcal{D}$ and a logic formula $\phi(x_{1},\ldots,x_{m})$ where each variable has domain $D$ and where each atom is of the form $R(f_{1}(y_{1}),\ldots,f_{r}(y_{r}))$ with $(E,R,r)\in\Gamma$ a relation and $f_{1},\ldots,f_{r}\in\mathcal{M}^{D}_{E}$ maps. Contrary to the conventional definition, we add maps to translate from the domain of the formula to the domain of the relations. We refer to these maps as guarding functions.

When the (sets of) domains are clear from context, we often omit them. That is, we make no clear distinction between a relation $(E,R,r)$ and $R$ , a constraint language $(\mathcal{E},\Gamma)$ and $\Gamma$ , an fg-constraint language $(\mathcal{D},\mathcal{E},\Gamma,\mathcal{M})$ and $(\Gamma,\mathcal{M})$ , or a formula $(D,\phi)$ and $\phi$ .

We are now able to state our problem definition. Let $(\mathcal{D},\mathcal{E},\Gamma,\mathcal{M})$ be an fg-constraint language.

$\textsc{udCSP}(\mathcal{D},\mathcal{E},\Gamma,\mathcal{M})$

Instance: A tuple $(D,V,C)$ where

$\blacksquare$

$D\in\mathcal{D}$ is a domain, whose size is given in unary.
$\blacksquare$

$V$ is a set of variables on the domain $D$ .
$\blacksquare$

$C$ is a set of functionally guarded constraints, each consisting of a relation $(E,R,r)\in\Gamma$ with arity $r$ , a tuple of variables $v_{1},\ldots,v_{r}\in V$ and a tuple of maps $m_{1},\ldots,m_{r}\in\mathcal{M}^{D}_{E}$ .

Question: Does there exist a function $f:V\to D$ mapping each variable to an element from its domain such that for each constraint $(R,(v_{1},\ldots,v_{r}),(m_{1},\ldots,m_{r}))\in C$ we have that $(m_{1}(f(v_{1})),\ldots,m_{r}(f(v_{r})))\in R$ .

The choice of unary representation for the domain size is made primarily to avoid complications with algorithm efficiency, since these issues are not the focus of the paper. However, for arbitrary unary maps we anyway need $\Theta(n)$ space to define each map. On the other hand, for Monotone-CSP, an instance with $m$ constraints will have only $O(m)$ equivalence classes of domain elements, where two domain elements are equivalent if they are indistinguishable in every unary map. Hence the unary representation is not a significant restriction.

We typically parameterize the problem with respect to the parameter $|V|$ . Note that this parameterization is not very useful for CSP $(\Gamma)$ : when $\Gamma$ has a finite domain $D$ , then every instance can be solved in time $|V|^{|D|}\cdot poly(||I||)$ and CSP $(\Gamma)$ is always in FPT. Certainly, this is not true for the $\textsc{udCSP}(\Gamma,\mathcal{M})$ problem.

We note that the arc consistency procedure works in the udCSP setting and it still runs in polynomial time. Let $\Gamma$ be a finite constraint language with relations of maximum arity $r$ . Let $(n,V,C)$ be an instance of $\textsc{udCSP}(\Gamma)$ where $|C|=m$ and $V=\{x_{1},\dots,x_{k}\}$ . Since the sum of all domain sizes is initially $n k$ and every iteration reduces this sum by one, we need at most $n k$ iterations. Each iteration checks $m\cdot k\cdot n$ tuples of relation/variable/value and each check takes $O(n^{r})$ time. The runtime of this step is polynomial since $r$ is a fixed constant. The whole process takes polynomial time since $n$ is given in unary.

In most applications, the map families are completely determined by the domains. That is, we assume that the domains are equipped with some additional structure and that the map family consists precisely of the maps that preserve this structure. We introduce some examples of such map families for which we will study the (parameterized) complexity of udCSP problems. We begin with families containing all maps.

Definition 3.

Let $\mathcal{D}$ and $\mathcal{E}$ be sets of domains. We define $\mathrm{All}^{\mathcal{D}}_{\mathcal{E}}$ , or just $\mathrm{All}$ if $\mathcal{D}$ and $\mathcal{E}$ are clear from context, as the map family from $\mathcal{D}$ to $\mathcal{E}$ where $\mathrm{All}^{D}_{E}$ consists of all maps from $D$ to $E$ . For a constraint language $(\mathcal{E},\Gamma)$ , we define $\textsc{Unrestricted-CSP}(\Gamma)$ as $\textsc{udCSP}(\mathtt{D}_{\mathbb{N}},\mathcal{E},\Gamma,\mathrm{All})$ .

Dually, we define one of the simplest possible map families.

Definition 4.

Let $\mathcal{D}$ and $\mathcal{E}$ be sets of domains. We define $\mathrm{Id}^{\mathcal{D}}_{\mathcal{E}}$ , or just $\mathrm{Id}$ if $\mathcal{D}$ and $\mathcal{E}$ are clear from context, as the map family from $\mathcal{D}$ to $\mathcal{E}$ where $\mathrm{Id}^{D}_{D}$ contains only the identity function $i(x)=x$ for each $x\in D$ and $\mathrm{Id}^{D}_{E}=\emptyset$ for all distinct $D, E$ .

We note that if some constraint language $\Gamma$ has only one relational domain $D$ , then $\textsc{udCSP}(\Gamma,\mathrm{Id})$ is simply an alternative formulation of the standard CSP problem since the identity maps add no expressive power at all.

It is easy to show that $\textsc{Unrestricted-CSP}(\Gamma)$ is W[1]-hard except when $\Gamma$ is a trivial language definable over unary relations. In fact, even the Boolean equality relation $\mathsf{Eq}=\{00,11\}$ results in a W[1]-hard problem. In contrast, equality constraints are trivial to handle in the standard CSP setting and on the algebraic side one typically allows them to be used regardless of whether $\Gamma$ can express it or not. Hence, to obtain a reasonable problem we need to consider more restricted map families.

Definition 5.

We make the following definitions.

1.

Let $D$ and $E$ be finite domains equipped with some total order. A map $m:D\to E$ is called (anti-)monotone if $x\leq y$ implies that $m(x)\leq m(y)$ ( $m(y)\leq m(x)$ ).
2.

Let $\mathcal{D}$ and $\mathcal{E}$ be sets of finite ordered domains. We define $\mathrm{Mo}^{\mathcal{D}}_{\mathcal{E}}$ , or just $\mathrm{Mo}$ if $\mathcal{D}$ and $\mathcal{E}$ are clear from context, as the map family from $\mathcal{D}$ to $\mathcal{E}$ where $\mathrm{Mo}^{D}_{E}$ consists of all monotone maps from $D$ to $E$ . We similarly define $\mathrm{Mo}^{\prime}$ as the map family of all anti-monotone maps. ²²2The anti-monotone map family is not so interesting in its own right but becomes useful for constraint languages which, in a certain technical sense, can simulate anti-monotone maps and obtain more powerful definitions..
3.

For a constraint language $(\mathcal{E},\Gamma)$ , we note that every domain from $\mathcal{E}$ is isomorphic to some domain from $\mathtt{D}_{\mathbb{N}}$ equipped with the natural order. We define $\textsc{Monotone-CSP}(\Gamma)$ as $\textsc{udCSP}(\mathtt{D}_{\mathbb{N}},\mathtt{D}_{\mathbb{N}},\Gamma,\mathrm{% Mo})$ .

Similarly, we define $\textsc{Bi-Monotone-CSP}(\Gamma)$ as $\textsc{udCSP}(\mathtt{D}_{\mathbb{N}},\mathtt{D}_{\mathbb{N}},\Gamma,\mathrm{% Mo}\cup\mathrm{Mo}^{\prime})$ . We note that conditions of the type $x\geq a$ are monotone while $x\leq a$ are anti-monotone. We often use Iverson bracket notation for describing maps to $\{0,1\}$ .

Example 6.

Consider the NAE-Integer-3-SAT problem in [15], defined as follows: one is given variables $\{x_{1},\dots,x_{k}\}$ that each take a value in $\{1,\dots,n\}$ and clauses $\{C_{1},\dots,C_{m}\}$ of the form ${\rm NAE}(x_{i_{1}}\leq a_{1},x_{i_{2}}\leq a_{2},x_{i_{3}}\leq a_{3})$ , where $a_{1},a_{2},a_{3}\in\{1,\dots,n\}$ , and such a clause is satisfied if not all three inequalities are true and not all are false (i.e., they are “not all equal”). The goal is to find an assignment of the variables that satisfies all given clauses. In our notation this problem can be formulated as $\textsc{udCSP}(\{R_{\mathrm{NAE}}\},\mathrm{Mo}^{\prime})$ where $R_{\mathrm{NAE}}=\{0,1\}^{3}\setminus\{000,111\}$ .

4 Summary of Results

To obtain general results it is necessary to treat constraint languages in a unified way, i.e., to avoid proving hardness and tractability by exhaustive case analyses. However, it is far from clear how e.g. universal algebra can be used for this purpose since there are numerous complicating factors – whether equality is allowed on the relational side, that the underlying map family needs to be taken into account, and to what extent it is possible to restrict the number of cases by considering certain symmetries – and no existing algebraic theory fits this bill.

4.1 An Algebraic Approach for udCSP

The classical algebraic theory for CSPs is based on associating each set of relations $\Gamma$ with a closure $\langle\Gamma\rangle$ containing all primitive positive definable (pp-definable) relations, i.e., if $R$ can be expressed as the models of $\exists y_{1},\ldots,y_{n}\colon\varphi(x_{1},\ldots,x_{r},y_{1},\ldots,y_{n})$ where $\varphi(\cdot)$ is a conjunctive formula over atoms from $\Gamma\cup\{\mathsf{Eq}_{D}\}$ , where $\mathsf{Eq}_{D}$ is the equality relation over $D$ . The point of introducing $\langle\cdot\rangle$ is that sets of the form $\langle\Gamma\rangle$ can be dually defined as sets of polymorphisms $\mathrm{Pol}(\Gamma)$ , i.e., functions over $D$ such that $f$ applied component-wise to tuples in $R$ stays inside $R$ for every $R\in\Gamma$ . Intuitively, a polymorphism describes permissable ways to combine solutions of a CSP $(\Gamma)$ instance, and via the CSP dichotomy theorem [17, 58] we know that the only source of tractability of CSP $(\Gamma)$ is a non-trivial way to combine solutions, which can always be witnessed by an operation in $\mathrm{Pol}(\Gamma)$ . Unfortunately, nearly all aspects of pp-definitions (and, as a consequence, polymorphisms) are unusable in the $\textsc{udCSP}(\Gamma,\mathcal{M})$ setting, since

(1)

we cannot allow existentially quantified variables since our complexity parameter $|V|=k$ blows up if one does gadget replacement and introduces fresh variables for each constraint,
(2)

we cannot allow the equality constraint to be used implicitly since $\textsc{udCSP}(\Gamma,\mathcal{M})$ and $\textsc{udCSP}(\Gamma\cup\{\mathsf{Eq}_{D}\},\mathcal{M})$ may have different complexity, and
(3)

atoms $R(\cdot)$ should be allowed to use maps from $\mathcal{M}$ .

Some, or at least parts of these difficulties, have been addressed before, and lead to generalizations of the classical algebraic theory.

(1)

By removing existential quantification we get partial polymorphisms rather than totally defined polymorphisms, i.e., if $f$ is a partial polymorphism we only require the component-wise application of $f$ to tuples of a relation $R$ to stay inside $R$ if each application is defined.
(2)

If we additionally do not allow equality then the basic object is a partial multipolymorphism, i.e., a function $D\to 2^{D}$ where $2^{D}$ is the powerset of $D$ , and we identify the condition that $f$ returns the empty set to mean that it is undefined.
(3)

The generalization to atoms $R(m_{1}(x_{1}),\ldots,m_{r}(x_{r}))$ for maps $m_{i}\colon\mathtt{D}_{n}\to\mathtt{D}_{d}$ (where $\mathtt{D}_{n}$ is the domain of the relation being defined and $\mathtt{D}_{d}$ the domain of the relation $R$ in the base language) is largely unexplored but has been considered by Carbonnel [19] for the case when all maps have the same domain, and when equality is allowed, called functionally guarded pp-definitions³³3While Carbonnel refers to them as pp-definitions they can be formulated in a quantifier-free way via our maps terminology. [19]. Hadek et al. [38] also consider relational structures with unary functions, but their framework result in gadget reductions between CSPs that increase the number of variables, and is thus not suitable for the udCSP problem.

By combining these notions we land on equality-free functionally guarded primitively positively definable using relations from $\Gamma$ and maps from $\mathcal{M}$ which we refer to as fg-definitions over $(\Gamma,\mathcal{M})$ (but stress that definitions are quantifier-free). We let $\langle\Gamma,\mathcal{M}\rangle^{\nobreak\ }_{\mathrm{fg}}$ be the set of all fg-definable relations over $\Gamma$ .

The complicated aspect in this algebraic undertaking is not to combine the notions but to investigate whether it leads to a useful theory. In particular, arbitrary sets of partial polymorphisms are poorly understood even in the Boolean domain, and virtually nothing general is known about partial multifunctions for arbitrary finite domains. To have any chance of applying the theory we need to be able to make simplifying assumptions and describe partial multifunctions in an effective way.

Here, we dare say that our theory is surprisingly well-behaved even if no particular assumptions are made on $\mathcal{M}$ , and remarkably powerful in the monotone setting. The basic idea to get a functional correspondence to fg-definitions over $(\Gamma,\mathcal{M})$ is to not directly consider the partial multipolymorphisms of $\Gamma$ ( $\mathrm{mPol}(\Gamma)$ ) but rather to interpret these over different domains with the map family $\mathcal{M}$ ( $\mathrm{mPol}(\Gamma,\mathcal{M})$ ), and we say that each such function fg-preserves $(\Gamma,\mathcal{M})$ . This can formally be achieved by generalizing the well-known algebraic notion of concrete homomorphic image to the multifunction setting. We obtain the following general statement.

Theorem 7.

Let $(\Gamma,\mathcal{M})$ and $(\Delta,\mathcal{N})$ be constraint languages on the same instance domain set $\mathcal{D}$ . Then the following holds:

\langle\Gamma,\mathcal{M}\rangle^{\nobreak\ }_{\mathrm{fg}}\subseteq\langle% \Delta,\mathcal{N}\rangle^{\nobreak\ }_{\mathrm{fg}}\iff\mathrm{mPol}(\Delta,% \mathcal{N})\subseteq\mathrm{mPol}(\Gamma,\mathcal{M})

For the case when $\mathcal{M}$ contains all maps then $\mathrm{mPol}(R,\mathcal{M})$ collapses to partial multifunctions definable by polymorphism patterns. This means that we can concentrate on $k$ -ary partial multifunctions definable by identities of the form $f(x_{1},\ldots,x_{k})\approx x$ (sometimes called strong Maltsev conditions of height at most 1, or just polymorphism patterns). Total functions satisfying such identities are well-studied in the algebraic theory of CSPs [4] and include e.g. Maltsev operations definable by $m(x,x,y)\approx m(y,x,x)\approx y$ , and majority operations definable by $\mathrm{maj}(x,x,y)\approx\mathrm{maj}(x,y,x)\approx\mathrm{maj}(y,x,x)\approx x$ .

The main point of investigating such identities is that we no longer have to consider exhaustive case analysis between similar types of operations and can instead concentrate on the algebraically relevant properties. For example, any finite-domain CSP whose template is invariant under a total Maltsev operation can be solved in polynomial time via a generalization of Gaussian elimination [16] while a majority operation ensures that the CSP can be solved by local consistency.

It is unclear if we get something similarly well-behaved for restricted types of map families, and we stress that this question is virtually unexplored in algebra. We prove that if $\mathcal{M}=\mathrm{Mo}$ is the set of monotone maps then we get a description in terms of ordered polymorphism patterns. Abstractly, these can be defined by systems of identities of the form $f(x_{1},\ldots,x_{k})\approx x$ where the variables are equipped with an ordering, and we can construct partial multifunctions over some concrete domain $\mathtt{D}_{d}$ by considering monotone maps from the pattern variables to $\mathtt{D}_{d}$ . This makes it possible to formulate median, minimum and maximum operations in a straightforward way. E.g., if we order $x<y<z$ then the conditions for median say that $\mathsf{median}(x,y,z)=\mathsf{median}(x,z,y)=\mathsf{median}(y,x,z)=\mathsf{% median}(y,z,x)=\mathsf{median}(z,x,y)=\mathsf{median}(z,y,x)=y$ and maximum could be defined as $\mathsf{max}(x,y)=\mathsf{max}(y,x)=y$ . These ordered patterns can then be interpreted, say, over $\mathtt{D}_{3}$ , by letting the resulting partial multifunctions be defined for all possible combinations of monotone maps and identities (formally, the union of all concrete homomorphic images with respect to monotone maps from the variables to $\mathtt{D}_{3}$ ). Since it is cumbersome to specify an ordering for each pattern we often assume that the pattern variables take values in $\mathtt{D}_{d}$ for some $d\geq 1$ , and then use the natural order. For example, we could then concisely specify the median identities as $\mathrm{median}(0,1,2)\approx\ldots\approx\mathrm{median}(2,1,0)\approx 1$ .

Here it might be interesting to note that the minimum/maximum cannot be defined via the classical algebraic toolbox [4] but are instead treated as special instances of semilattice operations. This is not a problem when studying the classical complexity of CSPs but preserving the order becomes crucial in the $\textsc{udCSP}(\Gamma,\mathrm{Mo})$ setting.

4.2 udCSP with Monotone Maps and the Twin-width Parameter

Let us now turn to the complexity of $\textsc{udCSP}(\Gamma,\mathrm{Mo})$ and the twin-width parameter. In light of Theorem 7 we expect the complexity of this problem to be captured by (partial) polymorphisms definable by systems of identities with order, and this is indeed the case.

Theorem 8.

Let $\Gamma$ be a constraint language over finite ordered domain(s). If $(\Gamma,\mathrm{Mo})$ is fg-preserved by $\mathsf{min}$ , $\mathsf{max}$ or $\mathsf{median}$ , then $\textsc{udCSP}(\Gamma,\mathrm{Mo})$ is in $P$ . Otherwise, $\textsc{udCSP}(\Gamma,\mathrm{Mo})$ is NP-hard.

We similarly obtain a dichotomy result for the udCSP problem where both monotone and anti-monotone maps are allowed.

Theorem 9.

Let $\Gamma$ be a constraint language. If $(\Gamma,\mathrm{Mo}\cup\mathrm{Mo}^{\prime})$ is fg-preserved by $\mathsf{median}$ , then $\textsc{Bi-Monotone-CSP}(\Gamma)$ is in P. Otherwise, $\textsc{Bi-Monotone-CSP}(\Gamma)$ is NP-hard.

In addition, up to FPT-reductions, we show that for every language $\Gamma$ such that $\textsc{udCSP}(\Gamma,\mathrm{Mo})$ is NP-hard, $\textsc{udCSP}(\Gamma,\mathrm{Mo})$ and $\textsc{udCSP}(\Gamma,\mathrm{Mo}\cup\mathrm{Mo}^{\prime})$ have the same complexity. Thus we may assume that we are working with both monotone and anti-monotone maps. For parameterized tractability, we note that if $\Gamma$ can fg-define all permutations⁴⁴4To be precise we require for every permutation $\sigma\colon\mathtt{D}_{n}\to\mathtt{D}_{n}$ that $(\Gamma,\mathrm{Mo}\cup\mathrm{Mo}^{\prime})$ can fg-define the graph $\sigma^{\bullet}=\{(x,\sigma(x))\mid x\in\mathtt{D}_{n}\}$ ., then $\textsc{udCSP}(\Gamma,\mathrm{Mo}\cup\mathrm{Mo}^{\prime})$ is W[1]-hard by standard reductions. We thus seek an algebraic criterion that is an obstruction towards this. We define an ordered polymorphism pattern, the connector polymorphism, that serves this role. This operation can be abstractly defined over $\mathtt{D}_{3}$ as $\mathsf{con}(0,0,1,2,2)=0,\mathsf{con}(0,2,1,0,2)=1$ , and via the algebraic machinery described in Section 4.1 this pattern can be interpreted over any domain $\mathtt{D}_{d}$ to produce a concrete operation $\mathrm{con}_{d}$ . We also define a canonical W[1]-hardness relation $R_{3}=\{00,02,11,20,22\}$ , and note the following (somewhat informally).

(1)

$(R_{3},\mathrm{Mo})$ can fg-define the graph of every permutation.
(2)

Every language $(\Gamma,\mathrm{Mo}\cup\mathrm{Mo}^{\prime})$ not fg-preserved by $\mathsf{con}$ can fg-define $R_{3}$ .

We get the following theorem. Recall by Theorem 8 that if $\Gamma$ is invariant under $\min$ or $\max$ then $\textsc{udCSP}(\Gamma,\mathrm{Mo})$ is in P, so the added assumption does not diminish the hardness claim.

Theorem 10.

Assume that $(\Gamma,\mathrm{Mo})$ is not fg-preserved by $\mathsf{min}$ or $\mathsf{max}$ . If $\mathsf{con}\notin\mathrm{mPol}(\Gamma,\mathrm{Mo})$ then $\textsc{udCSP}(\Gamma,\mathrm{Mo})$ is W[1]-hard.

In the other direction, we show that for every finite language $\Gamma$ preserved by $\mathsf{con}$ , there is a permutation $\sigma$ not fg-definable in $\Gamma$ . As mentioned, twin-width is a notion of structural complexity that is very well suited for binary structures with an order, and the canonical example of a binary structure with unbounded twin-width is precisely the ability to define all permutations [13]. We use the notion of twin-width over ordered domains, which is particularly well-behaved [12]. There is then a notion of grid-rank, which serves as a obstruction towards a binary structure having bounded twin-width. We show that for every language $(\Gamma,\mathrm{Mo}\cup\mathrm{Mo}^{\prime})$ fg-preserved by $\mathsf{con}$ , the set of binary relations fg-definable over $\Gamma$ has constant grid-rank, and thus bounded twin-width (in fact, even if $\Gamma$ itself is not binary). By results from [12], and a dynamic programming algorithm, this is sufficient for a tractability result for binary languages.

Theorem 11.

Let $\Gamma$ be a binary constraint language over finite ordered domain(s). If $\mathsf{con}\in\mathrm{mPol}(\Gamma,\mathrm{Mo})$ then $\textsc{udCSP}(\Gamma,\mathrm{Mo}\cup\mathrm{Mo}^{\prime})$ is in FPT.

Extending Theorem 11 to relations of arbitrary arity meets difficulties. Twin-width is intrinsically a property of binary structures⁵⁵5and non-binary structures with first-order transductions from binary structures of bounded twin-width [13].. Furthermore, based on conversations with experts in the area, establishing a useful width notion for non-binary structures that generalizes twin-width is considered extremely challenging, or possibly impossible, given the tendency of non-binary structures to very rapidly become uncontrollably expressive. Thus we have three options:

(1)

hoping that no tractable non-binary languages exist,
(2)

moving on from twin-width to other width notions more suitable for non-binary structures, or
(3)

developing such a width-notion ourselves to suit our needs.

The first is a non-starter. Consider the basic 1-in-3 relation $R_{1/3}=\{100,010,001\}$ . It is easily verified to be preserved by $\mathrm{con}_{2}$ , so the W[1]-hardness proof of Theorem 10 does not apply. There is also no obvious way to reduce $\textsc{udCSP}(R_{1/3},\mathrm{Mo})$ to a binary structure while preserving bounded twin-width. In fact, the FPT-status of $\textsc{udCSP}(R_{1/3},\mathrm{Mo})$ is left as an open problem.

For the second, the most natural parameter to investigate is clique-width or one of its functionally equivalent parameters such as boolean width or rank-width. Rank-width is possible to extend to non-binary relations so a reasonable first question is whether the (graphs/matrices corresponding to a) set of binary, $\mathrm{Mo}$ -fg-definable relations over a relation $R$ preserved by the connector polymorphism has bounded rank-width or not. Here, we give a simple relation $R=\{01,10,12,21\}$ over $\mathtt{D}_{3}$ which together with Boolean implication $\{00,01,11\}$ can be used to give a construction in terms of diamond graphs which has unbounded rank-width.

Thus, we are left with designing a non-binary width parameter that generalizes twin-width. We consider such a parameter, inspired by the properties of $\mathsf{con}$ , based on extending grid-rank to non-binary structures which we call projected grid-rank. Towards the definition of this parameter we first note that simply excluding $k$ -grids is not enough: the relations $S_{n}(x,y,z)\equiv(x+y=z)$ over all domains $\mathtt{D}_{n}$ together with unary relations give a W[1]-hard CSP but, viewed as a 3-dimensional grid, each relation does not even contain a $2\times 2\times 2$ subgrid where every cell is non-constant. Instead, we define a projected grid of $R\subseteq\mathtt{D}_{n}^{r}$ w.r.t. a partition $A\cup B$ of $[r]$ to be a relation $R^{\prime}\subseteq S\times T$ where $S$ and $T$ are two ordered subsets of $\mathtt{D}_{n}^{A}$ , and $\mathtt{D}_{n}^{B}$ , respectively, such that $R^{\prime}=\{(s,t)\in S\times T\mid s\cup t\in R\}$ where $s\cup t$ denotes the tuple in $\mathtt{D}_{n}^{r}$ whose entries in coordinates $A$ match $s$ and whose entries in coordinates $B$ match $t$ . We then say that $R$ has projected grid-rank $k$ if it has a projected grid with grid-rank at least $k$ . The definition generalizes to constraint languages in the obvious way and we then relate bounded projected grid-rank to the connector polymorphism as follows.

Theorem 12.

Let $\Gamma$ be a finite base language. The set of fg-definable relations over $(\Gamma,\mathrm{Mo}\cup\mathrm{Mo}^{\prime})$ has bounded projected grid-rank if and only if $\Gamma$ satisfies the connector property.

If we return to the troublesome relation $S_{n}(x,y,z)\equiv(x+y=z)$ over $\mathtt{D}_{n}$ then we find that (1) it has the connector property, but (2) its projective grid-rank is growing with $n$ . Thus, any finite language $\Gamma$ with the connector property fails to fg-define $S_{n}$ for some $n\in\mathbb{N}$ . (This is analogous to the situation with permutations – every individual permutation has the connector property, but any finite language that can fg-define all of them does not.)

All evidence thus far suggests that the connector property is the correct boundary for tractability, even for higher-arity relations. We give one further piece of evidence. We show that for any binary projection of a $k$ -ary relation with bounded projected grid rank, the projected relation has bounded grid-rank (and thus bounded twin-width). This in particular rules out every W[1]-hardness proof we can think of for a language with the connector property.

Theorem 13.

There is a function $f\colon\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ such that the following holds: For all $d,k,n\in\mathbb{N}$ and every relation $R\subseteq{\mathtt{D}_{n}^{k}}$ with projected grid-rank at most $d$ , each binary projection of $R$ has grid-rank at most $f(d,k)$ .

The proof is based on a multi-layered Ramsey argument using the existence of large high-rank grids (analogous to applications of the Marcus-Tardos theorem in twin-width theory [12, 13, 56]) with the requirement that higher dimensions exhibit regular lexicographic-like ordering, inspired by the two-dimensional Erdős-Szekeres theorem of Fishburn and Graham [28]. See Figure 1 for a summary of our width results. Based on the strong connection between the connector and bounded width we pose the following conjecture (note that the hardness part of the conjecture already follows from our results and that we have verified the FPT part for binary relations).

Conjecture 14.

Let $\Gamma$ be a constraint language such that $\textsc{udCSP}(\Gamma,\mathrm{Mo})$ is NP-hard. Then $\textsc{udCSP}(\Gamma,\mathrm{Mo})$ is FPT if the connector polymorphism $\mathsf{con}$ fg-preserves $(\Gamma,\mathrm{Mo})$ and W[1]-hard otherwise.

Property

fg-definability

Projected GR

TW (binary proj.)

RW

Connector

Not all permutations

Bounded

Unbounded

Not connector

All permutations

Unbounded

Figure 1: Connections between the connector polymorphism and width-properties. In the table, GR stands for grid-rank, TW for twin-width, and RW for rank-width.

5 Applications and related work

We finish this paper by highlighting some interesting applications of the udCSP framework together with a number of connections to other problems.

Graph separation

Let us consider a natural application of udCSP: min-cuts in digraphs. We begin with the basic min-cut problem. Let $G$ be a digraph with $s,t\in V(G)$ , and let $\mathcal{P}=\{P_{1},\ldots,P_{k}\}$ be an arc-disjoint $s t$ -max flow in $G$ . For each path $P_{i}\in\mathcal{P}$ , we enumerate the edges of $P_{i}$ from $s$ to $t$ as $e_{i,1},\ldots,e_{i,m_{i}}$ . Then, there is an instance of $\textsc{udCSP}(\Gamma,\mathrm{Mo})$ over the Boolean language $\Gamma=\{\textsf{Impl},0\}$ with $k$ variables $x_{1},\ldots,x_{k}$ whose solutions are in bijection with the $s t$ -min cuts in $G$ (where $\textsf{Impl}=\{00,01,11\}$ and where we write $0$ for the constant Boolean relation $\{0\}$ ). We let $V(\mathcal{P}),E(\mathcal{P})$ denote the vertices and edges in $\mathcal{P}$ , respectively. Define a graph $G^{\prime}$ where the edges of the paths in $\mathcal{P}$ have been removed, i.e. $V(G^{\prime})=V(G)$ and $E(G^{\prime})=E(G)\setminus E(\mathcal{P})$ . For every pair of vertices $u,v\in V(\mathcal{P})\setminus\{t\}$ and $i,j\in[k]$ such that $u\in V(P_{i})$ , $v\in V(P_{j})$ , $(u,i)\neq(v,j)$ , and there is a path from $u$ to $v$ in $G^{\prime}$ with internal vertices (if any) from $V(G)\setminus V(\mathcal{P})$ , let $e_{i,a}$ and $e_{j,b}$ be the edges of $P_{i}$ following $u$ and $P_{j}$ following $v$ , respectively, and add a constraint $\textsf{Impl}([x_{i}\geq a],[x_{j}\geq b])$ . This includes the case $u=v$ if $i\neq j$ . The satisfying assignments of the resulting $\textsc{udCSP}(\Gamma,\mathrm{Mo})$ instance are in bijection with $s t$ -min cuts in the following sense. If $Z\subseteq E(G)$ is an $s t$ -min cut, then for each $i\in[k]$ let $Z\cap E(P_{i})=\{e_{i,n_{i}}\}$ and let $\varphi$ be the assignment where $\varphi(x_{i})=n_{i}$ for each $i$ . Then $\varphi$ satisfies all constraints, since otherwise there is a path in $G^{\prime}$ from the $s$ -side of $Z$ to the $t$ -side of $Z$ . Conversely, for every satisfying assignment $\varphi$ of the udCSP instance, let $Z=\{e_{i,n_{i}}\mid x_{i}=n_{i},i\in[k]\}$ . Then $Z$ is an $s t$ -min cut, since any path from the $s$ -side of $Z$ to the $t$ -side of $Z$ implies a Impl-constraint violated by $\varphi$ .

We can now view other min-cut problems through the lens of udCSP. First consider Paired Min-Cut, where some edges $e_{i,a}$ and $e_{j,b}$ are paired up, with the constraint that a min-cut $Z$ should contain $e_{i,a}$ if and only if it contains $e_{j,b}$ . Thus we want $x_{i}=a$ if and only if $x_{j}=b$ , which can be captured by the relation $R=\{00,02,11,20,22\}$ using unary maps as follows: $R(f_{a}(x_{i}),f_{b}(x_{j}))$ where $f_{i}(x)=0$ if $x<i$ , $f_{i}(x)=1$ if $x=i$ , and $f_{i}(x)=2$ , otherwise.

Thus $\textsc{udCSP}(\{R,\mathsf{Impl},0\},\mathrm{Mo})$ captures Paired Min-Cut and is W[1]-hard. We consider a couple of variations on this theme. Let $e_{i,a}=uv$ and $e_{j,b}=u^{\prime}v^{\prime}$ be two edges.

(1)

Replacing $R$ with $R_{a}=\{00,02,11,22\}$ yields a pairing constraint that additionally forbids that $u v$ is on the $s$ -side and $u^{\prime}v^{\prime}$ on the $t$ -side of the cut. This captures the constraint $(u\to v\to u^{\prime}\to v^{\prime})$ from the 3-Chain SAT problem [23, 44].
(2)

Replacing $R$ with $R_{b}=\{02,11,20,22\}$ yields a pairing constraint that additionally forbids that both $u v$ and $u^{\prime}v^{\prime}$ are on the $t$ -side of the cut, as in the Coupled Min-Cut problem [45].
(3)

Replacing $R$ with $R_{c}=\{00,02,11,20\}$ yields a pairing constraint that additionally forbids that both $u v$ and $u^{\prime}v^{\prime}$ are on the $s$ -side of the cut (as a kind of dual to Coupled Min-Cut).

It is readily checked that each of these three relations satisfies the connector property, hence $\textsc{udCSP}(\{R_{a},R_{b},R_{c},\mathsf{Impl},0\},\mathrm{Mo})$ is FPT. We note that $\ell$ -Chain SAT and Coupled Min-Cut were long-standing open problems, first solved via the introduction of the flow augmentation framework and the Boolean MinCSP dichotomy result mentioned above [44, 45]. Thus, the $\textsc{udCSP}(\Gamma,\mathrm{Mo})$ perspective “explains” the tractability of Coupled Min-Cut and $\ell$ -Chain SAT, and the intractability of Paired Min-Cut, in a more uniform and generalizable manner. Furthermore, as noted, the final phase in the algorithm of [45] for tractable bijunctive Boolean MinCSP is a complex branching algorithm that effectively solves an instance of a $k$ -variable udCSP. We find that this step can to a large extent be replaced and simplified by the notion of bounded twin-width.

One-hot

Another representation of an arbitrary large domain over a smaller domain is the one hot encoding, where a variable $x$ with domain $D=\{d_{1},\ldots,d_{n}\}$ is represented by $n$ Boolean variables $x_{i}$ indicating $x=d_{i}$ for each $i\in[n]$ . This fits easily into our setting, by using the Boolean base domain $B=\mathtt{D}_{2}$ , and for any larger domain $\mathtt{D}_{n}$ letting the map family $\mathrm{OH}$ consist of the indicator maps $f_{i}(x)=[x=i]$ . For FPT purposes, this is essentially equivalent to the Weighted CSP problem studied by Marx [49]. In this problem, given a fixed Boolean language $\Gamma$ , the input is a formula $\varphi$ over $\Gamma$ and an integer $k$ , and the question is whether $\varphi$ has a satisfying assignment where precisely $k$ variables are true. Marx gave a dichotomy for this setting, showing that the problem is FPT if $\Gamma$ is weakly separable, and W[1]-hard otherwise. Weak separability can be defined via partial polymorphisms [46], thus fitting into the algebraic framework.

To see that MinCSP $(\Gamma)$ and $\textsc{udCSP}(\Gamma,\mathrm{OH})$ are FPT-equivalent, consider the multicoloured version of Weighted CSP $(\Gamma)$ , where the variable set $V$ is additionally partitioned into $k$ parts $V=V_{1}\cup\ldots\cup V_{k}$ , with the restriction that the solution should contain precisely one true variable in each part $V_{i}$ . It is easy to see that Multicoloured Weighted CSP $(\Gamma)$ is equivalent to $\textsc{udCSP}(\Gamma,\mathrm{OH})$ , by interpreting each set $V_{i}$ as the domain of a variable $x^{i}$ in a udCSP instance. In turn, Multicoloured Weighted CSP is FPT-equivalent to Weighted CSP: in one direction, we can use the standard method of colour coding [1, 24] to guess the variable partition. In the other direction, it is a folklore result that Multicoloured Weighted CSP reduces back to Weighted CSP by weight-coding tricks (cf. [50, Lemma 3.2]); alternatively, it can be shown to be FPT directly [18, 49]. Hence a dichotomy for $\textsc{udCSP}(\Gamma,\mathrm{OH})$ follows from Marx [49].

Many-valued logic

We take the opportunity to broaden the perspective with computational complexity in mind. Consider clauses which are disjunctions of propositions of the form $x\in S$ , where $x$ is a variable and $S$ is a subset of a finite domain $D$ . This is the basis for a variant of many-valued logics known as signed logic; in this context, the sets of $S$ are called signs. Boolean propositional logic is an example with domain $\{0,1\}$ and literals $x$ , $\neg x$ corresponding to $x\in\{1\}$ , $x\in\{0\}$ , respectively. A motivation behind signed logics is that they offer a convenient framework for working with many-valued logics [39, 48, 53]. Computational aspects of signed logics have been studied extensively: the survey by Beckert, Hähnle, and Manyá [5] covers early results whereas more recent complexity-oriented results can be found in, for instance, [2, 20, 22, 35, 41].

Most complexity results in the literature focus on CNF formulas. Naturally, more complex formulas can be constructed by using other relations than clauses. If the domain $D$ is fixed and finite, then the complexity of the satisfiability follows immediately from the finite-domain CSP classification by Bulatov [17] and Zhuk [58]. There are indeed contexts where domain flexibility is desirable; database applications and knowledge representation in AI are conceivable examples. Another motivation is that certain families of many-valued logics can be treated in a uniform manner. It is common that such a family is parameterized by $k\geq 2$ and each logic has a value domain of size $k$ . One example is the family $P_{2},P_{3},\dots$ by Post [57, Section 11] and there are other examples by Gödel [37] and Łukasiewicz (cf. [42, Section III]).

By viewing signs as unary maps, we can drop restrictions: the domain is part of the input and the relations are not restricted to clauses. It is common that the signs have the form $\uparrow a=\{d\in D\;|\;d\succeq a\}$ and $\downarrow a=\{d\in D\;|\;d\preceq a\}$ , where $\prec$ is some partial order on $D$ ; formulas defined on such signs are called regular signed formulas. Example 6 and NAE-Integer-3-SAT is a problem of this kind where the underlying partial order is a total order. We can obtain a P/NP dichotomy for regular signed formulas over the totally ordered domain ${\mathbb{N}}$ : $\uparrow a(x)$ corresponds to the monotone map $[x\geq a]$ while $\downarrow a(x)$ corresponds to the anti-monotone map $[x\leq a]$ . The connection with $\textsc{udCSP}(\Gamma,\mathrm{Mo}\cup\mathrm{Mo}^{\prime})$ is obvious and we get a P/NP-dichotomy from Theorem 9. Signed logics have been studied with other partial orders (such as distributive and modular lattices) in mind than those that we have considered, cf. [5, Section 7] and [22, Section 7]. Another example is monosigned formulas: i.e. formulas with signs of the form $\{d\}$ for some $d\in D$ . To analyze the complexity of the monosigned case, then we have to understand the complexity of $\textsc{udCSP}(\Gamma,\mathrm{OH})$ for Boolean $\Gamma$ – a problem that we have already encountered.

Further variants of signed logics appear in the literature. For instance, Bodirsky and Mottet [8] consider an infinite domain $D$ and a finite set $U$ of unary relations $U_{1},\dots,U_{n}\subseteq D$ . They prove a P/NP dichotomy for CSP $(\Gamma)$ where the finite constraint language $\Gamma$ only contains relations that are first-order definable in $\{U_{1},\dots,U_{n}\}$ . This may be viewed as a variant of signed logic where the allowed signs are those that are first-order definable in $U$ . Thus, the set of available signs is finite and this result is incomparable to ours.

Map Type

Classical Complexity

Parameterized Complexity

Unrestricted

in P if

\Gamma

is essentially unary

FPT if

\Gamma

is essentially unary

Monotone

in P iff

\operatorname{Pol}(\Gamma)\cap\{\min,\max,\operatorname{median}\}\neq\emptyset

restriction:

\Gamma

binary

FPT iff

\Gamma

has connector

Figure 2: Complexity of

\textsc{udCSP}(\Gamma,\mathcal{M})

for unrestricted and monotone maps.

6 Discussion

We have studied connections between parameterized complexity, universal algebra, and structural width parameters. This was enabled by introducing the $\textsc{udCSP}(\Gamma,\mathcal{M})$ framework to represent CSPs with few variables but with unbounded domain size. These problems have appeared in the literature as important, intermediate problems in both hardness and tractability contexts, but has not been systematically studied as an independent formalism. To be able to obtain general results we introduced a novel algebraic approach based on partial multifunctions and proved that the polymorphism side boiled down to partial multifunctions (definable as patterns) interpreted over different domains with the help of the map family $\mathcal{M}$ . In the monotone world these patterns turned out to be particularly simple and resulted in order polymorphisms where the ordering of the input arguments is sufficient to determine the output.

We have presented a computational complexity dichotomy for $\textsc{Monotone-CSP}(\Gamma)$ via the classical $\min,\max$ and $\operatorname{median}$ operations. In the parameterized setting we proved W[1]-hardness if $\Gamma$ does not have the connector property, and proved a complementary FPT result for binary base languages $\Gamma$ . However, even the binary setting is rather expressive and we exemplify this by showing how one of the hardest steps in the Boolean MinCSP dichotomy by [45] can be simplified by a reduction to a Monotone-CSP problem. Extending our complexity results to higher-arity relations is related to the difficult task of generalizing twin-width to non-binary structures. Inspired by algebraic results, we introduced a novel structural parameter, projected grid-rank, and showed how it relates to the connector property and the twin-width parameter. Based on this, we conjecture that $\textsc{Monotone-CSP}(\Gamma)$ is FPT if and only if $\Gamma$ has the connector property. We want to point out that the $\textsc{udCSP}(\Gamma,\mathrm{Mo})$ framework is extremely expressive and, based on the connections we already made in this paper, seems to be just the right blend since it is rich enough to connect to powerful methods and deep questions in parameterized complexity while still being tameable with universal algebra. We close the paper by discussing some future research directions.

A formal connection to parameterized MinCSP?

Let us begin with one of the questions that motivated this study. As mentioned in the introduction, there appears to be a connection between the parameterized complexity of MinCSP $(\Gamma)$ parameterized by the number of false constraints and the complexity of $\textsc{udCSP}(\Gamma^{\prime},\mathcal{M})$ -problems expressible in the MinCSP, for suitable $\Gamma^{\prime}$ and $\mathcal{M}$ (especially $\mathcal{M}=\mathrm{Mo}$ ). It would be very interesting to work out this connection more formally. For example, is there a direct algebraic proof that if $\Gamma$ belongs to one of the FPT classes for Boolean MinCSP $(\Gamma)$ , then $\Gamma$ cannot express a suitably defined FPT-reduction from any problem $\textsc{Monotone-CSP}(\Gamma^{\prime})$ where $\Gamma^{\prime}$ does not have the connector property?

We note that the classical complexity of MinCSP and Valued CSP problems is characterized algebraically by fractional or weighted polymorphisms [31], which are quite different from the partial polymorphism patterns considered in this paper. Furthermore, they are too coarse-grained to distinguish between FPT and W[1]-hard cases of MinCSP $(\Gamma)$ . Consequentially, existing parameterized complexity characterizations of MinCSP $(\Gamma)$ -type problems have all been non-algebraic in nature, either purely combinatorial in their dichotomy descriptions [23, 45, 55], or giving only a partial dichotomy (e.g., classifying a finite list of cases) [25, 54], or else only considering the complexity up to constant-factor FPT approximations [9, 27]. The latter is a more well-behaved question, algebraically speaking, than the existence of an exact FPT-algorithm since constant-factor FPT approximability is preserved under equality-free pp-definitions. More algebraically guided tools are expected to be required for FPT/W[1]-dichotomies for MinCSP $(\Gamma)$ going much beyond this list.

For a particularly intriguing case, Temporal CSPs are a class of infinite-domain CSPs over the ordered domain $(\mathbb{Q},<)$ . As with finite-domain CSPs, there is a notion of a language-restricted version Temporal CSP $(\Gamma)$ for a constraint language $\Gamma$ , in which case $\Gamma$ contains a finite set of relations definable over $(\mathbb{Q},<)$ in first-order logic. The set of tractable temporal CSPs was characterized by Bodirsky and Kára [7] (covered in a more modern way in the book of Bodirsky [6]). A very natural follow-up question is to determine the temporal languages $\Gamma$ such that the MinCSP over $\Gamma$ is FPT parameterized by the solution cost. However, this task has proven highly challenging so far, as temporal CSPs have significant structural complexity. The results of this paper should help in this regard.

A dichotomy for non-binary relations

The most intriguing, and also the hardest, open question is whether our dichotomy for Monotone-CSP can be strengthened to arbitrary non-binary relations, and since our hardness condition is still valid the missing case is when $\Gamma$ has the connector property. Classical graph parameters such as rank-width or clique-width are not useful in this setting since we have proved that there exist families of languages with the connector property that have unbounded rank-width. We therefore investigated a higher-arity generalization of grid-rank, projected grid-rank, and proved that the connector property coincides with bounded projected grid-rank. Through a complex Ramsey argument we proved that projected grid-rank coincides with bounded twin-width of binary projections. Constructively using this property seems hard, however, without simultaneously generalizing twin-width and contraction sequences to higher-arity relations, and via our Ramsey argument we know that we cannot actually escape twin-width. For a concrete example where the complexity of $\textsc{Monotone-CSP}(\Gamma)$ is unknown, consider e.g. $\Gamma=\{R_{1/3}\}$ for $R_{1/3}=\{001,010,100\}$ . This relation has the connector property but is non-binary, and could be a manageable starting point towards resolving the full dichotomy.

More classes of $\textsc{udCSP}(\Gamma,\mathcal{M})$ problems

We have considered just a small assortment of map families in this paper. What other map families result in interesting $\textsc{udCSP}(\Gamma,\mathcal{M})$ problems? The signed logics from Section 5 may serve as a source of inspiration. They have been studied with other partial orders in mind than those that we have considered, cf. [5, Section 7] and [22, Section 7]. Typical examples are the full class of lattices and subclasses such as distributive and modular lattices. For even more general classes it is easy to formulate map families with respect to an algebraic structure, e.g., by associating the base domain $\mathtt{D}_{d}$ and the input domain $\mathtt{D}_{n}$ with groups (or some other algebraic structures) and then consider all group homomorphisms. This question can also be generalized with category theory where the basic algebraic objects (e.g., groups or orders) would correspond to categories, and the map family would correspond to sets of morphisms.

References

[1] Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. Journal of the ACM, 42(4):844–856, 1995. doi:10.1145/210332.210337.
[2] Carlos Ansótegui and Felip Manyà. New logical and complexity results for signed-SAT. In Proc. 33rd IEEE International Symposium on Multiple-Valued Logic (ISMVL-2023), pages 181–187, 2003. doi:10.1109/ISMVL.2003.1201404.
[3] L. Barto, J. Opršal, and M. Pinsker. The wonderland of reflections. Israel Journal of Mathematics, 223(1):363–398, February 2018. doi:10.1007/s11856-017-1621-9.
[4] Libor Barto, Andrei A. Krokhin, and Ross Willard. Polymorphisms, and how to use them. In The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 1–44. Dagstuhl Publishing, 2017. doi:10.4230/DFU.VOL7.15301.1.
[5] Bernhard Beckert, Reiner Hähnle, and Felip Manyà. The SAT problem of signed CNF formulas. In David Basin, Marcello D’Agostino, Dov M. Gabbay, Seán Matthews, and Luca Viganò, editors, Labelled Deduction, Applied Logic Series, vol 17, pages 59–80. Springer Netherlands, 2000.
[6] Manuel Bodirsky. Complexity of Infinite-Domain Constraint Satisfaction. Cambridge University Press, 2021.
[7] Manuel Bodirsky and Jan Kára. The complexity of temporal constraint satisfaction problems. J. ACM, 57(2):9:1–9:41, 2010. doi:10.1145/1667053.1667058.
[8] Manuel Bodirsky and Antoine Mottet. A dichotomy for first-order reducts of unary structures. Logical Methods in Computer Science, 14(2), 2018. doi:10.23638/LMCS-14(2:13)2018.
[9] Édouard Bonnet, László Egri, and Dániel Marx. Fixed-parameter approximability of Boolean MinCSPs. In Proc. 24th Annual European Symposium on Algorithms (ESA-2016), pages 18:1–18:18, 2016. doi:10.4230/LIPIcs.ESA.2016.18.
[10] Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width II: small classes. Combinatorial Theory, 2(2), 2022. doi:10.5070/C62257876.
[11] Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width III: max independent set, min dominating set, and coloring. SIAM Journal on Computing, 53(5):1602–1640, 2024. doi:10.1137/21M142188X.
[12] Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, and Szymon Toruńczyk. Twin-width IV: ordered graphs and matrices. Journal of the ACM, 71(3):1–45, 2024.
[13] Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width I: tractable FO model checking. Journal of the ACM, 69(1):3:1–3:46, 2022. doi:10.1145/3486655.
[14] Zarathustra Brady. Notes on CSPs and polymorphisms. CoRR, abs/2210.07383, 2022. doi:10.48550/arXiv.2210.07383.
[15] Karl Bringmann, Danny Hermelin, Matthias Mnich, and Erik Jan van Leeuwen. Parameterized complexity dichotomy for Steiner multicut. Journal of Computer and System Sciences, 82(6):1020–1043, 2016. doi:10.1016/J.JCSS.2016.03.003.
[16] Andrei Bulatov and Víctor Dalmau. A simple algorithm for mal’tsev constraints. SIAM Journal on Computing, 36(1):16–27, 2006. doi:10.1137/050628957.
[17] Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs. In Proc. 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS-2017), pages 319–330, 2017. doi:10.1109/FOCS.2017.37.
[18] Andrei A. Bulatov and Dániel Marx. Constraint satisfaction parameterized by solution size. SIAM Journal on Computing, 43(2):573–616, 2014. doi:10.1137/120882160.
[19] Clément Carbonnel. On redundancy in constraint satisfaction problems. In Proc. 28th International Conference on Principles and Practice of Constraint Programming (CP-2022), pages 11:1–11:15, 2022. doi:10.4230/LIPIcs.CP.2022.11.
[20] Witold Charatonik and Michal Wrona. 2-SAT problems in some multi-valued logics based on finite lattices. In Proc. 37th International Symposium on Multiple-Valued Logic (ISMVL-2007), page 21, 2007. doi:10.1109/ISMVL.2007.1.
[21] Sitan Chen, Adam R. Klivans, and Raghu Meka. Learning deep ReLU networks is fixed-parameter tractable. In Proc. 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS-2021), pages 696–707, 2021. doi:10.1109/FOCS52979.2021.00073.
[22] Victor Chepoi, Nadia Creignou, Miki Hermann, and Gernot Salzer. The Helly property and satisfiability of Boolean formulas defined on set families. European Jornal of Combinatorics, 31(2):502–516, 2010. doi:10.1016/J.EJC.2009.03.022.
[23] Rajesh Chitnis, László Egri, and Dániel Marx. List H-coloring a graph by removing few vertices. Algorithmica, 78(1):110–146, 2017. doi:10.1007/S00453-016-0139-6.
[24] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.
[25] Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, Marcin Pilipczuk, and Roohani Sharma. Parameterized complexity classification for interval constraints. In Proc. 18th International Symposium on Parameterized and Exact Computation (IPEC-2023), volume 285, pages 11:1–11:19, 2023. doi:10.4230/LIPIcs.IPEC.2023.11.
[26] Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, and Magnus Wahlström. Almost consistent systems of linear equations. ACM Transactions on Algorithms, 21(4):44:1–44:55, 2025. doi:10.1145/3733107.
[27] Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, and Magnus Wahlström. Parameterized approximability for modular linear equations. In Proc. 33rd Annual European Symposium on Algorithms (ESA-2025), pages 88:1–88:15, 2025. doi:10.4230/LIPIcs.ESA.2025.88.
[28] Peter C Fishburn and Ronald L Graham. Lexicographic Ramsey theory. Journal of Combinatorial Theory, Series A, 62(2):280–298, 1993.
[29] Vincent Froese and Christoph Hertrich. Training neural networks is NP-hard in fixed dimension. In Proc. Annual Conference on Neural Information Processing Systems 2023 (NeurIPS-2023), 2023.
[30] Vincent Froese, Christoph Hertrich, and Rolf Niedermeier. The computational complexity of ReLU network training parameterized by data dimensionality. Journal of Artificial Intelligence Research, 74:1775–1790, 2022. doi:10.1613/JAIR.1.13547.
[31] Peter Fulla and Stanislav Zivný. A Galois connection for weighted (relational) clones of infinite size. ACM Trans. Comput. Theory, 8(3):9:1–9:21, 2016. doi:10.1145/2898438.
[32] Esther Galby, Liana Khazaliya, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale. Metric dimension parameterized by feedback vertex set and other structural parameters. SIAM Journal on Discrete Mathematics, 37(4):2241–2264, 2023. doi:10.1137/22M1510911.
[33] Robert Ganian, Liana Khazaliya, Fionn Mc Inerney, and Mathis Rocton. The computational complexity of positive non-clashing teaching in graphs. In Proc. 13th International Conference on Learning Representations (ICLR-2025), 2025.
[34] Tomáš Gavenčiak, Martin Koutecký, and Dušan Knop. Integer programming in parameterized complexity: Five miniatures. Discrete Optimization, 44:100596, 2022. doi:10.1016/J.DISOPT.2020.100596.
[35] Àngel J. Gil, Miki Hermann, Gernot Salzer, and Bruno Zanuttini. Efficient algorithms for description problems over finite totally ordered domains. SIAM Journal on Computing, 38(3):922–945, 2008. doi:10.1137/050635900.
[36] Sylvain Guillemot and Dániel Marx. Finding small patterns in permutations in linear time. In Proc. 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2014), pages 82–101, 2014. doi:10.1137/1.9781611973402.7.
[37] Kurt Gödel. Zum intuitionistischen Aussagenkalkül. Anzeiger der Akademie der Wissenschaften in Wien, 69:65–66, 1932.
[38] Maximilian Hadek, Tomas Jakl, and Jakub Oprsal. A categorical perspective on constraint satisfaction: The wonderland of adjunctions. CoRR, abs/2503.10353, 2025. doi:10.48550/arXiv.2503.10353.
[39] Reiner Hähnle. Automated Deduction in Multiple-valued logics, volume 10 of International Series of Monographs on Computer Science. Oxford University Press, 1994.
[40] Meike Hatzel, Lars Jaffke, Paloma T. Lima, Tomáš Masařík, Marcin Pilipczuk, Roohani Sharma, and Manuel Sorge. Fixed-parameter tractability of directed multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation. In Proc. 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2023), pages 3229–3244, 2023. doi:10.1137/1.9781611977554.CH123.
[41] Peter Jonsson and Gustav Nordh. Approximability of clausal constraints. Theory of Computing Systems, 46(2):370–395, 2010. doi:10.1007/S00224-008-9145-7.
[42] Alexander S. Karpenko. Łukasiewicz Logics and Prime Numbers. Luniver Press, Beckington, 2006.
[43] Sammy Khalife, Hongyu Cheng, and Amitabh Basu. Neural networks with linear threshold activations: structure and algorithms. Mathematical Programming, 206(1):333–356, 2024. doi:10.1007/S10107-023-02016-5.
[44] Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström. Flow-augmentation I: directed graphs. Journal of the ACM, 72(1):5:1–5:38, 2025. doi:10.1145/3706103.
[45] Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström. Flow-augmentation III: complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints. SIAM Journal on Computing, 54(4):1065–1137, 2025. doi:10.1137/23M1553698.
[46] Stefan Kratsch, Dániel Marx, and Magnus Wahlström. Parameterized complexity and kernelizability of Max Ones and Exact Ones problems. ACM Transactions on Computation Theory, 8(1):1:1–1:28, 2016. doi:10.1145/2858787.
[47] Hendrik W. Lenstra. Integer programming with a fixed number of variables. Mathematics of Operations Research, 8(4):538–548, 1983. doi:10.1287/MOOR.8.4.538.
[48] James J. Lu, Neil V. Murray, and Erik Rosenthal. A framework for automated reasoning in multiple-valued logics. Journal of Automated Reasoning, 21(1):39–67, 1998. doi:10.1023/A:1005784309139.
[49] Dániel Marx. Parameterized complexity of constraint satisfaction problems. Computational Complexity, 14(2):153–183, 2005. doi:10.1007/S00037-005-0195-9.
[50] Dániel Marx and Michal Pilipczuk. Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask). In Proc. 31st International Symposium on Theoretical Aspects of Computer Science (STACS-2014), pages 542–553, 2014. doi:10.4230/LIPIcs.STACS.2014.542.
[51] Dániel Marx and Igor Razgon. Constant ratio fixed-parameter approximation of the edge multicut problem. Information Processing Letters, 109(20):1161–1166, 2009. doi:10.1016/J.IPL.2009.07.016.
[52] Neeldhara Misra, Manas Mulpuri, Prafullkumar Tale, and Gaurav Viramgami. Romeo and Juliet meeting in forest like regions. Algorithmica, 86(11):3465–3495, 2024. doi:10.1007/S00453-024-01264-X.
[53] Neil V. Murray and Erik Rosenthal. Adapting classical inference techniques to multiple-valued logics using signed formulas. Fundamentae Informaticae, 21(3):237–253, 1994. doi:10.3233/FI-1994-2135.
[54] George Osipov, Marcin Pilipczuk, and Magnus Wahlström. Parameterized complexity of MinCSP over the point algebra. In Proc. 32nd Annual European Symposium on Algorithms (ESA-2024), volume 308, pages 93:1–93:15, 2024. doi:10.4230/LIPIcs.ESA.2024.93.
[55] George Osipov and Magnus Wahlström. Parameterized complexity of equality MinCSP. In Proc. 31st Annual European Symposium on Algorithms (ESA-2023), volume 274, pages 86:1–86:17, 2023. doi:10.4230/LIPIcs.ESA.2023.86.
[56] Michal Pilipczuk, Marek Sokolowski, and Anna Zych-Pawlewicz. Compact representation for matrices of bounded twin-width. In Proc. 39th International Symposium on Theoretical Aspects of Computer Science (STACS-2022), pages 52:1–52:14, 2022. doi:10.4230/LIPIcs.STACS.2022.52.
[57] Emil Post. Introduction to a general theory of elementary propositions. American Journal of Mathematics, 643(3):163–185, 1921.
[58] Dmitriy Zhuk. A proof of the CSP dichotomy conjecture. Journal of the ACM, 67(5):30:1–30:78, 2020. doi:10.1145/3402029.

[bib.bib1] [1] Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. Journal of the ACM, 42(4):844–856, 1995. doi:10.1145/210332.210337.

[bib.bib2] [2] Carlos Ansótegui and Felip Manyà. New logical and complexity results for signed-SAT. In Proc. 33rd IEEE International Symposium on Multiple-Valued Logic (ISMVL-2023), pages 181–187, 2003. doi:10.1109/ISMVL.2003.1201404.

[bib.bib3] [3] L. Barto, J. Opršal, and M. Pinsker. The wonderland of reflections. Israel Journal of Mathematics, 223(1):363–398, February 2018. doi:10.1007/s11856-017-1621-9.

[bib.bib4] [4] Libor Barto, Andrei A. Krokhin, and Ross Willard. Polymorphisms, and how to use them. In The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 1–44. Dagstuhl Publishing, 2017. doi:10.4230/DFU.VOL7.15301.1.

[bib.bib5] [5] Bernhard Beckert, Reiner Hähnle, and Felip Manyà. The SAT problem of signed CNF formulas. In David Basin, Marcello D’Agostino, Dov M. Gabbay, Seán Matthews, and Luca Viganò, editors, Labelled Deduction, Applied Logic Series, vol 17, pages 59–80. Springer Netherlands, 2000.

[bib.bib6] [6] Manuel Bodirsky. Complexity of Infinite-Domain Constraint Satisfaction. Cambridge University Press, 2021.

[bib.bib7] [7] Manuel Bodirsky and Jan Kára. The complexity of temporal constraint satisfaction problems. J. ACM, 57(2):9:1–9:41, 2010. doi:10.1145/1667053.1667058.

[bib.bib8] [8] Manuel Bodirsky and Antoine Mottet. A dichotomy for first-order reducts of unary structures. Logical Methods in Computer Science, 14(2), 2018. doi:10.23638/LMCS-14(2:13)2018.

[bib.bib9] [9] Édouard Bonnet, László Egri, and Dániel Marx. Fixed-parameter approximability of Boolean MinCSPs. In Proc. 24th Annual European Symposium on Algorithms (ESA-2016), pages 18:1–18:18, 2016. doi:10.4230/LIPIcs.ESA.2016.18.

[bib.bib10] [10] Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width II: small classes. Combinatorial Theory, 2(2), 2022. doi:10.5070/C62257876.

[bib.bib11] [11] Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width III: max independent set, min dominating set, and coloring. SIAM Journal on Computing, 53(5):1602–1640, 2024. doi:10.1137/21M142188X.

[bib.bib12] [12] Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, and Szymon Toruńczyk. Twin-width IV: ordered graphs and matrices. Journal of the ACM, 71(3):1–45, 2024.

[bib.bib13] [13] Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width I: tractable FO model checking. Journal of the ACM, 69(1):3:1–3:46, 2022. doi:10.1145/3486655.

[bib.bib14] [14] Zarathustra Brady. Notes on CSPs and polymorphisms. CoRR, abs/2210.07383, 2022. doi:10.48550/arXiv.2210.07383.

[bib.bib15] [15] Karl Bringmann, Danny Hermelin, Matthias Mnich, and Erik Jan van Leeuwen. Parameterized complexity dichotomy for Steiner multicut. Journal of Computer and System Sciences, 82(6):1020–1043, 2016. doi:10.1016/J.JCSS.2016.03.003.

[bib.bib16] [16] Andrei Bulatov and Víctor Dalmau. A simple algorithm for mal’tsev constraints. SIAM Journal on Computing, 36(1):16–27, 2006. doi:10.1137/050628957.

[bib.bib17] [17] Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs. In Proc. 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS-2017), pages 319–330, 2017. doi:10.1109/FOCS.2017.37.

[bib.bib18] [18] Andrei A. Bulatov and Dániel Marx. Constraint satisfaction parameterized by solution size. SIAM Journal on Computing, 43(2):573–616, 2014. doi:10.1137/120882160.

[bib.bib19] [19] Clément Carbonnel. On redundancy in constraint satisfaction problems. In Proc. 28th International Conference on Principles and Practice of Constraint Programming (CP-2022), pages 11:1–11:15, 2022. doi:10.4230/LIPIcs.CP.2022.11.

[bib.bib20] [20] Witold Charatonik and Michal Wrona. 2-SAT problems in some multi-valued logics based on finite lattices. In Proc. 37th International Symposium on Multiple-Valued Logic (ISMVL-2007), page 21, 2007. doi:10.1109/ISMVL.2007.1.

[bib.bib21] [21] Sitan Chen, Adam R. Klivans, and Raghu Meka. Learning deep ReLU networks is fixed-parameter tractable. In Proc. 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS-2021), pages 696–707, 2021. doi:10.1109/FOCS52979.2021.00073.

[bib.bib22] [22] Victor Chepoi, Nadia Creignou, Miki Hermann, and Gernot Salzer. The Helly property and satisfiability of Boolean formulas defined on set families. European Jornal of Combinatorics, 31(2):502–516, 2010. doi:10.1016/J.EJC.2009.03.022.

[bib.bib23] [23] Rajesh Chitnis, László Egri, and Dániel Marx. List H-coloring a graph by removing few vertices. Algorithmica, 78(1):110–146, 2017. doi:10.1007/S00453-016-0139-6.

[bib.bib24] [24] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.

[bib.bib25] [25] Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, Marcin Pilipczuk, and Roohani Sharma. Parameterized complexity classification for interval constraints. In Proc. 18th International Symposium on Parameterized and Exact Computation (IPEC-2023), volume 285, pages 11:1–11:19, 2023. doi:10.4230/LIPIcs.IPEC.2023.11.

[bib.bib26] [26] Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, and Magnus Wahlström. Almost consistent systems of linear equations. ACM Transactions on Algorithms, 21(4):44:1–44:55, 2025. doi:10.1145/3733107.

[bib.bib27] [27] Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, and Magnus Wahlström. Parameterized approximability for modular linear equations. In Proc. 33rd Annual European Symposium on Algorithms (ESA-2025), pages 88:1–88:15, 2025. doi:10.4230/LIPIcs.ESA.2025.88.

[bib.bib28] [28] Peter C Fishburn and Ronald L Graham. Lexicographic Ramsey theory. Journal of Combinatorial Theory, Series A, 62(2):280–298, 1993.

[bib.bib29] [29] Vincent Froese and Christoph Hertrich. Training neural networks is NP-hard in fixed dimension. In Proc. Annual Conference on Neural Information Processing Systems 2023 (NeurIPS-2023), 2023.

[bib.bib30] [30] Vincent Froese, Christoph Hertrich, and Rolf Niedermeier. The computational complexity of ReLU network training parameterized by data dimensionality. Journal of Artificial Intelligence Research, 74:1775–1790, 2022. doi:10.1613/JAIR.1.13547.

[bib.bib31] [31] Peter Fulla and Stanislav Zivný. A Galois connection for weighted (relational) clones of infinite size. ACM Trans. Comput. Theory, 8(3):9:1–9:21, 2016. doi:10.1145/2898438.

[bib.bib32] [32] Esther Galby, Liana Khazaliya, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale. Metric dimension parameterized by feedback vertex set and other structural parameters. SIAM Journal on Discrete Mathematics, 37(4):2241–2264, 2023. doi:10.1137/22M1510911.

[bib.bib33] [33] Robert Ganian, Liana Khazaliya, Fionn Mc Inerney, and Mathis Rocton. The computational complexity of positive non-clashing teaching in graphs. In Proc. 13th International Conference on Learning Representations (ICLR-2025), 2025.

[bib.bib34] [34] Tomáš Gavenčiak, Martin Koutecký, and Dušan Knop. Integer programming in parameterized complexity: Five miniatures. Discrete Optimization, 44:100596, 2022. doi:10.1016/J.DISOPT.2020.100596.

[bib.bib35] [35] Àngel J. Gil, Miki Hermann, Gernot Salzer, and Bruno Zanuttini. Efficient algorithms for description problems over finite totally ordered domains. SIAM Journal on Computing, 38(3):922–945, 2008. doi:10.1137/050635900.

[bib.bib36] [36] Sylvain Guillemot and Dániel Marx. Finding small patterns in permutations in linear time. In Proc. 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2014), pages 82–101, 2014. doi:10.1137/1.9781611973402.7.

[bib.bib37] [37] Kurt Gödel. Zum intuitionistischen Aussagenkalkül. Anzeiger der Akademie der Wissenschaften in Wien, 69:65–66, 1932.

[bib.bib38] [38] Maximilian Hadek, Tomas Jakl, and Jakub Oprsal. A categorical perspective on constraint satisfaction: The wonderland of adjunctions. CoRR, abs/2503.10353, 2025. doi:10.48550/arXiv.2503.10353.

[bib.bib39] [39] Reiner Hähnle. Automated Deduction in Multiple-valued logics, volume 10 of International Series of Monographs on Computer Science. Oxford University Press, 1994.

[bib.bib40] [40] Meike Hatzel, Lars Jaffke, Paloma T. Lima, Tomáš Masařík, Marcin Pilipczuk, Roohani Sharma, and Manuel Sorge. Fixed-parameter tractability of directed multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation. In Proc. 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2023), pages 3229–3244, 2023. doi:10.1137/1.9781611977554.CH123.

[bib.bib41] [41] Peter Jonsson and Gustav Nordh. Approximability of clausal constraints. Theory of Computing Systems, 46(2):370–395, 2010. doi:10.1007/S00224-008-9145-7.

[bib.bib42] [42] Alexander S. Karpenko. Łukasiewicz Logics and Prime Numbers. Luniver Press, Beckington, 2006.

[bib.bib43] [43] Sammy Khalife, Hongyu Cheng, and Amitabh Basu. Neural networks with linear threshold activations: structure and algorithms. Mathematical Programming, 206(1):333–356, 2024. doi:10.1007/S10107-023-02016-5.

[bib.bib44] [44] Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström. Flow-augmentation I: directed graphs. Journal of the ACM, 72(1):5:1–5:38, 2025. doi:10.1145/3706103.

[bib.bib45] [45] Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström. Flow-augmentation III: complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints. SIAM Journal on Computing, 54(4):1065–1137, 2025. doi:10.1137/23M1553698.

[bib.bib46] [46] Stefan Kratsch, Dániel Marx, and Magnus Wahlström. Parameterized complexity and kernelizability of Max Ones and Exact Ones problems. ACM Transactions on Computation Theory, 8(1):1:1–1:28, 2016. doi:10.1145/2858787.

[bib.bib47] [47] Hendrik W. Lenstra. Integer programming with a fixed number of variables. Mathematics of Operations Research, 8(4):538–548, 1983. doi:10.1287/MOOR.8.4.538.

[bib.bib48] [48] James J. Lu, Neil V. Murray, and Erik Rosenthal. A framework for automated reasoning in multiple-valued logics. Journal of Automated Reasoning, 21(1):39–67, 1998. doi:10.1023/A:1005784309139.

[bib.bib49] [49] Dániel Marx. Parameterized complexity of constraint satisfaction problems. Computational Complexity, 14(2):153–183, 2005. doi:10.1007/S00037-005-0195-9.

[bib.bib50] [50] Dániel Marx and Michal Pilipczuk. Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask). In Proc. 31st International Symposium on Theoretical Aspects of Computer Science (STACS-2014), pages 542–553, 2014. doi:10.4230/LIPIcs.STACS.2014.542.

[bib.bib51] [51] Dániel Marx and Igor Razgon. Constant ratio fixed-parameter approximation of the edge multicut problem. Information Processing Letters, 109(20):1161–1166, 2009. doi:10.1016/J.IPL.2009.07.016.

[bib.bib52] [52] Neeldhara Misra, Manas Mulpuri, Prafullkumar Tale, and Gaurav Viramgami. Romeo and Juliet meeting in forest like regions. Algorithmica, 86(11):3465–3495, 2024. doi:10.1007/S00453-024-01264-X.

[bib.bib53] [53] Neil V. Murray and Erik Rosenthal. Adapting classical inference techniques to multiple-valued logics using signed formulas. Fundamentae Informaticae, 21(3):237–253, 1994. doi:10.3233/FI-1994-2135.

[bib.bib54] [54] George Osipov, Marcin Pilipczuk, and Magnus Wahlström. Parameterized complexity of MinCSP over the point algebra. In Proc. 32nd Annual European Symposium on Algorithms (ESA-2024), volume 308, pages 93:1–93:15, 2024. doi:10.4230/LIPIcs.ESA.2024.93.

[bib.bib55] [55] George Osipov and Magnus Wahlström. Parameterized complexity of equality MinCSP. In Proc. 31st Annual European Symposium on Algorithms (ESA-2023), volume 274, pages 86:1–86:17, 2023. doi:10.4230/LIPIcs.ESA.2023.86.

[bib.bib56] [56] Michal Pilipczuk, Marek Sokolowski, and Anna Zych-Pawlewicz. Compact representation for matrices of bounded twin-width. In Proc. 39th International Symposium on Theoretical Aspects of Computer Science (STACS-2022), pages 52:1–52:14, 2022. doi:10.4230/LIPIcs.STACS.2022.52.

[bib.bib57] [57] Emil Post. Introduction to a general theory of elementary propositions. American Journal of Mathematics, 643(3):163–185, 1921.

[bib.bib58] [58] Dmitriy Zhuk. A proof of the CSP dichotomy conjecture. Journal of the ACM, 67(5):30:1–30:78, 2020. doi:10.1145/3402029.

Going Beyond Twin-Width? CSPs with Unbounded Domain and Few Variables

Abstract

Keywords and phrases:

Category:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 High-level Background

(1) Constraint satisfaction problems (CSP).

(2) The twin-width parameter.

2 CSPs and Parameterized Complexity

3 Problem Statement

Definition 1.

Definition 2.

Definition 3.

Definition 4.

Definition 5.

Example 6.

4 Summary of Results

4.1 An Algebraic Approach for udCSP

Theorem 7.

4.2 udCSP with Monotone Maps and the Twin-width Parameter

Theorem 8.

Theorem 9.

Theorem 10.

Theorem 11.

Theorem 12.

Theorem 13.

Conjecture 14.

5 Applications and related work

Graph separation

One-hot

Many-valued logic

6 Discussion

A formal connection to parameterized MinCSP?

A dichotomy for non-binary relations

More classes of udCSP⁢(𝚪,𝓜) problems

References

More classes of $\textsc{udCSP}(\Gamma,\mathcal{M})$ problems