Component twin-width as a parameter for BINARY-CSP and its semiring generalisations
This provides improved algorithmic tools for solving constraint satisfaction problems, which is incremental but practically useful for theoretical computer science and combinatorial optimization.
The authors developed an algebraic framework using semirings to unify various generalizations of binary constraint satisfaction problems (BINARY-CSPs), such as counting, list, and weighted versions, and extended the component twin-width parameter to these problems. They obtained an FPT algorithm and improved exponential-time algorithms for broad classes of binary constraints, demonstrating better complexity bounds for several well-known problems like H-coloring variants.
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.