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 fine-grained and the parameterized complexity of severalgeneralizations of binary constraint satisfaction problems (BINARY-CSPs), thatsubsume variants of graph colouring problems. Our starting point is theobservation that several algorithmic approaches that resulted in complexityupper bounds for these problems, share a common structure. We thus explore analgebraic approach relying on semirings that unifies different generalizationsof BINARY-CSPs (such as the counting, the list, and the weighted versions), andthat facilitates a general algorithmic approach to efficiently solving them.The latter is inspired by the (component) twin-width parameter introduced byBonnet et al., which we generalize via edge-labelled graphs in order toformulate it to arbitrary binary constraints. We consider input instances withbounded component twin-width, as well as constraint templates of boundedcomponent twin-width, and obtain an FPT algorithm as well as an improved,exponential-time algorithm, for broad classes of binary constraints. Weillustrate the advantages of this framework by instantiating our generalalgorithmic approach on several classes of problems (e.g., the $H$-coloringproblem and its variants), and showing that it improves the best complexityupper bounds in the literature for several well-known problems.

Component twin-width as a parameter for BINARY-CSP and its semiring generalisations