A new empirical study of weak backdoors

P. Gregory, M. Fox, D. Long

Research output: Contribution to conferencePaperpeer-review

11 Citations (Scopus)

Abstract

Work by Kilby, Slaney, Thiebaux and Walsh [1] showed that the backdoors and backbones of unstructured Random 3SAT instances are largely disjoint. In this work we extend this study to the consideration of backdoors in SAT encodings of structured problems. We show that the results of Kilby et al. also apply to structured problems. Further, we analyse the frequency with which individual variables appear in backdoors for specific problem instances. In all problem classes there are variables with particularly high frequencies of backdoor membership. Backbone variables that do appear in backdoors typically appear in very few.
Original languageEnglish
Pages618-623
Number of pages5
Publication statusPublished - 2008
Event14th International Conference on Principles and Practice of Constraint Programming - Sydney, Australia
Duration: 1 Sept 2008 → …

Conference

Conference14th International Conference on Principles and Practice of Constraint Programming
CitySydney, Australia
Period1/09/08 → …

Keywords

  • weak backdoors
  • SAT encodings
  • structured problems

Fingerprint

Dive into the research topics of 'A new empirical study of weak backdoors'. Together they form a unique fingerprint.

Cite this