A Tree Decomposition Based Approach to Solve Structured SAT Instances
Djamal Habet, Lionel Paris, Cyril Terrioux · 2009
The main purpose of the paper is to solve structured instances of the satisfiability problem. The structure of a SAT instance is represented by an hypergraph, whose vertices correspond to the variables and the hyper-edges to the clauses. The proposed method is based on a tree decomposition of this hyper-graph which guides the enumeration process of a DPLL-like method. During the search, the method makes explicit some information which is recorded as structural goods and nogoods. By exploiting this information, the method avoids some redundancies in the search, and so it guarantees a bounded theoretical time complexity which is related to the tree-decomposition. Finally, the method is assessed on structured SAT benchmarks.