Journal article icon

Journal article

Backdoors into heterogeneous classes of SAT and CSP

Abstract:

In this paper we extend the classical notion of strong and weak backdoor sets for SAT and CSP by allowing that different instantiations of the backdoor variables result in instances that belong to different base classes; the union of the base classes forms a heterogeneous base class. Backdoor sets to heterogeneous base classes can be much smaller than backdoor sets to homogeneous ones, hence they are much more desirable but possibly harder to find. We draw a detailed complexity landscape for ...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1016/j.jcss.2016.10.007

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
More from this funder
Name:
Royal Society
Funding agency for:
Zivny, S
Publisher:
Elsevier
Journal:
Journal of Computer and System Sciences More from this journal
Volume:
85
Pages:
38–56
Publication date:
2016-01-01
Acceptance date:
2016-10-24
DOI:
EISSN:
1090-2724
ISSN:
0022-0000
Keywords:
Pubs id:
pubs:654396
UUID:
uuid:f802cbe2-9158-4bc1-88ea-63ff070081fd
Local pid:
pubs:654396
Source identifiers:
654396
Deposit date:
2016-10-24

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP