Wady Naanaa - New schemes for simplifying binary constraint satisfaction problems

dmtcs:4398 - Discrete Mathematics & Theoretical Computer Science, June 4, 2020, vol. 22 no. 1 - https://doi.org/10.23638/DMTCS-22-1-10
New schemes for simplifying binary constraint satisfaction problems

Authors: Wady Naanaa

    Finding a solution to a Constraint Satisfaction Problem (CSP) is known to be an NP-hard task. This has motivatedthe multitude of works that have been devoted to developing techniques that simplify CSP instances before or duringtheir resolution.The present work proposes rigidly enforced schemes for simplifying binary CSPs that allow the narrowing of valuedomains, either via value merging or via value suppression. The proposed schemes can be viewed as parametrizedgeneralizations of two widely studied CSP simplification techniques, namely, value merging and neighbourhoodsubstitutability. Besides, we show that both schemes may be strengthened in order to allow variable elimination,which may result in more significant simplifications. This work contributes also to the theory of tractable CSPs byidentifying a new tractable class of binary CSP.


    Volume: vol. 22 no. 1
    Section: Discrete Algorithms
    Published on: June 4, 2020
    Accepted on: June 4, 2020
    Submitted on: March 22, 2018
    Keywords: variable elimination,tractable CSP,Constraint satisfaction problems,value merging,[INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI],[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]

    Share

    Consultation statistics

    This page has been seen 310 times.
    This article's PDF has been downloaded 138 times.