Abstract
We study the parameterized complexity of MinCSP for socalled equality languages, i.e., for finite languages over an infinite domain such as ℕ, where the relations are defined via firstorder formulas whose only predicate is =. This is an important class of languages that forms the starting point of all study of infinitedomain 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(Γ) for every finite equality language Γ, under the natural parameter, as either FPT, W[1]hard but admitting a constantfactor FPTapproximation, or not admitting a constantfactor FPTapproximation unless FPT=W[2]. In particular, we describe an FPT case that slightly generalises Multicut, and show a constantfactor FPTapproximation for Disjunctive Multicut, the generalisation of Multicut where the "cut requests" come as disjunctions over O(1) individual cut requests s_i ≠ t_i. We also consider singleton expansions of equality languages, enriching an equality language with the capability for assignment constraints (x = i) for either a finite or infinitely many constants i, and fully characterize the complexity of the resulting MinCSP.
BibTeX  Entry
@InProceedings{osipov_et_al:LIPIcs.ESA.2023.86,
author = {Osipov, George and Wahlstr\"{o}m, Magnus},
title = {{Parameterized Complexity of Equality MinCSP}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {86:186:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772952},
ISSN = {18688969},
year = {2023},
volume = {274},
editor = {G{\o}rtz, Inge Li and FarachColton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18739},
URN = {urn:nbn:de:0030drops187393},
doi = {10.4230/LIPIcs.ESA.2023.86},
annote = {Keywords: parameterized complexity, constraint satisfaction, parameterized approximation}
}
Keywords: 

parameterized complexity, constraint satisfaction, parameterized approximation 
Collection: 

31st Annual European Symposium on Algorithms (ESA 2023) 
Issue Date: 

2023 
Date of publication: 

30.08.2023 