Geodesic
Backdoors in combinatorial problems and their probabilistic generalizations
Prikladnaya Diskretnaya Matematika. Supplement, no. 15 (2022), pp. 100-104 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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: backdoors in combinatorial problems, Boolean Satisfiability Problem (SAT), 0-1-Integer Linear Programming. 
@article{PDMA_2022_15_a22,
     author = {A. A. Semenov},
     title = {Backdoors in combinatorial problems and their probabilistic generalizations},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {100--104},
     year = {2022},
     number = {15},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2022_15_a22/}
}
TY  - JOUR
AU  - A. A. Semenov
TI  - Backdoors in combinatorial problems and their probabilistic generalizations
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2022
SP  - 100
EP  - 104
IS  - 15
UR  - http://geodesic.mathdoc.fr/item/PDMA_2022_15_a22/
LA  - ru
ID  - PDMA_2022_15_a22
ER  - 
%0 Journal Article
%A A. A. Semenov
%T Backdoors in combinatorial problems and their probabilistic generalizations
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2022
%P 100-104
%N 15
%U http://geodesic.mathdoc.fr/item/PDMA_2022_15_a22/
%G ru
%F PDMA_2022_15_a22
A. A. Semenov. Backdoors in combinatorial problems and their probabilistic generalizations. Prikladnaya Diskretnaya Matematika. Supplement, no. 15 (2022), pp. 100-104. http://geodesic.mathdoc.fr/item/PDMA_2022_15_a22/

[1] Williams R., Gomes C. P., and Selman B., “Backdoors to typical case complexity”, Proc. IJCAI'03 (August, 2003), 1173–1178

[2] Chen Ch., Li R., Matematicheskaya logika i avtomaticheskoe dokazatelstvo teorem, Nauka, M., 1983

[3] Semenov A., Pavlenko A., Chivilikhin D., and Kochemazov S., “On probabilistic generalization of backdoors in Boolean satisfiability”, Proc. AAAI, 2022 https://www.aaai.org/AAAI22Papers/AAAI-8477.SemenovA.pdf

[4] Metropolis N. and Ulam S., “The Monte Carlo method”, J. Amer. Statistical Assoc., 44:247 (1949), 335–341 | DOI | MR | Zbl

[5] https://github.com/ctlab/EvoGuess/releases/tag/v2.0.0

[6] Dowling W. F. and Gallier J. H., “Linear-time algorithms for testing the satisfiability of propositional horn formulae”, J. Logic Programming, 1:3 (1984), 267–284 | DOI | MR | Zbl