A Decomposition Technique for CSPs Using Maximal Independent Sets and Its Integration with Local Search

All Papers

We introduce IndSet, a technique for decomposing a Constraint Satisfaction Problem (CSP) by identifying a maximal independent set in the constraint graph of the CSP. We argue that this technique reduces the complexity of solving the CSP exponentially by the size of the maximal independent set, and yields compact and robust solutions. We discuss how to integrate this decomposition technique with local search, and evaluate SLS/IndSet, which combines IndSet with a stochastic local search. Finally, we discuss the benefit of identifying dangling components of the decomposed constraint graph, and evaluate SLS/IndSet+Dangles, a strategy that exploits this structural improvement.