Recursive Backdoors for SAT

Nikolas Mählmann, Sebastian Siebertz, Alexandre Vigny

A strong backdoor in a formula $\varphi$ of propositional logic to a tractable class $\mathcal{C}$ of formulas is a set $B$ of variables of $\varphi$ such that every assignment of the variable…