# Parameterized Complexity of Equality MinCSP

arXiv: https://arxiv.org/abs/2305.11131 · HTML: https://mlsanity.com/paper/2305.11131/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 May 2023.

## Built on by (most cited first, 1 of 1)

- [CSPs with Few Alien Constraints](https://mlsanity.com/paper/2408.12909/) (2024)

## Abstract (arXiv)

We study the parameterized complexity of MinCSP for so-called equality languages, i.e., for finite languages over an infinite domain such as mathbbN, where the relations are defined via first-order formulas whose only predicate is =. This is an important class of languages that forms the starting point of all study of infinite-domain CSPs under the commonly used approach pioneered by Bodirsky, i.e., languages defined as reducts of finitely bounded homogeneous structures. Moreover, MinCSP over equality languages forms a natural class of optimisation problems in its own right, covering such problems as Edge Multicut, Steiner Multicut and (under singleton expansion) Edge Multiway Cut. We classify MinCSP(Gamma) for every finite equality language Gamma, under the natural parameter, as either FPT, W[1]-hard but admitting a constant-factor FPT-approximation, or not admitting a constant-factor FPT-approximation unless FPT=W[2]. In particular, we describe an FPT case that slightly generalises Multicut, and show a constant-factor FPT-approximation for Disjunctive Multicut, the generalisation of Multicut where the ``cut requests'' come as disjunctions over d = O(1) individual cut requests si neq ti. We also consider singleton expansions of equality languages, i.e., enriching an equality language with the capability for assignment constraints (x=i) for either finitely or infinitely many constants i ∈ mathbbN, and fully characterize the complexity of the resulting MinCSP.