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

arXiv: https://arxiv.org/abs/2207.12368 · HTML: https://mlsanity.com/paper/2207.12368/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 36 references that are in the map.
- First posted on arXiv 14 Jul 2022.

## Builds on (most cited first, 10 of 10)

- [Algebraic approach to promise constraint satisfaction](https://mlsanity.com/paper/1811.00970/) (2018)
- [Twin-width I: tractable FO model checking](https://mlsanity.com/paper/2004.14789/) (2020)
- [Twin-width II: small classes](https://mlsanity.com/paper/2006.09877/) (2020)
- [A dichotomy theorem for nonuniform CSPs simplified](https://mlsanity.com/paper/2007.09099/) (2020)
- [Twin-width IV: ordered graphs and matrices](https://mlsanity.com/paper/2102.03117/) (2021)
- [Twin-width and permutations](https://mlsanity.com/paper/2102.06880/) (2021)
- [Twin-width and polynomial kernels](https://mlsanity.com/paper/2107.02882/) (2021)
- [Twin-width VI: the lens of contraction sequences](https://mlsanity.com/paper/2111.00282/) (2021)
- [Deciding twin-width at most 4 is NP-complete](https://mlsanity.com/paper/2112.08953/) (2021)
- [Twin-width VIII: delineation and win-wins](https://mlsanity.com/paper/2204.00722/) (2022)

## Abstract (arXiv)

We investigate the fine-grained and the parameterized complexity of several generalizations of binary constraint satisfaction problems (BINARY-CSPs), that subsume variants of graph colouring problems. Our starting point is the observation that several algorithmic approaches that resulted in complexity upper bounds for these problems, share a common structure. We thus explore an algebraic approach relying on semirings that unifies different generalizations of BINARY-CSPs (such as the counting, the list, and the weighted versions), and that facilitates a general algorithmic approach to efficiently solving them. The latter is inspired by the (component) twin-width parameter introduced by Bonnet et al., which we generalize via edge-labelled graphs in order to formulate it to arbitrary binary constraints. We consider input instances with bounded component twin-width, as well as constraint templates of bounded component twin-width, and obtain an FPT algorithm as well as an improved, exponential-time algorithm, for broad classes of binary constraints. We illustrate the advantages of this framework by instantiating our general algorithmic approach on several classes of problems (e.g., the H-coloring problem and its variants), and showing that it improves the best complexity upper bounds in the literature for several well-known problems.