Backdoors into heterogeneous classes of SAT and CSP
Backdoor sets represent clever reasoning shortcuts through the search space for SAT and CSP. By instantiating the backdoor variables one reduces the given instance to several easy instances that belong to a tractable class.The overall time needed to solve the instance is exponential in the size of t...
| Main Authors: | , , , , |
|---|---|
| Format: | Conference item |
| Published: |
Association for the Advancement of Artificial
Intelligence
2014
|
| _version_ | 1826272229543903232 |
|---|---|
| author | Gaspers, S Misra, N Ordyniak, S Szeider, S Živný, S |
| author_facet | Gaspers, S Misra, N Ordyniak, S Szeider, S Živný, S |
| author_sort | Gaspers, S |
| collection | OXFORD |
| description | Backdoor sets represent clever reasoning shortcuts through the search space for SAT and CSP. By instantiating the backdoor variables one reduces the given instance to several easy instances that belong to a tractable class.The overall time needed to solve the instance is exponential in the size of the backdoor set, hence it is a challenging problem to find a small backdoor set if one exists; over the last years this problem has been subject of intensive research. In this paper we extend the classical notion of a strong backdoor set 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 the problem of detecting strong backdoor sets into heterogeneous base classes for SAT and CSP. We provide algorithms that establish fixed-parameter tractability under natural parameterizations, and we contrast the tractability results with hardness results that pinpoint the theoretical limits. Our results apply to the current state-of-the-art of tractable classes of CSP and SAT that are definable by restricting the constraint language. |
| first_indexed | 2024-03-06T22:09:14Z |
| format | Conference item |
| id | oxford-uuid:513b24b0-742c-43be-b0b6-2caf6d24a449 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T22:09:14Z |
| publishDate | 2014 |
| publisher | Association for the Advancement of Artificial
Intelligence |
| record_format | dspace |
| spelling | oxford-uuid:513b24b0-742c-43be-b0b6-2caf6d24a4492022-03-26T16:18:18ZBackdoors into heterogeneous classes of SAT and CSPConference itemhttp://purl.org/coar/resource_type/c_5794uuid:513b24b0-742c-43be-b0b6-2caf6d24a449Symplectic Elements at OxfordAssociation for the Advancement of Artificial Intelligence2014Gaspers, SMisra, NOrdyniak, SSzeider, SŽivný, SBackdoor sets represent clever reasoning shortcuts through the search space for SAT and CSP. By instantiating the backdoor variables one reduces the given instance to several easy instances that belong to a tractable class.The overall time needed to solve the instance is exponential in the size of the backdoor set, hence it is a challenging problem to find a small backdoor set if one exists; over the last years this problem has been subject of intensive research. In this paper we extend the classical notion of a strong backdoor set 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 the problem of detecting strong backdoor sets into heterogeneous base classes for SAT and CSP. We provide algorithms that establish fixed-parameter tractability under natural parameterizations, and we contrast the tractability results with hardness results that pinpoint the theoretical limits. Our results apply to the current state-of-the-art of tractable classes of CSP and SAT that are definable by restricting the constraint language. |
| spellingShingle | Gaspers, S Misra, N Ordyniak, S Szeider, S Živný, S Backdoors into heterogeneous classes of SAT and CSP |
| title | Backdoors into heterogeneous classes of SAT and CSP |
| title_full | Backdoors into heterogeneous classes of SAT and CSP |
| title_fullStr | Backdoors into heterogeneous classes of SAT and CSP |
| title_full_unstemmed | Backdoors into heterogeneous classes of SAT and CSP |
| title_short | Backdoors into heterogeneous classes of SAT and CSP |
| title_sort | backdoors into heterogeneous classes of sat and csp |
| work_keys_str_mv | AT gasperss backdoorsintoheterogeneousclassesofsatandcsp AT misran backdoorsintoheterogeneousclassesofsatandcsp AT ordyniaks backdoorsintoheterogeneousclassesofsatandcsp AT szeiders backdoorsintoheterogeneousclassesofsatandcsp AT zivnys backdoorsintoheterogeneousclassesofsatandcsp |