Notice
This item was automatically migrated from a legacy system. It's data has not been checked and might not meet the quality criteria of the present system.
Record link: 
http://hdl.handle.net/20.500.12708/27722
-
Title: 
Backdoors to Satisfaction
-
Citation: 
Gaspers, S., & Szeider, S. (2012). Backdoors to Satisfaction. In H. L. Bodlaender, R. G. Downey, F. Fomin, & D. Marx (Eds.), The Multivariate Algorithmic Revolution and Beyond (pp. 287–317). Springer LNCS. https://doi.org/10.1007/978-3-642-30891-8_15
-
Publisher DOI: 
10.1007/978-3-642-30891-8_15
-
Publication Type: 
Book Contribution - Edited Volume Contribution
en
Authors: 
Gaspers, Serge 
Szeider, Stefan 
-
Organisational Unit: 
E192-03 - Forschungsbereich Knowledge Based Systems 
-
Published in: 
The Multivariate Algorithmic Revolution and Beyond 
-
Date (published): 
2012
-
Number of Pages: 
31
-
Peer reviewed: 
Yes
-
Abstract: 
A backdoor set is a set of variables of a propositional formula such that fixing the truth values of the variables in the backdoor set moves the formula into some polynomial-time decidable class. If we know a small backdoor set we can reduce the question of whether the given formula is satisfiable to the same question for one or several easy formulas that belong to the tractable class under consideration. In this survey we review parameterized complexity results for problems that arise in the context of backdoor sets, such as the problem of finding a backdoor set of size at most k , parameterized by k . We also discuss recent results on backdoor sets for problems that are beyond NP.
en
Project title: 
The Parameterized Complexity of Reasoning Problems: 239962 (Europäischer Forschungsrat (ERC)) 
-
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
Mathematik, Informatik
-
Appears in Collections:
Book Contribution

Show full item record

Page view(s)

208
checked on Nov 23, 2023

Google ScholarTM

Check