Backdoors in combinatorial problems and their probabilistic generalizations

We present some recent results about the structures which arise in many combinatorial problems under the term “Backdoors”. A backdoor for a constraint satisfaction problem is a set of variables, the knowledge of which makes it possible to solve the original problem more efficiently than without knowing a backdoor. In the past few years, backdoors have become quite a popular subject of research. They are actively investigated in both theoretical and practical areas of computer science. We will start from some simple modifications of known results about backdoors. In particular, we present one refinement of the well-known result from the paper by R. Williams, C. Gomes and B. Selman (2003) about the worst-case complexity estimation of SAT using strong backdoors. Also, we discuss a probabilistic generalization of a strong backdoor notion and show that this concept can improve the efficiency of algorithms applied to hard instances (both industrial and crafted ones) from Boolean Satisfiability (SAT) and 0-1-Integer Linear Programming (0-1-ILP). In particular, we present the results of computational experiments which demonstrate the ability of probabilistic backdoors to significantly speed up the solution of the aforementioned hard combinatorial problems.

Keywords

Authors

References