Showing 2023Show all
3 papers · 1 filter
cs.DS2023
Parameterized Complexity of MinCSP over the Point Algebra
George Osipov, Marcin Pilipczuk, Magnus Wahlström
The input in the Minimum-Cost Constraint Satisfaction Problem (MinCSP) over the Point Algebra contains a set of variables, a collection of constraints of the form , ,…
cs.DS2023
Parameterized Complexity Classification for Interval Constraints
Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak +3
Constraint satisfaction problems form a nicely behaved class of problems that lends itself to complexity classification results. From the point of view of parameterized complexity,…
cs.DS2023
Parameterized Complexity of Equality MinCSP
George Osipov, Magnus Wahlström
We study the parameterized complexity of MinCSP for so-called equality languages, i.e., for finite languages over an infinite domain such as , where the relations are d…