[Back]

S. Gaspers, St. Szeider:
"Strong Backdoors to Bounded Treewidth SAT";
Talk: FOCS, the Annual Symposium on Foundations of Computer Science, Berkeley, CA, USA; 2013-10-27 - 2013-10-29; in: "Proceedings FOCS 2013, The 54th Annual Symposium on Foundations of Computer Science", O. Reingold (ed.); IEEE, (2013), 489 - 498.

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 treewidth 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 TW≤t of CNF formulas whose associated graphs have treewidth at most t. The main results are positive:
There is a cubic-time algorithm that, given a CNF formula F and two constants k,t ≥ 0, either finds a strong TW≤t-backdoor set of size at most 2k, or concludes that F has no strong TW≤t-backdoor set of size at most k.
There is a cubic-time algorithm that, given a CNF formula F, computes the number of satisfying assignments of F or concludes that sbt(F)>k, for any pair of constants k,t ≥ 0. Here, sbt(F) denotes the size of a smallest strong TW≤t-backdoor set of F.
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 treewidth 1 (i.e., sbt(F)=1) entails formulas of arbitrarily large treewidth and arbitrarily large cycle cutsets (variables whose deletion makes the instance acyclic).

http://dx.doi.org/10.1109/FOCS.2013.59

Project Head Stefan Szeider:
The Parameterized Complexity of Reasoning Problems