English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We study the parameterized complexity of MinCSP for so-called equalitylanguages, i.e., for finite languages over an infinite domain such as$\mathbb{N}$, where the relations are defined via first-order formulas whoseonly predicate is $=$. This is an important class of languages that forms thestarting point of all study of infinite-domain CSPs under the commonly usedapproach pioneered by Bodirsky, i.e., languages defined as reducts of finitelybounded homogeneous structures. Moreover, MinCSP over equality languages formsa natural class of optimisation problems in its own right, covering suchproblems as Edge Multicut, Steiner Multicut and (under singleton expansion)Edge Multiway Cut. We classify MinCSP$(\Gamma)$ for every finite equalitylanguage $\Gamma$, under the natural parameter, as either FPT, W[1]-hard butadmitting a constant-factor FPT-approximation, or not admitting aconstant-factor FPT-approximation unless FPT=W[2]. In particular, we describean FPT case that slightly generalises Multicut, and show a constant-factorFPT-approximation for Disjunctive Multicut, the generalisation of Multicutwhere the ``cut requests'' come as disjunctions over $d = O(1)$ individual cutrequests $s_i \neq t_i$. We also consider singleton expansions of equalitylanguages, i.e., enriching an equality language with the capability forassignment constraints $(x=i)$ for either finitely or infinitely many constants$i \in \mathbb{N}$, and fully characterize the complexity of the resultingMinCSP.

Parameterized Complexity of Equality MinCSP