Towards an algebraic approach to the reconfiguration CSP
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912943983034368 |
|---|---|
| author | Kimura, Kei |
| author_facet | Kimura, Kei |
| contents | This paper investigates the reconfiguration variant of the Constraint Satisfaction Problem (CSP), referred to as the Reconfiguration CSP (RCSP). Given a CSP instance and two of its solutions, RCSP asks whether one solution can be transformed into the other via a sequence of intermediate solutions, each differing by the assignment of a single variable. RCSP has attracted growing interest in theoretical computer science, and when the variable domain is Boolean, the computational complexity of RCSP exhibits a dichotomy depending on the allowed constraint types. A notable special case is the reconfiguration of graph homomorphisms -- also known as graph recoloring -- which has been studied using topological methods. We propose a novel algebraic approach to RCSP, inspired by techniques used in classical CSP complexity analysis. Unlike traditional methods based on total operations, our framework employs partial operations to capture a reduction involving equality constraints. This perspective facilitates the extension of complexity results from Boolean domains to more general settings, demonstrating the versatility of partial operations in identifying tractable RCSP instances. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_22914 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Towards an algebraic approach to the reconfiguration CSP Kimura, Kei Data Structures and Algorithms This paper investigates the reconfiguration variant of the Constraint Satisfaction Problem (CSP), referred to as the Reconfiguration CSP (RCSP). Given a CSP instance and two of its solutions, RCSP asks whether one solution can be transformed into the other via a sequence of intermediate solutions, each differing by the assignment of a single variable. RCSP has attracted growing interest in theoretical computer science, and when the variable domain is Boolean, the computational complexity of RCSP exhibits a dichotomy depending on the allowed constraint types. A notable special case is the reconfiguration of graph homomorphisms -- also known as graph recoloring -- which has been studied using topological methods. We propose a novel algebraic approach to RCSP, inspired by techniques used in classical CSP complexity analysis. Unlike traditional methods based on total operations, our framework employs partial operations to capture a reduction involving equality constraints. This perspective facilitates the extension of complexity results from Boolean domains to more general settings, demonstrating the versatility of partial operations in identifying tractable RCSP instances. |
| title | Towards an algebraic approach to the reconfiguration CSP |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2511.22914 |