Algorithms for Computing Backbones of Propositional Formulae∗

The problem of propositional satisfiability (SAT) has found a number of applications in both theoreti-cal and practical computer science. In many appli-cations, however, knowing a formula’s satisfiability alone is insufficient. Often, some other properties of the formula need to be computed. This article fo-cuses on one such property: the backbone of a for-mula, which is the set of literals that are true in all the formula’s models. Backbones find theoretical ap-plications in characterization of SAT problems and they also find practical applications in product con-figuration or fault localization. This article overviews existing algorithms for backbone computation and in-troduces two novel ones. Further, an extensive evalu-ation of the algorithms is presented. This evaluation demonstrates that one of the novel algorithms signif-icantly outperforms the existing ones.