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
Version:
Publisher's version

Actions


Access Document


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

Authors


Gaspers, S More by this author
Ordyniak, S More by this author
Szeider, S More by this author
More by this author
Department:
Oxford, MPLS, Computer Science
More from this funder
Funding agency for:
Živný, S
Australian Government More from this funder
Expand funders...
Publisher:
Elsevier Publisher's website
Journal:
Journal of Computer and System Sciences Journal website
Volume:
85
Pages:
38-56
Publication date:
2016-11-05
Acceptance date:
2016-10-23
DOI:
ISSN:
0022-0000 and 1090-2724
Pubs id:
pubs:654370
URN:
uri:88836faf-6750-41d2-8f9c-ba7c96a410c5
UUID:
uuid:88836faf-6750-41d2-8f9c-ba7c96a410c5
Local pid:
pubs:654370

Terms of use


Metrics



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

TO TOP