Skip to Main content Skip to Navigation
New interface
Preprints, Working Papers, ...

Variable elimination in binary CSPs

Abstract : We investigate rules which allow variable elimination in binary CSP (constraint satisfaction problem) instances while conserving satisfiability. We study variable-elimination rules based on the language of forbidden patterns enriched with counting and quantification over variables and values. We propose new rules and compare them, both theoretically and experimentally. We give optimised algorithms to apply these rules and show that each define a novel tractable class. Using our variable-elimination rules in preprocessing allowed us to solve more benchmark problems than without.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

https://hal-amu.archives-ouvertes.fr/hal-02142769
Contributor : Cyril Terrioux Connect in order to contact the contributor
Submitted on : Tuesday, February 16, 2021 - 11:03:12 AM
Last modification on : Thursday, July 14, 2022 - 4:13:14 AM
Long-term archiving on: : Monday, May 17, 2021 - 6:52:40 PM

File

1905.04209.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02142769, version 1
  • ARXIV : 1905.04209

Citation

Martin Cooper, Achref El Mouelhi, Cyril Terrioux. Variable elimination in binary CSPs. 2019. ⟨hal-02142769⟩

Share

Metrics

Record views

182

Files downloads

42