Parameterized Complexity of Equality MinCSP

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.