There are various approaches to exploiting "hidden structure" in instances of hard combinatorial problems to allow faster algorithms than for general unstructured or random instances. For SAT and its counting version #SAT, hidden structure has been exploited in terms of decomposability and strong backdoor sets. Decomposability can be considered in terms of the tree width of a graph that is associated with the given CNF formula, for instance by considering clauses and variables as vertices of the graph, and making a variable adjacent with all the clauses it appears in. On the other hand, a strong backdoor set of a CNF formula is a set of variables such that each assignment to this set moves the formula into a fixed class for which (#)SAT can be solved in polynomial time. In this paper we combine the two above approaches. In particular, we study the algorithmic question of finding a small strong backdoor set into the class W ≤ t of CNF formulas whose associated graphs have tree width at most t. The main results are positive: (1) There is a cubic-time algorithm that, given a CNF formula F and two constants k, t ≥ 0, either finds a strong W_≤ t-backdoor set of size at most 2k, or concludes that F has no strong W_≤ t-backdoor set of size at most k. (2) There is a cubic-time algorithm that, given a CNF formula F, computes the number of satisfying assignments of F or concludes that sb_t(F)>k, for any pair of constants k, t ≥ 0. Here, sb_t(F) denotes the size of a smallest strong W_≤ t-backdoor set of F. We establish both results by distinguishing between two cases, depending on whether the tree width of the given formula is small or large. For both results the case of small tree width can be dealt with relatively standard methods. The case of large tree width is challenging and requires new and sophisticated combinatorial arguments. The main tool is an auxiliary graph whose ver- ices represent sub graphs in F's associated graph. It captures various ways to assemble large-tree width sub graphs in F's associated graph. This is used to show that every backdoor set of size k intersects a certain set of variables whose size is bounded by a function of k and t. For any other set of k variables, one can use the auxiliary graph to find an assignment t to these variables such that the graph associated with F[t] has tree width at least t+1. The significance of our results lies in the fact that they allow us to exploit algorithmically a hidden structure in formulas that is not accessible by any one of the two approaches (decomposability, backdoors) alone. Already a backdoor of size 1 on top of tree width 1 (i.e., sb_1(F)=1) entails formulas of arbitrarily large tree width and arbitrarily large cycle cut sets (variables that need to be deleted to make the instance a cyclic).
展开▼
