Abstract: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.
From: Kei Kimura [view email]
[v1]
Fri, 28 Nov 2025 06:36:53 UTC (44 KB)
[v2]
Thu, 5 Mar 2026 09:15:26 UTC (44 KB)
[v3]
Wed, 19 Aug 2026 09:17:53 UTC (49 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。