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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We investigate the parameterized complexity of Binary CSP parameterized bythe vertex cover number and the treedepth of the constraint graph, as well asby a selection of related modulator-based parameters. The main findings are asfollows:  i) Binary CSP parameterized by the vertex cover number is$\mathrm{W}[3]$-complete. More generally, for every positive integer $d$,Binary CSP parameterized by the size of a modulator to a treedepth-d graph is$\mathrm{W}[2d+1]$-complete. This provides a new family of natural problemsthat are complete for odd levels of the W-hierarchy.  ii) We introduce a new complexity class XSLP, defined so that Binary CSPparameterized by treedepth is complete for this class. We provide twoequivalent characterizations of XSLP: the first one relates XSLP to a model ofan alternating Turing machine with certain restrictions on conondeterminism andspace complexity, while the second one links XSLP to the problem ofmodel-checking first-order logic with suitably restricted universalquantification. Interestingly, the proof of the machine characterization ofXSLP uses the concept of universal trees, which are prominently featured in therecent work on parity games  iii) We describe a new complexity hierarchy sandwiched between theW-hierarchy and the A-hierarchy: For every odd $t$, we introduce aparameterized complexity class $\mathrm{S}[t]$ with $\mathrm{W}[t]\subseteq\mathrm{S}[t]\subseteq \mathrm{A}[t]$, defined using a parameter thatinterpolates between the vertex cover number and the treedepth.  We expect that many of the studied classes will be useful in the future forpinpointing the complexity of various structural parameterizations of graphproblems.

Parameterized Complexity of Binary CSP: Vertex Cover, Treedepth, and Related Parameters